Lubell-Yamamoto-Meshalkin egyenlőtlenség
A matematika , Lubell-Yamamoto-Meshalkin egyenlőtlenség , vagy LYM egyenlőtlenség , a kombinatorikus egyenlőtlenség a méretek a készlet egy Sperner család , bizonyítja Bollobás , Lubell, Meshalkin és Yamamoto.
Számos alkalmazása van a kombinatorikában; különösen Sperner lemmájának bizonyítására használható . Ezt a kifejezést hasonló egyenlőtlenségek jelölésére is használják.
Államok
Legyen U állítva n elemek At egy család a részek az U amelyek közül egyik sem tartalmazza egy másik, és egy k száma részeinek mérete k a családban A . Így,
∑k=0nemnál nélk(nemk)≤1.{\ displaystyle \ sum _ {k = 0} ^ {n} {\ frac {a_ {k}} {n \ select k}} \ leq 1.}
Lubell bemutató
Lubell (1966-ban) azt mutatja, ez a LYM egyenlőtlenség egy kettős számlálás érv , amelyben számít a permutációk a U = {1, ... N } két módon. Először is közvetlen felsorolással n vannak ! . De másfelől, tudjuk választani tagja S a család egy és bijekciót s : {1, ..., | S |} → S és töltse ki az s- t egy U permutációban . Ha | S | = k , így társítjuk a k-t ( n - k )! permutációk. Minden permutáció van társítva legfeljebb egy tagja S az A. Valóban a abszurditását, ha s egy permutációja társított két tag, S és T az A vett olyan, hogy | S | ≤ | T |, majd a {1,…, | képe S | s által S jelentése S , és szerepel a T-ben . Következésképpen az ezen konstrukció által generált permutációk száma
∑S∈NÁL NÉL|S|!(nem-|S|)!=∑k=0nemnál nélkk!(nem-k)!.{\ displaystyle \ sum _ {S \ in A} | S |! (n- | S |)! = \ sum _ {k = 0} ^ {n} a_ {k} k! (nk)!.}}
Mivel ez a szám legfeljebb megegyezik a permutációk teljes számával,
∑k=0nemnál nélkk!(nem-k)!≤nem!,{\ displaystyle \ sum _ {k = 0} ^ {n} a_ {k} k! (nk)! \ leq n!,}
amely arra a következtetésre jut.
Megjegyzések és hivatkozások
(fr) Ez a cikk részben vagy egészben az
angol Wikipedia
„ Lubell - Yamamoto - Meshalkin egyenlőtlenség ” című cikkéből származik
( lásd a szerzők felsorolását ) .
-
(in) B. Bollobás , " általánosított grafikonok " , Acta Math. Hungar. , vol. 16, n csont 3-41965, P. 447–452 ( DOI 10.1007 / BF01904851 )
-
(in) D. Lubell , " Sperner's lemma rövid bizonyítéka " , JCT , vol. 1, n o 21966, P. 299 ( DOI 10.1016 / S0021-9800 (66) 80035-2 )
-
(in) LD Meshalkin , " Sperner-tétel általánosítása a véges halmaz részhalmazainak számáról " , Th. Prob. Appl. , vol. 8, n o 21963, P. 203-204 ( DOI 10.1137 / 1108023 )
-
(en) Koichi Yamamoto , " Logaritmikus érdekében szabad elosztó rács " , J. Math. Soc. Japán , vol. 6,1954, P. 343-353 ( online olvasás )
-
(in) Mr. Beck , X. Wang és T. Zaslavsky , "A Sperner-tétel egyesítő általánosítása" , E. Gyari, Katona GOH és Lovász L. , További halmazok, grafikonok és számok: tisztelgés Sós Verának és Hajnal András , Springer , koll. "Bolyai Társaság Matematikai Studies" ( n o 15),2006, P. 9–24, arXiv : math / 0112067
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">