南京大学：《组合数学 Combinatorics》课程教学资源（课件讲稿）Extremal Combinatorics

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] k￾1 ⇥ | ⇤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 ⇥ ··· ⇥ Sn￾1 ⇥ [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