Definition 2.2.1.
A chain \(\mathcal{C}\subseteq 2^{[n]}\) is maximal if there is no chain \(\mathcal{C}'\) such that
\begin{equation*}
\mathcal{C}\subsetneq \mathcal{C}'\subseteq 2^{[n]}\text{.}
\end{equation*}
Section 2.2 The LYM Inequalities
We now explore some strengthenings of Sperner’s Theorem known as the LYM Inequality and the Local LYM Inequality; first, a definition.
“Chain.”
Since each chain can contain at most one element of \(\binom{[n]}{k}\) for each \(k\) (by Example 2.1.4 and Observation 2.1.11), we can equivalently say that a chain is maximal if it has \(n+1\) elements, one of each cardinality between \(0\) and \(n\text{.}\)
Theorem 2.2.3. The LYM Inequality [208, 295, 216, 39].
If \(\mathcal{A}\subseteq 2^{[n]}\) is an antichain, then
\begin{equation*}
\sum_{A\in\mathcal{A}}\frac{1}{\binom{n}{|A|}}\leq 1\text{.}
\end{equation*}
Proof.
Let \(\mathcal{C}\) be a maximal chain in \(2^{[n]}\) selected uniformly at random among all such chains. For each \(A\in 2^{[n]}\text{,}\) let \(1_A\) be the indicator function of the event that \(A\in\mathcal{C}\text{;}\) that is,
\begin{equation*}
1_A=\begin{cases}1\amp \text{ if } A\in\mathcal{C},\\ 0 \amp \text{ otherwise } . \end{cases}
\end{equation*}
Let \(\mathcal{A}\) be an antichain. For any choice of \(\mathcal{C}\text{,}\) we have
\begin{equation*}
\sum_{A\in \mathcal{A}}1_A = |\mathcal{A}\cap \mathcal{C}|\leq 1
\end{equation*}
by Observation 2.1.11. Therefore, if we take the expectation of both sides, then we get, by linearity of expectation (see Appendix B),
\begin{equation*}
1\geq \mathbb{E}\left(\sum_{A\in \mathcal{A}}1_A\right) = \sum_{A\in \mathcal{A}}\mathbb{E}(1_A) = \sum_{A\in \mathcal{A}}\mathbb{P}(A\in\mathcal{C})\text{.}
\end{equation*}
Now, for any \(0\leq k\leq n\text{,}\) the chain \(\mathcal{C}\) contains exactly one element of \(\binom{[n]}{k}\text{,}\) and any such set is equally likely to be contained in \(\mathcal{C}\text{,}\) by symmetry. Therefore, for any \(A\subseteq [n]\text{,}\) it holds that
\begin{equation*}
\mathbb{P}(A\in\mathcal{C}) = \frac{1}{\binom{n}{|A|}}\text{.}
\end{equation*}
Putting these inequalities together completes the proof.
Observe that the LYM Inequality is tight when \(\mathcal{A}=\binom{[n]}{k}\) for some \(k\text{.}\) One way to think about the LYM Inequality is to view each subset \(A\) of \([n]\) as being associated to a “cost” of \(\binom{n}{|A|}^{-1}\text{.}\) The LYM Inequality says that, for any antichain, the total cost of the elements within it must be at most one. Note that, since \(\binom{n}{k}\) is maximized when \(k\) is \(\lfloor n/2\rfloor\text{,}\) the sets of lowest cost are those of size \(\lfloor n/2\rfloor\text{.}\) From this, it is easily observed that no antichain can have more than \(\binom{n}{\lfloor n/2\rfloor}\) elements, and so the LYM Inequality implies Sperner’s Theorem.
Sperner’s Theorem can be equivalently thought of as a bound on the size of a family which does not contain a chain of cardinality two. In the same way as above, the LYM Inequality can also be used to determine the maximum size of a family in \(2^{[n]}\) that does not contain a longer chain.
Corollary 2.2.4. Erdős [85].
For \(2\leq k\leq n\text{,}\) if \(\mathcal{F}\subseteq 2^{[n]}\) such that \(\mathcal{F}\) does not contain a chain with \(k\) elements, then \(|\mathcal{F}|\) is bounded above by the sum of the \(k-1\) largest binomial coefficients \(\binom{n}{m}\text{.}\)
Proof.
Next, we apply the LYM Inequality to obtain a result on the “expansion” of a family of sets on the \(k\)th level of \(2^{[n]}\text{,}\) known as the Local LYM Inequality; first, a definition.
Definition 2.2.5.
The shadow of a family \(\mathcal{F}\subseteq \binom{[n]}{k}\) is defined to be
\begin{equation*}
\partial\mathcal{F}:=\{B: |B|=k-1\text{ and there exists } A\in\mathcal{F}\text{ such that } B\subseteq A\}\text{.}
\end{equation*}
Corollary 2.2.7. The Local LYM Inequality.
For \(1\leq k\leq n\text{,}\) if \(\mathcal{F}\subseteq \binom{[n]}{k}\text{,}\) then
\begin{equation*}
\frac{|\partial \mathcal{F}|}{\binom{n}{k-1}}\geq \frac{|\mathcal{F}|}{\binom{n}{k}}\text{.}
\end{equation*}
Proof.
Define
\begin{equation*}
\mathcal{A} := \mathcal{F} \cup \left(\binom{[n]}{k-1}\setminus \partial\mathcal{F}\right)\text{.}
\end{equation*}
Then \(\mathcal{A}\) is clearly an antichain (do you see why?). Therefore, by the LYM Inequality,
\begin{equation*}
\sum_{A\in\mathcal{A}}\frac{1}{\binom{n}{|A|}} = \frac{|\mathcal{F}|}{\binom{n}{k}} + \frac{\binom{n}{k-1}-|\partial \mathcal{F}|}{\binom{n}{k-1}} \leq 1
\end{equation*}
and we are done after a bit of rearranging.
Here are a few YouTube videos related to the LYM Inequalities:
