So I think there is some really deep duality between chains and anti-chains in posets.
Green’s theorem says that if you look at how many more elements you can cover if you are allowed an extra chain, and you look at that same sequence for anti chains, then these form conjugate partitions, i.e. their corresponding young diagrams are flipped versions of one another.
Now, that sounds really deep. For today, we are definitely not going to prove that. But what we are going to prove is that the size of the largest anti-chain (which can be interpretted as the size of the first row in one of the young diagrams I was discussing) is the same as the minimum number of chains required to cover the poset (which can be interpreted as the size of the first columns in the other young diagram).
Here goes:
Theorem. max anti-chain size = min chain-cover size
Proof. We will prove the equality via establishing \(\leq, \geq\). One inequality is immediate: any cover of the poset with chains contains at least one chain per element in the max size anti-chain.
Now, we want to show that there is some chain-cover which has exactly one chain per element in a max anti-chain. We do so by induction.
Our inductive hypothesis is that for any poset \(P_0\) on \(n-1\) elements which has maximal anti-chain of size \(d\) there is a cover of \(P\) using \(d\) chains. Now we consider a poset \(P\) with \(n\) elements, and maximal anti-chain size of \(d\). We want to exhibit a chain cover of \(P\) with \(d\) chains.
First, we note that if there are any elements that are just completely incomparable to everything then we just win, because those certainly are involved in any anti-chain of maximal length. Assume this is not the case. Take \(m\) to be a minimal element, and \(M\) to be a maximal element, in particular a maximum element among elements which are comparable to (i.e. larger than) \(m\).
If \(P-\{m,M\}\) has maximal anti-chain of size \(d-1\) then we just win, by computing a chain cover of it with \(d-1\) chains and then adding \(\{m,M\}\) as the final chain. So, assume that this is not the case, i.e. that \(P-\{m,M\}\) has an anti-chain \(A\) with \(d\) elements. Now let \(P^+=\left\{ x\in P\; : \;\exists a\in A st x\ge a \right\},P^- = \left\{ x\in P\; : \;\exists a \in A st x\le a \right\}\) be the stuff below the anti-chain and the stuff above the anti-chain. Note that \(P^-\cap P^+ = A\) because if we had an element that was below \(a_1\in A\) while being above \(a_2\in A\) then \(a_1,a_2\) would be comparable, violating their anti-chain-ness! Furthermore, \(P^- \cup P^+ = P\) or we could build a longer anti-chain out of whatever element is incomparable to every element of the anti-chain. \(m\in P^-, M\in P^+\) because by construction \(m,M\notin A\) which means that \(P^+,P^-\) are strictly smaller than \(P\) and we can use the inductive hypothesis on them. This results in \(d\)-chain covers of \(P^+,P^-\). But of course we can glue these together via the anti-chain elements, yielding a \(d\)-chain cover of \(P\), as desired.