Lubell–Yamamoto–Meshalkin inequality

The Lubell - Yamamoto - Meshalkin inequality or short LYM inequality is a result of discrete mathematics. She is most closely with the well-known theorem of Sperner (1905 - 1980) linked, they even generalized. Just like this, it is also in the LYM inequality to the representation of the relationship between the anti- chains of finite power sets and the binomial coefficients.

The inequality is Lubell (1966 ), Yamamoto (1954) and Meshalkin (1963 ) attributed what they found independently. However, it must be mentioned for the correct historical context that the Hungarian mathematician Béla Bollobás in 1965 - about the same time Lubell and Meshalkin - has published a very similar inequality. In fact, the inequality of Bollobás is even more generally compared to the LYM inequality.

In this context, it is worth noting that Emanuel Sperner used himself in his 1928 article he as key talking points and two inequalities proves, of which it has been proved that they in turn are logically equivalent to the LYM inequality.

Together with the set of Sperner form said inequalities a significant starting point for the development of the so-called Spernertheorie. This has emerged in recent decades become a separate branch of discrete mathematics. As part of this development has been particularly shown that the Lubell - Yamamoto - Meshalkin inequality can also be interpreted as a consequence of a general identity, the so-called Ahlswede - Zhang identity.

  • 3.1 Articles and papers
  • 3.2 monographs

The inequalities

The LYM inequality

Given a finite set of items where a natural number is, and a further quantity of subsets of which are pairwise not contain one another, so form an anti- chain of the power set.

Next is the number of occurring in quantities with exact elements. Then:

The Sperner's theorem is obtained from the LYM inequality by multiplying both sides of the inequality with the largest binomial coefficients and involving that the sum is equal to the number of is occurring levels.

The inequality of Bollobás

Given two finite sequences of finite sets and which satisfy the following two requirements:

Then:

The LYM inequality is obtained from the inequality of Bollobás, by counting off in the form

And then sets for each.

The two inequalities Spernerschen

Given a finite set of items where a natural number is, and also a lot of subsets of, which all have the same cardinality.

Furthermore, let the quantity system of those subsets such that for one and also and is the quantity system of those subsets such that for one and also.

Then the following two inequalities hold:

The Ahlswede - Zhang identity

This identity (also called AZ- identity, in the English literature as AZ identity called ) goes to the two mathematicians Rudolf Ahlswede - back and Zhen Zhang (1938, 2010 ). It represents a tightening of the LYM inequality and can be formulated as follows:

Given a finite set with elements () and to a non-empty class of sets of non-empty subsets of, ie a non-empty subset of the reduced power set. Next was for:

Then:

Is an anti- chain and so is. So is contained in the above sum, which shows that the AZ identity the LYM inequality implies immediately.

Swell

Articles and papers

  • R. Ahlswede; Z. Zhang: An identity in combinatorial extremal theory. In: Advances in Mathematics. 80, 1990, pp. 137- 151.MR1046687
  • R. Ahlswede; N. Cai: A generalization of the AZ identity. In: Combinatorica. 13, 1993, pp. 241-247. MR1238819
  • Béla Bollobás: On generalized graphs. In: Acta Mathematica Academiae Scientiarum Hungaricae. 16, 1965, pp. 447-452. doi: 10.1007/BF01904851, MR0183653
  • Curtis Greene and Daniel J. Kleitman: Proof techniques in the theory of finite sets in: GC Rota ( ed.): Studies in Combinatorics. Mathematical Association of America, Washington, DC, 1978, ISBN 0-88385-117-2, pp. 23-79. MR0513002
  • DJ Kleitman: On an extremal property of anti- chains in partial orders. The LYM property and some of its implications and applications in: M. Hall and JH van Lint (eds. ): Combinatorics ( Math Centre Tracts 55). Amsterdam 1974, pp. 77-90. MR0360379
  • D. Lubell: A short proof of Sperner 's lemma. In: Journal of Combinatorial Theory. 1, 1966, pp. 299, doi: 10.1016/S0021-9800 (66 ) 80035-2, MR0194348
  • L. D. Meshalkin: Generalization of Sperner 's theorem on the number of subsets of a finite set. In: Theory of Probability and its Applications. 8, 1963, pp. 203-204.
  • Hans -Josef Scholz: On the combinatorics of finite power sets associated with the set of Sperner. Dissertation, University of Dusseldorf (1987).
  • Emanuel Sperner: A theorem on subsets of a finite set. In: Math Z. 27, 1928, pp. 544-548. MR1544925
  • Koichi Yamamoto: Logarithmic order of free distributive lattice. In: Journal of the Mathematical Society of Japan. 6, 1954, pp. 343-353. MR0067086
  • Douglas B. West: Extremal problems in Partially ordered sets: Ivan Rival (ed. ): Ordered sets. Proceedings of the NATO advanced study institute held at Banff, Canada, August 28 to September 12, 1981 d. Reidel Publishing Company, Dordrecht [ua ] 1982, ISBN 90-277-1396-0, pp. 473-521. MR0661304

Monographs

  • Martin Aigner: Combinatorics II: matroids and Transversaltheorie ( = high school text). Springer Verlag, Berlin ( and others) 1976, ISBN 3-540-07949-1. MR0460127
  • Martin Aigner: Combinatorial Theory ( = basic teachings of Mathematical Sciences 234. ). Springer Verlag, Berlin (including ) 1979, ISBN 3-540-90376-3. MR0542445
  • Martin Aigner: Discrete Mathematics ( = documents the history of mathematics 6. ). 6th edition. Vieweg Verlag, Wiesbaden 2006, ISBN 978-3-8348-0084-8. MR1085963
  • Ian Anderson: Combinatorics of Finite Sets. Clarendon Press, Oxford, 1987, ISBN 0-19-853367-5. MR0892525
  • Konrad Engel: Sperner Theory ( Encyclopedia of Mathematics and = its Applications 65. ). Cambridge University Press, Cambridge ( and others) 1997, ISBN 0-521-45206-6. MR1429390
  • Egbert Harzheim: Ordered Sets ( Advances in Mathematics = 7. ). Springer Verlag, New York, NY 2005, ISBN 0-387-24219-8. MR2127991
  • Stasys Jukna: Extremal Combinatorics ( = Texts in Theoretical Computer Science). Springer Verlag, Heidelberg ( and others) 2011, ISBN 978-3-642-17363-9. MR2865719
  • Joseph PS Kung, Gian- Carlo Rota, Catherine H. Yan: Combinatorics: The Rota Way. Cambridge University Press, Cambridge ( and Others ) 2009, ISBN 978-0-521-73794-4. MR2483561
Antichain Digital Object Identifier Daniel Kleitman Mathematische Zeitschrift Oxford University Press Gian-Carlo Rota
35626
de