南京大学：《组合数学》课程教学资源（课堂讲义）极值集合论 Extremal set theory

Extremal Combinatorics "How large or how small a collection of finite objects can be,if it has to satisfy certain restrictions.” set system F2lm with ground set [n]

Extremal Combinatorics “How large or how small a collection of finite objects can be, if it has to satisfy certain restrictions.” F ￾ 2[n] set system with ground set [n]

Sunflowers Fa sunflower of size r with center C: IF=r S,T∈F,S∩T=C a sunflower of size 6 with core C

S6 S5 4 S S3 S2 S1 Sunflowers a sunflower of size 6 with core C F a sunflower of size r with center C: |F| = r ⇥S, T ￾ F, S ⌅ T = C C

Sunflowers F a sunflower of size r with center C: F=r S,T∈F,S∩T=C a sunflower of size 6 with core 0

S6 S5 4 S S3 S2 S1 Sunflowers a sunflower of size 6 with core F a sunflower of size r with center C: |F| = r ⇥S, T ￾ F, S ⌅ T = C ￾

Sunflower Lemma(Erdos-Rado 1960) () F1>k(-1) a sunflower gCF,such that g=r Induction on k.when k=1 () |F|>r-1 3r singletons

Induction on k. when k=1 F ￾ ￾[n] 1 ⇥ |F| > r ￾ 1 ∃ r singletons F ￾ ￾[n] k ⇥ . |F| > k!(r ￾ 1)k Sunflower Lemma (Erdős-Rado 1960) ⇥ a sunflower G ￾ F, such that |G| = r

Sunflower Lemma (Erdos-Rado 1960) rs(). F1>k(r-1)6E 3a sunflower gC F,such that g=r Fork≥2， take largest gF with disjoint members VS,T∈G that S≠T,SnT=0 case.I: gr,g is a sunflower of size r case.2: |g1≤r-1, Goal:find a popular xe[n]

For k≥2, take largest G ￾ F with disjoint members ⇤S, T ￾ G that S ⇥= T, S ⌃ T = ⌅ case.1: |G| ￾ r, G is a sunflower of size r case.2: |G| ⇥ r ￾ 1, Goal: find a popular x∈[n] F ￾ ￾[n] k ⇥ . |F| > k!(r ￾ 1)k Sunflower Lemma (Erdős-Rado 1960) ⇥ a sunflower G ￾ F, such that |G| = r

Sunflower Lemma (Erdos-Rado 1960) () F1>k(r-1) a sunflower gCF,such that g=r lg≤r-1, Goal:find a popular xE[n] consider {S∈F|x∈S remove x H={S\{x}|S∈F∧x∈S} if7H>(k-1)(r-1)-11.H

Goal: find a popular x∈[n] consider H = {S \ {x} | S ￾ F ⌅ x ￾ S} {S ￾ F | x ￾ S} remove x H ⇥ ￾ [n] k ￾ 1 ⇥ if |H| > (k ￾ 1)!(r ￾ 1) I.H. k￾1 |G| ⇥ r ￾ 1, F ￾ ￾[n] k ⇥ . |F| > k!(r ￾ 1)k Sunflower Lemma (Erdős-Rado 1960) ⇥ a sunflower G ￾ F, such that |G| = r

() 1F1>!(-1) take largest gF with disjoint members g≤r-1,letY=US|Y\≤k(r-1) S∈g claim:Yintersects all SEF if otherwise::3T∈F,T∩Y=0 T is disjoint with all SEg contradiction!

|G| ⇥ r ￾ 1, Y = ￾ S￾G let S take largest G ￾ F with disjoint members |Y | ⇥ k(r ￾ 1) F ￾ ￾[n] k ⇥ . |F| > k!(r ￾ 1)k claim: Y intersects all S ￾ F if otherwise: ⇥T ￾ F, T ⇧ Y = ⇤ T is disjoint with all S ￾ G contradiction!

e() |F>(r-1) take maximal gF with disjoint members Ig≤r-1,letY=Js Y≤k(r-1) S∈g Y intersects all S∈F pigeonhole:]x∈Y, #ofS∈Fcontainx if 1{S∈F1xeS1 、(r-1) YI 之r-1) =(k-1)川(-1)k-1 H={S\{x}|S∈F∧x∈S k-1 17>(k-1)(-1)-1

H = {S \ {x} | S ￾ F ⌅ x ￾ S} |G| ⇥ r ￾ 1, Y = ￾ S￾G let S take maximal G ￾ F with disjoint members |Y | ⇥ k(r ￾ 1) pigeonhole: ∃ x∈Y, |{S ￾ F | x ￾ S}| ￾ |F| |Y | F ￾ ￾[n] k ⇥ . |F| > k!(r ￾ 1)k ⇥ k!(r ￾ 1)k k(r ￾ 1) = (k ￾ 1)!(r ￾ 1)k￾1 H ⇥ ￾ [n] k ￾ 1 ⇥ |H| > (k ￾ 1)!(r ￾ 1)k￾1 Y intersects all S ￾ F # of S ￾ F contain x

Sunflower Lemma (Erdos-Rado 1960) 1F>(r-1)k> a sunflower gCF,such that g=r 3x∈Y,lett={S\{x}|S∈F∧x∈S ∈() 17H>(k-1)(r-1)k-1 I.H.:H contains a sunflower of size r adding x back,it is a sunflower inF

∃ x∈Y, H = {S \ {x} | S ￾ F ⌅ x ￾ S} H ⇥ ￾ [n] k ￾ 1 ⇥ let |H| > (k ￾ 1)!(r ￾ 1)k￾1 I.H.: H contains a sunflower of size r adding x back, it is a sunflower in F F ￾ ￾[n] k ⇥ . |F| > k!(r ￾ 1)k Sunflower Lemma (Erdős-Rado 1960) ⇥ a sunflower G ￾ F, such that |G| = r

Sunflower Conjecture IF>c(r)k a sunflower gCF,such that g=r c(r):constant depending only on r Alon-Shpilka-Umans 2012: if sunflower conjecture is true then matrix multiplication is slow

c(r) : constant depending only on r F ￾ ￾[n] k ⇥ . Sunflower Conjecture ⇥ a sunflower G ￾ F, such that |G| = r |F| > c(r) k Alon-Shpilka-Umans 2012: if sunflower conjecture is true then matrix multiplication is slow