Lubell-Yamamoto-Meshalkin inequality

In combinatorial mathematics, the Lubell-Yamamoto-Meshalkin inequality, more commonly known as the LYM inequality, is an inequality on the sizes of sets in a Sperner family, proved by harvtxt|Bollobás|1965, harvtxt|Lubell|1966, harvtxt|Meshalkin|1963, and harvtxt|Yamamoto|1954. It is named for the initials of three of its discoverers.

The term is also used for similar inequalities.

Theorem.Let "U" be a set of "n" items, let "A" be a family of subsets of "U" such that no set in "A" is a subset of another set in "A", and let "a_k" denote the number of sets of size "k" in "A". Then: $sum\_\{k=0\}^nfrac\{a\_k\}$n choose k le 1.

"Proof". (Lubell 1966)We consider the powerset of "U" as a lattice, partially ordered by the subset relationship; in order-theoretic terminology, "A" is an antichain in this lattice. Consider an element "K" of "A", with "|K| = k". There are exactly "k!(n-k)!" maximal chains that contain "K", as we can start from the empty set and get to "K" by adding one element at a time in "k!" ways, and then we complete the maximal chain by adding in the other "n-k" elements one at a time.

This method counts maximal chains, and we never count the same maximal chain twice, for if the same chain was counted from two sets "K" and "L" then it means that either "K" ⊆ "L" or "L" ⊆ "K", either of which contradicts the fact that both sets are part of an antichain. As the number of chains counted by this method cannot exceed "n!", the total number of maximal chains, we have

: $sum\_\{K\; in\; A\}\; k!\; (n-k)!\; =\; sum\_\{k=0\}^n\; a\_k\; k!\; (n-k)!\; le\; n!.$

Finally we divide the above inequality by "n"! to obtain the result. $Box$

"Alternative Proof".Let us enumerate the elements of "U", $u\_i$ for $1le\; ile\; n$. Now, let us pick a uniform random permutation $sigma\_1,\; ldots,\; sigma\_n$ of the elements "1", ..., "n", and consider the probability that for some "k", $S\_k=\{u\_\{sigma\_1\},ldots,u\_\{sigma\_k\}\}$ is in "A".

For "iS_i is a subset of $S\_j$, and hence they cannot both be elements of "A". Thus $S\_k$ can be an element of "A" for at most one value of "k". Thus the probability that there exists a "k" such that $S\_k$ is in "A" is equal to the sum, for $0le\; kle\; n$, of the probability that $S\_k$ is in "A".

Since $S\_k$ is uniformly chosen from the subsets of "U" of size "k", the probability that $S\_k$ is in "A" is precisely $frac\{a\_k\}$n choose k. Thus the left hand side of the inequality in the statement is equal to the probability that there exists a "k" such that "S_k" is in $A$, so it (like all probabilities) cannot be greater than 1. $Box$

Let us randomly pick the elements of "U", one by one, without replacement, until we have picked them all. Consider the probability that at some point we have picked precisely the elements of some member of "A".

Clearly, since no set in "A" is a subset of another set in "A", it is not possible to have pi

This inequality has many applications in combinatorics; in particular, it can be used to prove Sperner's theorem.

References

*citation
first = B. | last = Bollobás | authorlink = Béla Bollobás
title = On generalized graphs
journal = Acta Math. Acad. Sci. Hungar.,
volume = 16 | pages = 447–452 | year = 1965.

*citation
last = Lubell | first = D.
year = 1966
title = A short proof of Sperner's theorem
journal = Journal of Combinatorial Theory
volume = 1 | pages = 299.

*citation
last = Meshalkin | first = L. D.
year = 1963
title = Generalization of Sperner's theorem on the number of subsets of a finite set
journal = Theory of Probability and its Applications
volume = 8 | pages = 203–204.

*citation
last = Yamamoto | first = Koichi
year = 1954
title = Logarithmic order of free distributive lattice
journal = Journal of the Mathematical Society of Japan
volume = 6 | pages = 343–353.