Question

To head off any confusion: I'm talking about the extremal-combinatorics Sperner's theorem, bounding the sizes of antichains in a Boolean lattice.

So the "canonical proof" of this theorem seems to be essentially Lubell's -- it's formulated in several different ways, but my favorite is this. Let $A$ be an antichain in $2^{[n]}$. Pick an arbitrary saturated chain and consider a random automorphism $\phi$ of the poset. Since $A$ is an antichain, so is the image $\phi(A)$, and the expected number of elements of $\phi(A)$ that lie in the distinguished chain is at most 1. Now if $S \subset [n]$ has k elements, then $\phi$ maps $S$ into our distinguished chain with probability $1/\binom{n}{k}$; linearity of expectation gives us the LYM inequality and Sperner's theorem follows.

This is a lovely proof, but reading over the DHJ polymath threads I heard about another approach -- apparently the approach Sperner himself used -- which one commenter described by the wonderful phrase "pushing shadows around." Evocative as this phrase is, I'm not actually sure what it means: presumably the idea is to replace an antichain by another antichain, at least as large and whose elements are "closer to the center?" This idea seems like it should work, but I can't quite get it to go through, which makes me think I'm missing something. Does anyone know the details of this proof?

Answer 1

Let $\mathcal{B}$ be a collection of $k$-sets , subsets of an $n$-set $S$. For $k < n$ define the shade of $\mathcal{B}$ to be $$\nabla \mathcal{B}=\{ D\subset S : |D|=k+1,\exists B\in \mathcal{B},B\subset D\}$$ and the shadow of $\mathcal{B}$ to be $$\Delta \mathcal{B}=\{ D\subset S : |D|=k-1,\exists B\in \mathcal{B},D\subset B\}$$ Sperner proved the lemma: $|\Delta \mathcal{B}|\geq \frac{k}{n-k+1}|\mathcal{B}|$ for $k > 0$, and $|\nabla \mathcal{B}|\geq \frac{n-k}{k+1}|\mathcal{B}|$ for $k < n$.

This implies that if $k\le \frac{1}{2}(n-1)$, then $|\nabla \mathcal{B}|\geq |\mathcal{B}|$ and if $k\geq\frac{1}{2}(n+1)$ then $|\Delta \mathcal{B}|\geq |\mathcal{B}|$. Now the proof proceeds in the obvious steps: Suppose we have an antichain $\mathcal{A}$, and it has $p_i$ elements of size $i$. If $i < \frac{1}{2}(n-1)$ then from the above we can substitute them with $p_i$ elements of size $i+1$. Similarly for the elements of size $i > \frac{1}{2}(n+1)$. You end up with an antichain of elements of size $\lfloor \frac{n}{2}\rfloor$ giving you the proof of Sperner's theorem.

I really enjoyed Combinatorics of finite sets by I. Anderson which treats Sperner's theorem, LYM, Erdos-Ko-Rado, Kruskal-Katona etc. The above is just a sketch but there you can find all the details.

Answer 2

Gjergji already provided the answer, but want to add a reference to an excellent book which contains more about Sperner's theorem than any other source: "Sperner Theory" by Konrad Engel. As the name suggests the book contains many different proofs of the the theorem, but a lot of other information that is hard to find in anywhere else: various generalizations, lots references to results that one would never even hear about otherwise, etc. It is from this book that I learned the argument in the question.