Generalized linear model

2014-01-12T11:19:33Z

2001:4CA0:4E01:0:20F:FEFF:FE5F:B33E: /* Link function */

In [[combinatorics|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 {{harvtxt|Bollobás|1965}}, {{harvtxt|Lubell|1966}}, {{harvtxt|Meshalkin|1963}}, and {{harvtxt|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<sub>k</sub>'' denote the number of sets of size ''k'' in ''A''. Then
: <math>\sum_{k=0}^n\frac{a_k}{{n \choose k}} \le 1.</math>

==Lubell's proof==
{{harvtxt|Lubell|1966}} proves the Lubell–Yamamoto–Meshalkin inequality by a [[double counting (proof technique)|double counting argument]] in which he counts the [[permutation]]s 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 of ''U'' by selecting a set ''S'' in ''A'' and concatenating a permutation of the elements of ''S'' with a permutation of the nonmembers. If |''S''| = ''k'', it will be associated in this way with ''k''!(''n'' − ''k'')! permutations.
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
:<math>\sum_{S\in A}|S|!(n-|S|)!=\sum_{k=0}^n a_k k! (n-k)!.</math>
Since this number is at most the total number of all permutations,
:<math>\sum_{k=0}^n a_k k! (n-k)!\le n!.</math>
Finally dividing the above inequality by ''n''! leads to the result.

== References ==

*{{citation
| first = B. | last = Bollobás | authorlink = Béla Bollobás
| title = On generalized graphs
| journal = Acta Mathematica Academiae Scientiarum Hungaricae
| volume = 16 | issue = 3–4 | pages = 447–452 | year = 1965
| doi = 10.1007/BF01904851 |mr=0183653 }}.

*{{citation
| last = Lubell | first = D.
| year = 1966
| title = A short proof of Sperner's lemma
| journal = Journal of Combinatorial Theory
| volume = 1 | issue = 2 | pages = 299
| doi = 10.1016/S0021-9800(66)80035-2 |mr=0194348 }}.

*{{citation
| last = Meshalkin | first = L. D.
| year = 1963
| title = Generalization of Sperner's theorem on the number of subsets of a finite set
| journal = Theory of Probability and its Applications
| volume = 8 | issue = 2 | pages = 203–204
| doi = 10.1137/1108023 |mr=0150049 }}.

*{{citation
| last = Yamamoto | first = Koichi
| year = 1954
| title = Logarithmic order of free distributive lattice
| journal = Journal of the Mathematical Society of Japan
| volume = 6 | pages = 343–353
|mr=0067086 }}.

{{DEFAULTSORT:Lubell-Yamamoto-Meshalkin inequality}}
[[Category:Combinatorics]]
[[Category:Inequalities]]
[[Category:Order theory]]
[[Category:Set families]]
[[Category:Articles containing proofs]]

formulasearchengine - User contributions [en]

Generalized linear model