【CS Peer Talk #11】Improved Bounds for the Sunflower Lemma
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.
Kewen Wu is an undergraduate in Peking University. He majors in CS, doubles in Math, and is expected to graduate in 2020. He has broad interests in theoretical computer science.