### 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:** 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 a minimal, and $1\in P$ a 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.
- $P^+\cap P^-=A$, for otherwise $A$ would not be an antichain.

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.

**Theorem 8.2** 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$

Return to
the
home page of the 2nd edition