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 Bollobás (1965), Lubell (1966), Meshalkin (1963), and Yamamoto (1954). It is named for the initials of three of its discoverers.

This inequality belongs to the field of combinatorics of sets, and has many applications in combinatorics. In particular, it can be used to prove Sperner's theorem. Its name is also used for similar inequalities.

Statement of the theorem

Let U be an n-element set, 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}}}\leq 1.

Lubell's proof

Lubell (1966) proves the Lubell–Yamamoto–Meshalkin inequality by a double counting argument in which he counts the permutations of U in two different ways. First, by counting all permutations of U directly, one finds that there are n! of them. But secondly, one can generate a permutation (i.e., an order) of the elements of U by selecting a set S in A and concatenating a permutation of the elements of S with a permutation of the nonmembers (elements of U\S). If |S| = k, it will be associated in this way with k!(n − k)! permutations, and in each of them the first k elements will be just the elements of S. Each permutation can only be associated with a single set in A, for if two prefixes of a permutation both formed sets in A then one would be a subset of the other. Therefore, the number of permutations that can be generated by this procedure is

\sum _{{S\in A}}|S|!(n-|S|)!=\sum _{{k=0}}^{n}a_{k}k!(n-k)!.

Since this number is at most the total number of all permutations,

\sum _{{k=0}}^{n}a_{k}k!(n-k)!\leq n!.

Finally dividing the above inequality by n! leads to the result.

References

Bollobás, B. (1965), "On generalized graphs", Acta Mathematica Academiae Scientiarum Hungaricae, 16 (3–4): 447–452, doi:10.1007/BF01904851, MR 0183653 .

Lubell, D. (1966), "A short proof of Sperner's lemma", Journal of Combinatorial Theory, 1 (2): 299, doi:10.1016/S0021-9800(66)80035-2, MR 0194348 .

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 (2): 203–204, doi:10.1137/1108023, MR 0150049 .

Yamamoto, Koichi (1954), "Logarithmic order of free distributive lattice", Journal of the Mathematical Society of Japan, 6: 343–353, doi:10.2969/jmsj/00630343, MR 0067086 .

This article is issued from Wikipedia - version of the 11/20/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.