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