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