Lubell-Yamamoto-Meshalkin inequality

From Wikipedia, the free encyclopedia

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 Bollobás (1965), Lubell (1966), Meshalkin (1963), and 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}^n\frac{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$

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

[edit] References

Bollobás, B. (1965), “On generalized graphs”, Acta Math. Acad. Sci. Hungar., 16: 447–452 .

Lubell, D. (1966), “A short proof of Sperner's theorem”, Journal of Combinatorial Theory 1: 299 .

Meshalkin, L. D. (1963), “Generalization of Sperner's theorem on the number of subsets of a finite set”, Theory of Probability and its Applications 8: 203–204 .