Let $\mathcal{P}=(X, \leq)$ be a partial order. Define $height(\mathcal{P})$ as max length of chain and $width(\mathcal{P})$ as max cardinality of antichain. I have to show two things:
- if $|X|>mn$ then $height(\mathcal{P}) \geq m+1$ or $width(\mathcal{P}) \geq n+1$
- if $|X|=n$ then $height(\mathcal{P}) \geq \lfloor\sqrt{n-1}\rfloor+1$ or $width(\mathcal{P}) \geq \lfloor\sqrt{n-1}\rfloor+1$
My attempt to the first one:
Let's assume that $|X| > mn$ but $height(\mathcal{P}) < m+1$ or $width(\mathcal{P}) < n+1$. By Dilworth's theorem we know that max cardinality of antichain is minimum cardinality of chains. If $|\mathcal{L}|=width(\mathcal{P})$ is the min number of chains and $a=height(\mathcal{P})$ then $|X| \leq |\mathcal{L}|a \leq mn $, but $|X|> mn$, so by contradiction the statement is true.
However, I have a hard time with the second one. I do it similarly but get stuck on the last step: $$ |X| \leq |\mathcal{L}|a<(\lfloor\sqrt{n-1}\rfloor+1)(\lfloor\sqrt{n-1}\rfloor+1)\leq (\sqrt{n-1}+1)^2=n-1+1+2\sqrt{n-1}=n+2\sqrt{n-1}$$ So $$n=|X| < n+2\sqrt{n-1}$$ $$0 < \sqrt{n-1}$$ which has solutions for $n>1$. The first proof seems fine to me so why it doesn't work in the second one?
You can reduce (2) to (1) by showing that if $|X| = n$, then $|X| > \bigl(\lfloor \sqrt{n - 1} \rfloor\bigr)^2$.
Indeed, for all $n \geq 1$, $$\bigl(\lfloor \sqrt{n - 1} \rfloor\bigr)^2 \leq (\sqrt{n-1})^2 = n - 1 < n.$$