combinatorial Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...

mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, the Lubell–Yamamoto–Meshalkin inequality, more commonly known as the LYM inequality, is an inequality on the sizes of sets in a

Sperner family In combinatorics, a Sperner family (or Sperner system; named in honor of Emanuel Sperner), or clutter, is a family ''F'' of subsets of a finite set ''E'' in which none of the sets contains another. Equivalently, a Sperner family is an antichain ...

, proved by , , , and . 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 Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...

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_^n\frac \le 1.

Lubell's proof

proves the Lubell–Yamamoto–Meshalkin inequality by a double counting argument in which he counts the

permutation In mathematics, a permutation of a set can mean one of two different things: * an arrangement of its members in a sequence or linear order, or * the act or process of changing the linear order of an ordered set. An example of the first mean ...

s of ''U'' in two different ways. First, by counting all permutations of ''U'' identified with 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 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 :

\sum_, S, !(n-, S, )!=\sum_^n a_k k! (n-k)!.

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

\sum_^n a_k k! (n-k)!\le n!.

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

References

* * * *{{citation , last = Yamamoto , first = Koichi , year = 1954 , title = Logarithmic order of free distributive lattice , journal = Journal of the Mathematical Society of Japan , volume = 6 , issue = 3–4 , pages = 343–353 , mr=0067086 , doi=10.2969/jmsj/00630343, doi-access = free . Combinatorics Inequalities (mathematics) Order theory Families of sets Articles containing proofs