Nierówność Lubella-Yamamoto-Meshalkina

Nierówność Lubella-Yamamoto-Meshalkina (ang. Lubell-Yamamoto-Meshalkin Inequality, LYM Inequality^[1][2]) – nierówność kombinatoryczna ograniczająca maksymalną liczność rodziny zbiorów, w której żaden zbiór nie jest podzbiorem innego. Nierówność ta stanowi twierdzenie silniejsze od twierdzenia Spernera i jest często wykorzystywana do jego udowodnienia^[3].

Nierówność LYM została udowodniona niezależnie przez Yamamoto (1954), Meshalkina (1963) i Lubella (1966)^[1][3].

Twierdzenie

Niech ${\displaystyle A}$ będzie zbiorem ${\displaystyle n}$-elementowym, a ${\displaystyle {\mathcal {F}}}$ rodziną Spernera podzbiorów zbioru ${\displaystyle A,}$ czyli taką rodziną zbiorów, że żaden z nich nie jest zawarty w innym. Wówczas zachodzi nierówność^[2][3]

${\displaystyle \sum _{S\in {\mathcal {F}}}{\frac {1}{\binom {n}{|S|}}}\leq 1}$.

Alternatywnie, jeśli oznaczymy przez ${\displaystyle p_{k}}$ liczbę zbiorów ${\displaystyle k}$-elementowych w ${\displaystyle {\mathcal {F}},}$ to spełniona jest nierówność^[1][2]

${\displaystyle \sum _{k=1}^{n}{\frac {p_{k}}{\binom {n}{k}}}\leq 1}$.

Dowód^[1]

Niech ${\displaystyle {\mathcal {F}}=\{A_{1},A_{2},\dots ,A_{m}\}.}$ Zauważmy, że jest dokładnie ${\displaystyle n!}$ permutacji elementów zbioru ${\displaystyle A.}$ Powiemy, że taka permutacja zaczyna się od ${\displaystyle A_{i},}$ jeśli pierwszych ${\displaystyle |A_{i}|}$ elementów tej permutacji stanowi permutację zbioru ${\displaystyle A_{i}.}$

Niech ${\displaystyle P_{i}}$ będzie zbiorem permutacji zaczynających się od ${\displaystyle A_{i}.}$ Wówczas pierwszych ${\displaystyle |A_{i}|}$ elementów permutacji ${\displaystyle \pi \in P_{i}}$ możemy ustawić na ${\displaystyle |A_{i}|!}$ sposobów, a pozostałe ${\displaystyle n-|A_{i}|}$ elementów na ${\displaystyle (n-|A_{i}|)!}$ sposobów. Zatem z reguły mnożenia ${\displaystyle |P_{i}|=|A_{i}|!(n-|A_{i}|)!.}$

Ponieważ żaden ze zbiorów ${\displaystyle A_{i}}$ nie jest zawarty w innym, zbiory ${\displaystyle P_{i}}$ są rozłączne. Wobec tego

${\displaystyle \sum _{i=1}^{m}|A_{i}|!(n-|A_{i}|)!=\sum _{i=1}^{m}|P_{i}|\leq n!}$.

Dzieląc powyższą nierówność obustronnie przez ${\displaystyle n!}$, z definicji współczynnika dwumianowego otrzymujemy

${\displaystyle \sum _{i=1}^{m}{\frac {1}{\binom {n}{|A_{i}|}}}=\sum _{i=1}^{m}{\frac {|A_{i}|!(n-|A_{i}|)!}{n!}}\leq 1}$,

co stanowi tezę w pierwszej postaci. Druga postać tezy wynika wprost z tego, że

${\displaystyle \sum _{i=1}^{m}{\frac {1}{\binom {n}{|A_{i}|}}}=\sum _{k=1}^{n}{\frac {p_{k}}{\binom {n}{k}}}}$.

Zobacz też

• twierdzenie Spernera
• twierdzenie Erdősa-Ko-Rado

Przypisy

1. IanI. Anderson IanI., Combinatorics of finite sets, Oxford University Press, 1989, s. 2-3, ISBN 978-0-19-853367-2  (ang.).
2. Tran DanT.D. Thu Tran DanT.D., On Local LYM Identities, „Annals of Combinatorics”, 17 (4), 2013, s. 755–763, DOI: 10.1007/s00026-013-0205-6, ISSN 0218-0006 [dostęp 2024-02-29]  (ang.).
3. WitoldW. Lipski WitoldW., WiktorW. Marek WiktorW., Analiza kombinatoryczna, t. 59, Państwowe Wydawnictwo Naukowe, 1986 (Biblioteka Matematyczna), s. 188-189, ISBN 978-83-01-04972-0  (pol.).