Extremal Combinatorics "How large or how small a collection of finite objects can be,if it has to satisfy certain restrictions." graphs set systems(hypergraphs)
Extremal Combinatorics “How large or how small a collection of finite objects can be, if it has to satisfy certain restrictions.” graphs set systems (hypergraphs)
Set Systems(Families) family:F2 ground set: [n] F has a particular property >？≤F|≤？
Set Systems (Families) F 2[n] family: ground set: [n] F has a particular property ? |F| ?
Antichains F2 is an antichain {1,2,3} VA,B∈F,AEB 《1.213}23} (is antichain } {2 3} largest size:(m2l） “Is this the largest size for all antichains?
Antichains ∅ {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} {1,2} {1,3} {2,3} ⌅A, B ⇥ F, A ⇤ B F 2 is an antichain [n] [n] k ⇥ is antichain largest size: n n/2⇥ ⇥ “Is this the largest size for all antichains?
Sperner's Theorem Theorem(Sperner 1928) F C 2 is an antichain. (2) Emanuel Sperner (1905-1980)
'$ # $ " $ "$ ($ ' ' ($ 2 $ $#$'# ( $* 0 ) $"" #"$ #$ * # 2 ' $ .% .$0 " #$ 1 ''$ " '$' $$ $ ' - $ $ "* #' ($$# 0 ( '+ ' ( $ $#' + ( $ ' " $ $ $ # 0 3/4 ,'$ # $! $$" ##" 2 - " $ 0 $##$$'# ( $ $$ $'# 0 )$ $#$ $$7 # $#+ $'# $## - $* $$ " ! " 0!$ '$&' ' ('$# * 6 $ 34 8" # $ $$$ ! ! " " ! " 0 5 '"$ $ $ #$ 0 ! ! " " ! '$ ##" + $ ( ##+ ($ (# $' # $0 ( $$ ($$$0 " $ " ≤ ! ! " " 0 ! $" ( ∅ ⊂ ⊂ ⊂ ⊂ +" 0"'$$$ 7 # $#+" ($ $$ ($ ( # ' + $ $'$ $$ $ ' $ +$' # 0 &+$ ∈ " $!"'$ $$ 0$ $0 ' ∅ " $ $ # ' ( +$ $ ' " $ $ '$ # ' 0 $ # ' + ( $## $$#! " $ $ # − $0 $$$ $ " $ + $$$0 ' # +# # ( ' ( - 0 0 ##"' $ ' ( $ $ ' ' ' ( $ − $ & $ & ' ( $0 |F| n ⇤n/2⌅ ⇥ . Theorem (Sperner 1928) |F| n ⇤n/2⌅ ⇥ . Theorem (Sperner 1928) F 2[n] is an antichain. Sperner’s Theorem Emanuel Sperner (1905 - 1980)
Sperner's proof {1,2,3} {1,2,3} {1,2} {1,3} {2,3} {1,2} {13} 23} 1 {2} 3} 1) 2} 3) 0 0
Sperner’s proof ∅ {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} ∅ {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}
Fc() shade:V=Te()13eF,SCT shadow:AF-{r∈（四）I3S∈F,TCS S={1,2,3,4,5} F={{1,2,3,{1,3,4,2,3,5}} VF={{1,2,3,4},{1,2,3,5},{1,3,4,5},2,3,4,5}} △F={1,2},{2,3},{1,3,{3,4,{1,4,{2,5{3,5}
shade: shadow: S = {1,2,3,4,5} F = ⇥F = F = { {1,2,3}, {1,3,4}, {2,3,5} } { {1,2,3,4}, {1,2,3,5}, {1,3,4,5}, {2,3,4,5} } {{1,2}, {2,3}, {1,3}, {3,4}, {1,4}, {2,5}, {3,5}} F [n] k ⇥ ⌃F = ⇤ T ⇥ [n] k+1⇥ | ⇤S ⇥ F, S T ⌅ F = ⇤ T ⇥ [n] k1 ⇥ | ⇤S ⇥ F, T S ⌅
Lemma(Sperner) LetF().Then n-k F列≥太+i列 (for k <n) n(for k △F1≥ double counting R={(S,T)S∈F,T∈VF,ScT} VS∈F, n-kT∈(r)have TS 1R=(n-k)儿F到 VTVF,T has ()+1 many k-subsets |R≤(k+1)川VF
Let F [n] k ⇥ . Then |⇧F| ⇥ n k k + 1 |F| |F| ⇥ k n k + 1|F| (for k 0) Let F [n] k ⇥ . Then |⇧F| ⇥ n k k + 1 |F| |F| ⇥ k n k + 1|F| (for k 0) Lemma (Sperner) double counting ⇥S F, n k T ⇤ [n] k+1⇥ have T ⇥ S R = {(S, T) | S ⇥ F, T ⇥ F, S T} |R| = (n k)|F| ⇥T ⌅F, T has k+1 k ⇥ = k + 1 many k-subsets |R| (k + 1)|⇧F|
Lemma(Sperner) Let F().Then VF1≥ n-k +iF列 (for k<n) k △F1≥ (for ke Corollary: Ifk≤(n-1),then VF|≥F. Ifk≥(m-1),then|△F|≥F
Let F [n] k ⇥ . Then |⇧F| ⇥ n k k + 1 |F| |F| ⇥ k n k + 1|F| (for k 0) Let F [n] k ⇥ . Then |⇧F| ⇥ n k k + 1 |F| |F| ⇥ k n k + 1|F| (for k 0) Lemma (Sperner) Corollary: If k ⇥ 1 2 (n 1), then |⌃F| ⇤ |F|. If k ⇥ 1 2 (n 1), then |F| ⇥ |F|
Sperner's Theorem FC2 is an antichain.Then F≤(ny2）- letF=Fn {1,2,3} k {1,2} {1,3} {2,3} Ifk≤(n-1),then VF1≥|F. 1 3} Ifk≥2(m-1),then△F≥lF. replaceF&by{ar VFk if k<(n-1) fk≥(n-1) no overlaps！ repeat until with no decreasing of
Sperner’s Theorem F 2[n] is an antichain. Then |F| ⇥ n n/2⇥ ⇥ . Fk = F ⇥ [n] k ⇥ let ∅ {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3} If k ⇥ 1 2 (n 1), then |⌃F| ⇤ |F|. If k ⇥ 1 2 (n 1), then |F| ⇥ |F|. If k ⇥ 1 2 (n 1), then |⌃F| ⇤ |F|. If k ⇥ 1 2 (n 1), then |F| ⇥ |F|. replace Fk by ⌅Fk if k < 1 2 (n 1) Fk if k ⇥ 1 2 (n 1) no overlaps! repeat until F [n] n/2⇥ ⇥ with no decreasing of |F|
Sperner's Theorem F is an antichain.Then(). Lubell's proof (double counting) {1,2,3} maximal chain: {1.2} 1.3 23} 0cS1c·cSm-1C[nl of maximal chains in 21:n! {2} 3} ∀Sc[m, ☑ of maximal chains containing S:S!(n-S)! F is antichain 廿chain C,|FnC≤1 maximal chains crossings#all maximal chains
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|)! # maximal chains crossing F ≤ # all maximal chains