Dilworths Theorem proof doubt

112 Views Asked by At

This is the proof I am talking about http://www.math.cmu.edu/~af1p/Teaching/Combinatorics/F03/Class14.pdf

When you take a maximal chain C in P and then obtain antichains in P\C, if the size of the maximum size antichain in P was m can you get an antichain in P\C of size m?

From the pdf: Can Case 2 ever happen?

1

There are 1 best solutions below

0
On BEST ANSWER

Consider $P = \bf{2} \times \bf{3}$, where $\bf{n}$ is the $n$-element chain on the set $\{0, 1, \dots, n - 1\}$. The maximal size of antichain in $P$ is $2$. Take maximal chain $C = \{(0, 0), (0, 1), (1, 1), (1, 2)\} \subset P$. Note that $P \setminus C = \{(1, 0), (0, 2)\}$ which is an antichain in $P$ of size $2$.