The Lubell-Yamamoto-Meshalkin Inequality

Table of Contents

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$

$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}

Mathonline

Learn Mathematics

The Lubell-Yamamoto-Meshalkin Inequality