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

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. 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

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 = ￾ 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!

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 = ￾ 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) () 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)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 () 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