Nierówność Lubella-Yamamoto-Meshalkina

Nierówność Lubella-Yamamoto-Meshalkina (ang. Lubell-Yamamoto-Meshalkin Inequality, LYM Inequality) – 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.

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

Twierdzenie

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

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

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

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

Dowód

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

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

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

$\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 $n!$, z definicji współczynnika dwumianowego otrzymujemy

$\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

$\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