Extremal Combinatorics "How large or how small a collection of finite objects can be,if it has to satisfy certain restrictions..” set system F2l 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 F a sunflower of size r with center C: |F|=r VS,T∈F,S∩T=C a sunflower of size 6 with core C 丹 S S
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 VS,T∈F,S∩T=C a sunflower of size 6 with core ( S1 员 s
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) c() 1F>(-1)k> 3a sunflower gCF,such that G=r Induction on k. when k=1 ) se 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) () |F1>k(r-1)k> 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: g≥r, G is a sunflower of size r case.2: |g≤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) (） 1F1>k(r-1)k> 3a sunflower gC F,such that g=r g≤r-1, Goal:find a popular xE[n] consider {S∈F|x∈S) remove x H={S\{x}|S∈F∧x∈S} () if17>(k-1)(-1)k-1 I.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
s(W) 1F>k!(-1)k take largest g with disjoint members g≤r-1, letY=US|Y\≤k(r-1) S∈g claim:Y intersects all S eF 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!
r() 1F>k(r-1) take maximal gF with disjoint members g≤r-1, IetY=USIY\≤k(r-1) S∈g Y intersects all S∈F pigeonhole:3x∈Y, #ofS∈F contain x 1F到 {S∈F|x∈S k!(r-1)k Y k(r-1) = (k-1)川(-1)-1 H={S\{c}|S∈F∧x∈S} HE () 7>(k-1)(r-1)k-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) () F>:(r-1)k> 3a sunflower gC F,such that g=r 3x∈Y,IetH={S\{x}|S∈F∧x∈S 为() 7>(k-1)(-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 () F>c(r) 3a sunflower gC F,such that 9=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