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. k1 |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 = SG 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 = SG 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)k1 H ⇥ [n] k 1 ⇥ |H| > (k 1)!(r 1)k1 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)k1 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