Relation between sizes of chains and antichains in a poset

Question

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 ?

Answer 1

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.

Answer 2

(We are assuming that $\frac nc$ is an integer, but you can see everything going through with slight modification if it were not).

Let $P$ be a poset with $n$ elements, and $c$ be the size of the maximal chain in $P$.

Then, by your theorem, $P$ can be partitioned into $c$ anti-chains.

When you partition a set of $n$ points into $c$ distinct parts, then at least one part has size greater than or equal to $\frac nc$, by the fact that the maximum of every set of numbers must exceed or equal the average.

So, there is an antichain of size at least $\frac nc$.

Therefore, for all $d$ : if $d > c$, then there is no chain of size $d$, but there is an antichain of size $\frac nc > \frac nd$.

If $d \leq c$, then there is a chain of size $c \geq d$.

Either way, we are done.