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 $ℱ$ 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ść Szablon:Wzór

Alternatywnie, jeśli oznaczymy przez $p_k$ liczbę zbiorów $k$-elementowych w $ℱ,$ to spełniona jest nierówność Szablon:Wzór

Dowód

Niech $ℱ=\{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 Szablon:Wzór

Dzieląc powyższą nierówność obustronnie przez $n!$, z definicji współczynnika dwumianowego otrzymujemy Szablon:Wzór co stanowi tezę w pierwszej postaci. Druga postać tezy wynika wprost z tego, że Szablon:Wzór

Zobacz też

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