Sperner's Theorem F)is an antichain.Then(2). Lubell's proof (double counting) {1,23} maximal chain: {1,2} 13}23y 0cS1C…cSn-1c[ml of maximal chains in 21:n! {2} 3} ∀SC[ml, ☑ of maximal chains containing S:S!(n-S)! F is antichain >Vchain C,IFncl≤1 ∑1S1(n-1S1)!≤nd S∈F
Sperner’s Theorem F 2[n] is an antichain. Then |F| ⇥ n n/2⇥ ⇥ . ∅ {1} {2} {3} {1,2} {1,3} {2,3} Lubell’s proof {1,2,3} (double counting) maximal chain: ⇤ ⇥ S1 ⇥ ··· ⇥ Sn1 ⇥ [n] # of maximal chains in 2[n]: n! {1,3} # of maximal chains containing S: F is antichain ∀ chain C, |F ⇤ C| 1 ⇥S [n], |S|!(n |S|)! SF |S|!(n |S|)! ⇥ n!
Sperner's Theorem Fc2 is an antichain.Then F≤(ny2） Lubell's proof(double counting) >lS1(n-IS)I≤nd S∈F IS(m-1S1)！ n! ≤1 S∈F F1≤(2〉
Sperner’s Theorem F 2[n] is an antichain. Then |F| ⇥ n n/2⇥ ⇥ . |F| n n/2⇥ ⇥ = 1 |F| n n/2⇥ ⇥ Lubell’s proof (double counting) SF |S|!(n |S|)! ⇥ n! ⇤ SF 1 n |S| ⇥ SF |S|!(n |S|)! n!
LYM Inequality (Lubell-Yamamoto 1954,Meschalkin 1963) LYM inequality F C 2 is an antichain. 1 ≤1 S∈F
F 2[n] is an antichain. LYM inequality F 2[n] is an antichain. LYM inequality (Lubell-Yamamoto 1954, Meschalkin 1963) LYM Inequality 1 ⇤ SF 1 n |S| ⇥
FC2m)is an antichain. 1 ( ≤1 S∈F Alon's proof(the probabilistic method) let t be a random permutation [n] Cx={π1}，{T1,2},,{不1，，不n} VS∈F, otherwise let x=>Xs-FnC S∈F C contains Exs-Prisc- 1 precisely 1 S]-set uniform over all |S]-sets
F 2[n] F 2 is an antichain. [n] is an antichain. 1 Alon’s proof (the probabilistic method) let π be a random permutation [n] C = {{1}, {1, 2},..., {1,..., n}} = |F ⇤ C| uniform over all |S|-sets contains precisely 1 |S|-set C let ⇤ SF 1 n |S| ⇥ ⇥S F, XS = 1 S C 0 otherwise X = SF XS E[XS] = Pr[S C] = 1 n |S| ⇥
FC2ml is an antichain. 1 ( ≤1 S∈F Alon's proof(the probabilistic method) let t be a random permutation [n] C元={π1}，{π1，π2}，，{π1，，元n} X=∑∑Xs=IFnCx≤1 is antichain S∈F Cr is chain 1 E(Xs)= ( 1≥ Ex-∑EX1~ 1 S∈F S∈F
Alon’s proof (the probabilistic method) let π be a random permutation [n] C = {{1}, {1, 2},..., {1,..., n}} 1 F is antichain C is chain 1 X = = |F ⇤ C| SF XS E[XS] = 1 n |S| ⇥ E[X] = SF E[XS] = ⇤ SF 1 n |S| ⇥ F 2[n] F 2 is an antichain. [n] is an antichain. 1 ⇤ SF 1 n |S| ⇥