Loading AI tools
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. To include the initials of all four discoverers, it is sometimes referred to as the YBLM inequality.
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.
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 ak denote the number of sets of size k in A. Then
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 identified with {1, …, n } 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 choosing a map that sends {1, … , |S | } to S. If |S | = k, the set S is associated in this way with k!(n − k)! permutations, and in each of them the image of the first k elements of U is exactly S. Each permutation may 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
Since this number is at most the total number of all permutations,
Finally dividing the above inequality by n! leads to the result.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.