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