Lubell-Yamamoto-Meshalkin inequality

The Lubell-Yamamoto-Meshalkin inequality or LYM inequality for short is a result of discrete mathematics . It is closely linked to the well-known Sperner theorem (after Emanuel Sperner , 1905–1980), which it even generalizes. As with this, the LYM inequality is also about the representation of the relationship between the anti-chains of finite power sets and the binomial coefficients .

The inequality is the three mathematicians L Ubell (1966), Y amamoto (1954) and M eshalkin attributed (1963), which found it independently. For a correct historical classification, however, it must be mentioned that the Hungarian mathematician Béla Bollobás published a very similar inequality in 1965 - around the same time as Lubell and Meshalkin. In fact, when compared to the LYM inequality, Bollobás 's inequality is even more general.

In this context it is worth mentioning that Emanuel Sperner himself uses two inequalities as an essential argumentation aid in his article in 1928 and proves which have been shown to be logically equivalent to the LYM inequality.

Together with Sperner's theorem, the mentioned inequalities form an essential starting point for the development of the so-called Sperner's theory. This has developed into a separate branch of discrete mathematics in the last few decades . In the context of this development, it was found in particular that the Lubell-Yamamoto-Meshalkin inequality can also be understood as a consequence of a general identity , the so-called Ahlswede-Zhang identity .

The inequalities

The LYM inequality

A finite set     with   elements is given , where     a natural number is given, and further a set system   of subsets of which are not contained in each other in pairs, i.e.   form an anti-chain of the power set . ${\displaystyle X}$ ${\displaystyle n}$   ${\displaystyle n}$   ${\displaystyle {\mathcal {A}}}$ ${\displaystyle X}$   ${\displaystyle {\mathcal {P}}(X)}$

Next, let     the number of     sets with exactly     elements occur in. Then: ${\displaystyle i=0,\dots ,n}$   ${\displaystyle {a_{i}}}$ ${\displaystyle {\mathcal {A}}}$ ${\displaystyle i}$

${\displaystyle {\sum _{i=0}^{n}{\frac {a_{i}}{\binom {n}{i}}}}\leq 1}$

The set of Sperner is obtained from the LYM inequality by on both sides of the inequality with the largest binomial coefficients     multiplied and involves that the total     equals the number of in     is occurring levels. ${\displaystyle {\tbinom {n}{\lfloor {n/2}\rfloor }}}$ ${\displaystyle {a_{i}}}$ ${\displaystyle {\mathcal {A}}}$

Bollobás's inequality

Given are two finite sequences of finite sets     and     which satisfy the following two rules: ${\displaystyle (A_{1},\dots ,A_{M})}$ ${\displaystyle (B_{1},\dots ,B_{M})}$

1. ${\displaystyle A_{J}\cap B_{J}=\emptyset }$( ) ${\displaystyle J=1,\dots ,M}$
2. ${\displaystyle A_{J}\cap B_{K}\neq \emptyset }$(  ; ) ${\displaystyle J,K=1,\dots ,M}$ ${\displaystyle J\neq K}$

Then:

${\displaystyle {\sum _{J=1}^{M}{\frac {1}{\binom {|A_{J}|+|B_{J}|}{|A_{J}|}}}}\leq 1.}$

The LYM inequality is obtained from Bollobás's inequality by     counting in the form ${\displaystyle {\mathcal {A}}}$

${\displaystyle {\mathcal {A}}=\{A_{1},\dots ,A_{M}\}}$( ) ${\displaystyle M=|{\mathcal {A}}|}$

and then for     each     sets. ${\displaystyle J=1,\dots ,M}$ ${\displaystyle B_{J}=X\setminus A_{J}}$

The two Sperner's inequalities

Let a finite set     with   elements be given , with     a natural number, and also a set system     of subsets of     , which all have the same cardinality   . ${\displaystyle X}$ ${\displaystyle n}$   ${\displaystyle n}$ ${\displaystyle {\mathcal {T}}}$ ${\displaystyle X}$   ${\displaystyle k\leq n}$

