Improved Bounds for the Sunflower Lemma
- Kewen Wu, Turing Class (Class of 2016)
- Time: 2020-07-03 10:00
- Host: PKU Turing Class Research Committee
- Venue: Online Talk
A sunflower with r petals is a collection of r sets so that the intersection of each pair is equal to the intersection of all of them. Erdős and Rado proved the sunflower lemma: for any fixed r, any family of sets of size w, with at least about w^w sets, must contain a sunflower. The famous sunflower conjecture is that the bound on the number of sets can be improved to c^w for some constant c. In this paper, we improve the bound to about (log w)^w. In fact, we prove the result for a robust notion of sunflowers, for which the bound we obtain is sharp up to lower order terms.