Lubell-Yamamoto-Meshalkin inequality
|
|
In combinatorial mathematics, the Lubell-Yamamoto-Meshalkin inequality, more commonly known as the LYM inequality, is an inequality proved by Lubell (1966), Yamamoto (1954), and Meshalkin (1963).
The term is also used for similar inequalities.
Theorem. Let ak denote the number of k-sets in an antichain of the inclusion lattice over the power set of an n-set. Then
- <math>\sum_{k=0}^n\frac{a_k}{{n \choose k}} \le 1.<math>
Proof (Lubell 1966). Every maximal chain in the power set ordered by inclusion meets an antichain in at most one element, say, a k-set. For i = k to 1, there are i choices of an (i − 1)-set out of each i-set chosen previously. Thus, in total, this k-set is contained in k! chains of subsets. Likewise, for i = k to n − 1, there are n − i choices of an (i + 1)-set on top of each i-set chosen previously. Thus, in total, it is contained in (n − k)! chains of supersets. So each of ak k-sets meets k! (n − k)! maximal chains. Counting the number of maximal chains meeting k-sets of all possible sizes from 0 to n, we obtain at most ∑ ak k! (n − k)! maximal chains meeting the antichain. The actual number cannot be greater than n! as the latter is the maximum number of all possible maximal chains. Therefore,
- <math>\sum_{k=0}^n a_k k! (n-k)! \le n!.<math>
Finally we divide the above inequality by n! to obtain the result. <math>\Box<math>
This inequality has many applications in combinatorics.
References
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-4.
Yamamoto, Koichi (1954). Logarithmic order of free distributive lattice, Journal of the Mathematical Society of Japan, 6, 343-53.