dual of Dilworth’s theorem

Theorem 1.

Let $P$ be a poset of height $h$ . Then $P$ can be partitioned into $h$ antichains and furthermore at least $h$ antichains are required.

Proof.

Induction on $h$ . If $h=1$ , then no elements of $P$ are comparable, so $P$ is an antichain. Now suppose that $P$ has height $h\\geq 2$ and that the theorem is true for $h-1$ . Let $A_{1}$ be the set of maximal elements of $P$ . Then $A_{1}$ is an antichain in $P$ and $P-A_{1}$ has height $h-1$ since we have removed precisely one element from every chain. Hence, $P-A_{1}$ can be paritioned into $h-1$ antichains $A_{2},A_{3},\\dots A_{h}$ . Now we have the partition $A_{1}\\cup A_{2}\\cup\\dots\\cup A_{h}$ of $P$ into $h$ antichains as desired.

The necessity of $h$ antichains is trivial by the pigeonhole principle; since $P$ has height $h$ , it has a chain of length $h$ , and each element of this chain must be placed in a different antichain of our partition.∎

单词	DualOfDilworthsTheorem
释义	dual of Dilworth’s theorem Theorem 1. Let $P$ be a poset of height $h$ . Then $P$ can be partitioned into $h$ antichains and furthermore at least $h$ antichains are required. Proof. Induction on $h$ . If $h=1$ , then no elements of $P$ are comparable, so $P$ is an antichain. Now suppose that $P$ has height $h\\geq 2$ and that the theorem is true for $h-1$ . Let $A_{1}$ be the set of maximal elements of $P$ . Then $A_{1}$ is an antichain in $P$ and $P-A_{1}$ has height $h-1$ since we have removed precisely one element from every chain. Hence, $P-A_{1}$ can be paritioned into $h-1$ antichains $A_{2},A_{3},\\dots A_{h}$ . Now we have the partition $A_{1}\\cup A_{2}\\cup\\dots\\cup A_{h}$ of $P$ into $h$ antichains as desired. The necessity of $h$ antichains is trivial by the pigeonhole principle; since $P$ has height $h$ , it has a chain of length $h$ , and each element of this chain must be placed in a different antichain of our partition.∎
随便看	p-adic valuation PadovanSequence Padovan sequence PairingFunction pairing function PairwiseComaximalIdealsProperty pairwise comaximal ideals property PairwiseDisjoint pairwise disjoint PaleyWienerTheorem Paley-Wiener theorem Palindrome palindrome PalindromicNumber palindromic number PalindromicPrime palindromic prime PandigitalNumber pandigital number PappussCentroidTheorem PappussTheorem Pappus’s centroid theorem Pappus’s theorem ParabolicSubgroup parabolic subgroup