Two proofs of Dilworth's theorem

The minimal number $m$ of disjoint chains covering a finite poset $P$ equals the maximal size $M$ of an antichain in $P$.

Proof (due to Perles [1]): Inequality $m\geq M$ is trivial because no chain can cover more than one element of every antichain and, hence, of an antichain with $M$ elements.

To prove $m\leq M$, argue by induction on $|P|$. If no two elements of $P$ are comparable, then $P$ itself is an antichain of $|P|=M$ elements, and can be covered by $M$ chains, each consisting of one element. Otherwise, consider a chain $C=\{0,1\}$ where $0\in P$ is some minimal, and $1\in P$ some maximal element in $P$. If every antichain in $P\setminus C$ has at most $M-1$ elements, then by the induction assumption, $P\setminus C$ can be covered by $M-1$ disjoint chains. Together with $C$, these chains cover entire $P$, implying that $m\leq M$ in this case.

Now assume that $P\setminus C$ has an antichain $A$ of size $|A|=M$. Consider the sets \[ P^+=\{x\in P\colon \mbox{$x\geq a$ for some $a\in A$}\}\ \ \mbox{ and }\ \ P^-=\{x\in P\colon \mbox{$x\leq a$ for some $a\in A$}\}. \] Note that

$P^+\cup P^-=P$, for otherwise the antichain $A$ would not be maximal ($A$ could be extended by adding any element not in the union);
$P^+\cap P^-=A$, because if $x$ is in the intersection, then $a\leq x\leq b$ for some elements $a,b\in A$, meaning that $a$ and $b$ are comparable by transitivity; since $A$ is an antichain, the only possibility is that $a=b$ and they both equal $x$.

Since $0\not\in A$ and $0$ is a minimal element of $P$, we have that $0\not\in P^+$. Similarly, $1\not\in P^-$. Thus, both posets $P^+$ and $P^-$ are strictly smaller than $P$. By the induction hypothesis, each of these sets can be partitioned into $M$ chains and since $P^+\cap P^-=A$, we can combine these chains to form the partition of the original set. Namely, if $\{C_a^+\colon a\in A\}$ is a decomposition of $P^+$, and $\{C_a^-\colon a\in A\}$ is a decomposition of $P^-$ into $M=|A|$ disjoint chains, then $\{C_a^+\cup C_a^-\colon a\in A\}$ is a decomposition of the entire poset $P$ into $M$ disjoint chains. Hence, $m\leq M$. $\Box$

In the book we presented a proof due to Galvin. Below we give a sightly more detailed version of this proof.

Suppose that the largest antichain in the poset $P$ has size $r$. Then $P$ can be partitioned into $r$ chains.

Proof: We use induction on the cardinality of $P$. Let $a$ be a maximal element of $P$, and let $k$ be the size of a largest antichain in $P'=P\setminus\{a\}$; hence, $k\leq r$. By the induction hypothesis, $P'$ is the union of $k$ disjoint chains $C_1,\ldots,C_k$. Every $k$-element antichain in $P'$ consists of one element from each $C_i$. Let $a_i$ be the maximal element in $C_i$ which belongs to some $k$-element antichain in $P'$.

It is not difficult to see that $A=\{a_1,\ldots,a_k\}$ is an antichain in $P'$. Suppose towards a contradiction that $a_i < a_j$ for some $i$ and $j$. By definition, $a_i$ is in some $k$-antichain $A_i$ and $a_j$ is in some $k$-antichain $A_j$. Since $A_j$ is a maximal antichain, it must intersect the chain $C_i$. Hence, there is an $x$ in $C_i \cap A_j$. By definition of $a_i$ we have $x \leq a_i$, hence by transitivity $x < a_j$. But that's a contradiction because $x$ and $a_j$ are in the same antichain $A_j$.

If $A\cup\{a\}$ is an antichain in $P$, then $k\leq r-1$, and we are done: the chains $C_1,\ldots,C_k$ and $\{a\}$ give us a desired decomposition of $P$ into $k+1\leq r$ chains. Otherwise, we have $a>a_i$ for some $i$. Then $K=\{a\}\cup\{x\in C_i~\colon~x\leq a_i\}$ is a chain in $P$, and there are no $k$-element antichains in $P\setminus K$ (since $a_i$ was the maximal element of $C_i$ participating in such an antichain). By the induction hypothesis, $P\setminus K$ is the union of $k-1$ disjoint chains. Together with the chain $K$, these chains cover entire $P$, as desired. $\Box$

References:

M.A. Perles, A proof of Dilworth’s decomposition theorem for partially ordered sets, Israel Jour. Math., 1 (1963) 105-107.

Return to the home page of the 2nd edition