1 of 13

Shivesh K. Roy

​

Sunflower Lemma and Its Applications

2 of 13

  •  

2

Set Family

 

 

 

 

 

 

Core

Petals

 

 

 

 

 

4

5

3

6

1,2

Sunflower with 4 petals

3 of 13

  •  

3

Sunflower

 

 

 

 

4

5

3

6

1,2

Sunflower with 4 petals

Core

Petals

 

 

 

 

Q: Does a pairwise disjoint family of sets form a sunflower?

 

 

Yes, with the empty core

4 of 13

  •  

4

Sunflower Lemma

 

 

 

 

Sunflower with 4 petals

Core

Petals

 

[Erdos-Rado’ J. Lond. Math. Soc. 60]

 

5 of 13

  •  

5

Proof of the Sunflower Lemma

[Erdos-Rado’ J. Lond. Math. Soc. 60]

 

6 of 13

  •  

6

Proof of the Sunflower Lemma

 

[Erdos-Rado’ J. Lond. Math. Soc. 60]

 

7 of 13

  •  

7

 

Proof of the Sunflower Lemma

 

 

1

5

6

 

1, 2, 4

1, 2, 5

1, 2, 6

2,4, 6

1,2, 3

 

 

8 of 13

  •  

8

 

Proof of the Sunflower Lemma

 

 

1

5

6

 

1, 2, 4

1, 2, 5

1, 2, 6

2,4, 6

1,2, 3

 

 

9 of 13

Data Reduction for NP-hard Problems

  •  

9

 

 

 

 

 

 

 

10 of 13

  •  

10

 

[Kirkpatrick & Hell’ SICOMP 83]

 

 

11 of 13

  •  

11

Cubic kernel for Triangle Packing

 

 

 

 

 

 

 

 

 

[Erdos-Rado’ J. Lond. Math. Soc. 60]

 

12 of 13

  •  

12

Summary

​

Open Problem

[Alweiss, Lovett, Wu, & Zhang’ Ann. Math. 21]

[Abu-Khzam’ Inf. Process. Lett. 10]

 

13 of 13

​

​

13