Clarifications on proof of Sperner's Theorem

Question

Here I am considering a set $X$ with $|X| = n$ and it's power set $ \mathcal P(X)$.

Denote by $X^{(i)}$ the set of elements of $\mathcal P(X)$ with $i$ elements, and consider $\mathcal P(X)$ as a poset ordered by $A < B \Leftrightarrow A \subset B$.

Then in my lecture notes, we have Sperner's Theorem saying the largest size of an anti-chain in $\mathcal P(X)$ is $\binom{n}{\lfloor n/2 \rfloor}$, witnessed by $X^{(\lfloor n/2 \rfloor)}$.

Then, to prove this: on realising that for any chain $C$ and anti-chain $A$ of $\mathcal P(X)$ we have that $|C \cap A| \leq 1$, my notes say that: "it is sufficient to partition $\mathcal P(X)$ into $\binom{n}{\lfloor n/2 \rfloor}$ chains".

I understand that on partitioning $\mathcal P(X)$ into this many chains, then we have that an anti-chain can have at most one non-trivial intersection with each of them. Further, we may notice (with appropriately chosen chains) that $X^{\lfloor n/2 \rfloor}$ is indeed a witness to the case of an antichain of size $\binom{n}{\lfloor n/2 \rfloor}$. Together this tells us the maximal anti-chain size is at least $\binom{n}{\lfloor n/2 \rfloor}.$

Why then do we now know there can't be an anti chain that is longer? From what I can tell this proof has given us the wrong bound (lower instead of upper) on the size of the largest possible anti-chain. I expect that I have misunderstood something crucial here, or missed an assumed result, and I would be very grateful if you could point it out to me.

I apologise if I haven't been clear enough here. I have understood what I said here but likely only because I have my lecture notes in front of me. If there is something worth clarifying please let me know.

In case it is important: the method by which we construct the $\binom{n}{\lfloor n/2 \rfloor}$ chains is by using complete matchings from either $X^{(i-1)}$ to $X^{(i)}$ or from $X^{(i)}$ to $X^{(i-1)}$ (order depending on the size of $i$) by viewing $(X^{(i)},X^{(i-1)})$ as a biregular, bipartite graph.

Answer 1

You have chains $C_1,\ldots,C_m$ where $m=\binom{n}{[n/2]}$. Each element of $\mathcal P(X)$ is in exactly one $C_j$. So each element of an antichain $\cal A$ has at most one element in each $C_j$, but each element of $\cal A$ is in some $C_j$, so there are at most $m$ elements in $\cal A$.

I prefer the proof from the LYM inequality....

Answer 2

On the one hand, you have $\cal{P}$ partitioned into $m= {{n} \choose {\lceil \frac{n}{2}\rceil}}$ chains via the proof in the later part of your post @user, which gives the upper bound of $m$ on the size of the largest antichain.

On the other hand, you have been given an explicit antichain with precisely $m$ elements--namely all subsets of $[n]$ with precisely $\lceil \frac{n}{2} \rceil$ elements, this gives the lower bound of $m$ on the size of the largest antichain.

If both the upper bound and the lower bound on the size of the largest antichain is $m$, then it follows that the size of the largest antichain must indeed be $m$.