Furthermore, let     the set system of those subsets be     such that for one     and more     is and be     the set system of those subsets   such that is for one     and more     . ${\displaystyle \Delta {\mathcal {T}}}$ ${\displaystyle A\subseteq X}$ ${\displaystyle T\in {\mathcal {T}}}$   ${\displaystyle A\subset T}$ ${\displaystyle |T\setminus A|=1}$ ${\displaystyle \nabla {\mathcal {T}}}$   ${\displaystyle A\subseteq X}$ ${\displaystyle T\in {\mathcal {T}}}$   ${\displaystyle A\supset T}$ ${\displaystyle |A\setminus T|=1}$

Then the following two inequalities hold :

First Sperner's inequality

${\displaystyle |\Delta {\mathcal {T}}|\geq {\frac {k}{n-k+1}}\cdot |{\mathcal {T}}|}$

Second Sperner's inequality

${\displaystyle |\nabla {\mathcal {T}}|\geq {\frac {n-k}{k+1}}\cdot |{\mathcal {T}}|}$

The Ahlswede-Zhang identity

This identity (including AZ identity called in the English literature as AZ identity called) goes to the two mathematicians Rudolf A hlswede (1938-2010) and Zhen Z hang back. It represents a tightening of the LYM inequality and can be formulated as follows:

Given a finite set     with     elements (   ) and a non-empty set system     of non-empty subsets of , i.e. a non-empty subset of the reduced power set   . Further be for     : ${\displaystyle M}$ ${\displaystyle n}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle {\mathcal {A}}\neq \emptyset }$ ${\displaystyle M}$ ${\displaystyle {\mathcal {P}}(M)\setminus \{\emptyset \}}$ ${\displaystyle X\subseteq M}$

${\displaystyle D_{\mathcal {A}}(X)={\begin{cases}\ \;\,\bigcap \{A\mid A\in {\mathcal {A}}\land A\subseteq X\}&\exists A\in {\mathcal {A}}:A\subseteq X\\\ \;\,\emptyset &\mathrm {sonst} \end{cases}}}$

Then:

${\displaystyle \sum _{\emptyset \neq X\subseteq M}{\frac {|D_{\mathcal {A}}(X)|}{|X|\cdot {\binom {n}{|X|}}}}=1}$

Is     an anti-chain of and     , so is   . So is included     in the above sum, which shows that the AZ identity directly implies the LYM inequality . ${\displaystyle {\mathcal {A}}}$ ${\displaystyle {\mathcal {P}}(X)}$ ${\displaystyle A\in {\mathcal {A}}}$ ${\displaystyle D_{\mathcal {A}}(A)=A}$ ${\displaystyle \sum _{A\in {\mathcal {A}}}{\frac {1}{\binom {n}{|A|}}}=\sum _{A\in {\mathcal {A}}}{\frac {|A|}{|A|\cdot {\binom {n}{|A|}}}}}$

swell

Articles and original works

• R. Ahlswede; Z. Zhang: An identity in combinatorial extremal theory . In: Advances in Mathematics . tape 80 , 1990, pp. 137-151 ( ams.org ).

• R. Ahlswede; N. Cai: A generalization of the AZ identity . In: Combinatorica . tape 13 , 1993, pp. 241-247 ( ams.org ).

• Béla Bollobás : On generalized graphs . In: Acta Mathematica Academiae Scientiarum Hungaricae . tape 16 , 1965, pp. 447-452 , doi : 10.1007 / BF01904851 ( ams.org ).

• 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 ( ams.org ).

• DJ Kleitman: On an extremal property of antichains in partial orders. The LYM property and some of its implications and applications in: M. Hall and JH van Lint (eds.): Combinatorics (Math. Center Tracts 55) . Amsterdam 1974, p. 77-90 ( ams.org ).

• D. Lubell: A short proof of Sperner's lemma . In: Journal of Combinatorial Theory . tape 1 , 1966, p. 299 , doi : 10.1016 / S0021-9800 (66) 80035-2 ( ams.org ).

• LD Meshalkin: Generalization of Sperner's theorem on the number of subsets of a finite set . In: Theory of Probability and its Applications . tape 8 , 1963, pp. 203-204 .

