The Lubell-Yamamoto-Meshalkin Inequality

The Lubell-Yamamoto-Meshalkin Inequality

Recall from the Antichains of Subsets of a Set page that if $A$ is an $n$-element set then a collection of subsets $B_1, B_2, ..., B_k$ of $A$ is said to be an antichain if for all $i, j \in \{1, 2, ..., k \}$ where $i \neq j$ we have that $B_i \not \subset B_j$ and $B_i \not \supset B_j$. In other words, none of the subsets in this collection are contained in one another.

For a finite set $n$-element set $A$ we are about to see that every collection $B$ of subsets of $A$ that is an antichain will have at most $\binom{n}{\left \lfloor \frac{n}{2} \right \rfloor}$ subsets of $A$, that is $\lvert B \rvert \leq \binom{n}{\left \lfloor \frac{n}{2} \right \rfloor}$ - this result famously known as Sperner's Antichain Theorem. We will first look at the very important Lubell-Yamamoto-Meshalkin inequality (LYM inequality) that we will use to prove Sperner's Theorem.

 Lemma 1 (The Lubell-Yamamoto-Meshalkin Inequality): Let $A$ be a finite $n$-element set, let $B$ be a collection of subsets of $A$ that form an antichain, and let $a_k$ for $k \in \{ 0, 1, 2, ..., n \}$ be the number of subsets of $A$ of size $k$ in $B$. Then $\displaystyle{\sum_{k=0}^{n} \frac{a_k}{\binom{n}{k}} \leq 1}$.
• Proof: Let $A$ be a finite $n$-element set. As we already know, the number of $n$-permutations of elements from $A$ is $n \cdot (n - 1) \cdot ... \cdot 2 \cdot 1 = n!$. Consider a subset $B \subset A$ where $\lvert B \rvert = k$. The number of permutations of the elements in $B$ is therefore $k \cdot (k - 1) \cdot ... \cdot 2 \cdot 1 = k!$. Furthermore, the number of elements in the subset $A \setminus B = \{ x \in A \: \mathrm{and} \: x \not \in B \}$ will be $n - k$ and the number of permutations in $A \setminus B$ is therefore $(n - k)\cdot (n - k - 1) \cdot ... \cdot 2 \cdot 1 = (n - k)!$. For each subset $B$ we can concatenate the $k$-permutations of $B$ with the $(n - k)$-permutations of $A \setminus B$. Thus by the multiplication principle there will be $k! \cdot (n - k)!$ many $n$-permutations for each subset $B$ of $A$.
• Now, each of these $n$-permutations is associated with only one subset in $A$ and the number of all of these concatenated $n$-permutations is less than or equal to the total number of $n$-permutations of elements from $A$ so:
(1)
\begin{align} \quad \sum_{B \subset A} \lvert B \rvert (n - \lvert B \rvert)! \leq n! \\ \quad \sum_{k=0}^{n} a_k \cdot k! (n - k)! \leq n! \\ \quad \sum_{k=0}^{n} \frac{a_k \cdot k! (n - k)!}{n!} \leq 1 \\ \quad \sum_{k=0}^{n} \frac{a_k}{\binom{n}{k}} \leq 1 \quad \blacksquare \end{align}