Relation between sizes of chains and antichains in a poset

discrete mathematicsgraph theoryorder-theory

The questions is to,

Show that every partially ordered set with $n$ elements either contains a chains of size greater than $c$ or an anti-chain of size at least $n/c$.

I only know definitions of chains and anti-chains but couldn't proceed with just that much.
I came across Dilworth's theorem so I was attempting induction using Dilworth but am unable to proceed further.

I know that if for a given poset $P$, let the size of the maximal chain is $r$, then I can partition $P$ into $r$ anti-chains but how should I take thiss further ?

Best Answer

Suppose there's no chain of size $>c$. Then in every decomposition of $P$ into disjoint chains, there are at least $n/c$ chains. Now by Dilworth's theorem, the size of the largest antichain is the size of the smallest chain covering, so is at least $n/c$, as each chain covering has $\ge n/c$ chains.

Related Question