• Hans-Josef Scholz: About the combinatorics of finite power sets in connection with Sperner's theorem . Dissertation, University of Düsseldorf (1987).

• Emanuel Sperner : A theorem about subsets of a finite set . In: Math. Z . tape 27 , 1928, pp. 544-548 ( ams.org ).

• Koichi Yamamoto: Logarithmic order of free distributive lattice . In: Journal of the Mathematical Society of Japan . tape 6 , 1954, pp. 343-353 ( ams.org ).

• Douglas B. West: Extremal problems in partially ordered sets in: 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 [et al. a.] 1982, ISBN 90-277-1396-0 , pp. 473-521 ( ams.org ).

Monographs

• Martin Aigner : Combinatorics II: Matroids and transversal theory (=  university text ). Springer Verlag , Berlin (inter alia) 1976, ISBN 3-540-07949-1 .

• Martin Aigner: Combinatorial Theory (=  Basic Teachings of Mathematical Sciences . Volume 234 ). Springer Verlag , Berlin (inter alia) 1979, ISBN 3-540-90376-3 ( ams.org ).

• Martin Aigner: Discrete Mathematics (=  documents on the history of mathematics . Volume 6 ). 6th edition. Vieweg Verlag , Wiesbaden 2006, ISBN 978-3-8348-0084-8 .

• Ian Anderson: Combinatorics of Finite Sets . Clarendon Press , Oxford 1987, ISBN 0-19-853367-5 ( ams.org ).

• Konrad Engel : Sperner Theory (=  Encyclopedia of Mathematics and its Applications . Volume 65 ). Cambridge University Press , Cambridge (et al.) 1997, ISBN 0-521-45206-6 ( ams.org ).

• Egbert Harzheim : Ordered Sets (=  Advances in Mathematics . Volume 7 ). Springer Verlag , New York, NY 2005, ISBN 0-387-24219-8 ( ams.org ).

• Stasys Jukna: Extremal Combinatorics (=  Texts in Theoretical Computer Science ). 2nd Edition. Springer Verlag , Heidelberg (inter alia) 2011, ISBN 978-3-642-17363-9 ( ams.org ).

• Joseph PS Kung, Gian-Carlo Rota , Catherine H. Yan: Combinatorics: The Rota Way . Cambridge University Press, Cambridge (et al.) 2009, ISBN 978-0-521-73794-4 ( ams.org ).

Web links

• Lectures on extremal set systems and two-colorings of hypergraphs (PDF; 237 kB) by Gy. Károlyi.
• Combinatorial Methods in Computer Science. (PDF; 1.4 MB) Script of a lecture by Peter Hauck, Uni Tübingen, SS 2008.
• Further article by Rudolf Ahlswede and Ning Cai on the AZ identity
• Additional article by TD Thu on AZ identity

References and footnotes

1. ^ Curtis Greene, Daniel J. Kleitman: Proof techniques in the theory of finite sets in: Studies in Combinatorics [Ed. Gian-Carlo Rota ] . S. 35 .
2. ^ Martin Aigner: Combinatorial Theory . S. 425 .
3. ↑ DJ Kleitman in: M. Hall and JH van Lint (eds.): Combinatorics (Math. Center Tracts 55) . Amsterdam 1974, p. 77 ff .
4. ↑ Hans-Josef Scholz: About the combinatorics of finite power sets in connection with Sperner's theorem . S. 19 .
5. ↑ Konrad Engel: Sperner Theory .
6. ↑ set system of the lower neighbors of   ${\displaystyle {\mathcal {T}}}$
7. ↑ set system of the upper neighbors of   ${\displaystyle {\mathcal {T}}}$
8. ^ R. Ahlswede, Z. Zhang: An identity in combinatorial extremal theory . In: Advances in Mathematics . tape 80 , 1990, pp. 137-151 .
9. ↑ Konrad Engel: Sperner Theory (=  Encyclopedia of Mathematics and its Applications . Volume 65 ). Cambridge University Press, Cambridge (et al.) 1997, ISBN 0-521-45206-6 , pp. 18th ff .