Nerovnost Lubell – Yamamoto – Meshalkin - Lubell–Yamamoto–Meshalkin inequality

v kombinační matematika, Nerovnost Lubell – Yamamoto – Meshalkin, běžněji známý jako LYM nerovnost, je nerovnost na velikosti sad v a Spernerova rodina, prokázáno Bollobás (1965), Lubell (1966), Meshalkin (1963), a Yamamoto (1954). Je pojmenován podle iniciál tří svých objevitelů.

Tato nerovnost patří do pole kombinatorika sad a má mnoho aplikací v kombinatorice. Lze jej použít zejména k prokázání Spernerova věta. Jeho název se také používá pro podobné nerovnosti.

Výrok věty

Nechat U být n- sada prvků, nechť A být rodinou podmnožin U taková, že žádná A je podmnožinou jiné sady v Aa nechte A_k označte počet sad velikostí k v A. Pak

${ displaystyle sum _ {k = 0} ^ {n} { frac {a_ {k}} {n zvolit k}} leq 1.}$

Lubellův důkaz

Lubell (1966) dokazuje nerovnost Lubell – Yamamoto – Meshalkin o a argument dvojího počítání ve kterém počítá obměny z U dvěma různými způsoby. Nejprve spočítáním všech permutací U identifikováno jako {1,…, n } přímo, jeden zjistí, že existují n! z nich. Ale za druhé, lze vygenerovat permutaci (tj. Pořadí) prvků prvku U výběrem sady S v A a výběr mapy, která odesílá {1,…, |S | } do S. Pokud |S | = k, sada S je tímto způsobem spojeno s k!(n − k)! permutace a v každé z nich obraz první k prvky U je přesně S. Každá permutace může být spojena pouze s jednou sadou v A, protože pokud dvě předpony permutace obě vytvořené sady v A pak by jedna byla podmnožinou druhé. Proto je počet permutací, které lze generovat tímto postupem,

${ displaystyle sum _ {S v A} | S |! (n- | S |)! = sum _ {k = 0} ^ {n} a_ {k} k! (n-k) !.}$

Protože toto číslo je nanejvýš celkový počet všech permutací,

${ displaystyle sum _ {k = 0} ^ {n} a_ {k} k! (n-k)! leq n !.}$

Nakonec vydělíme výše uvedenou nerovnost n! vede k výsledku.

Reference

• Bollobás, B. (1965), „O zobecněných grafech“, Acta Mathematica Academiae Scientiarum Hungaricae, 16 (3–4): 447–452, doi:10.1007 / BF01904851, PAN  0183653.

• Lubell, D. (1966), „Krátký důkaz Spernerova lemmatu“, Journal of Combinatorial Theory, 1 (2): 299, doi:10.1016 / S0021-9800 (66) 80035-2, PAN  0194348.

• Meshalkin, L. D. (1963), „Zobecnění Spernerovy věty o počtu podmnožin konečné množiny“, Teorie pravděpodobnosti a její aplikace, 8 (2): 203–204, doi:10.1137/1108023, PAN  0150049.

• Yamamoto, Koichi (1954), „Logaritmický řád volné distribuční mřížky“, Journal of the Mathematical Society of Japan, 6: 343–353, doi:10.2969 / jmsj / 00630343, PAN  0067086.