Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-110 | 23rd August 2019 06:47

Improved bounds for the sunflower lemma

RSS-Feed




TR19-110
Authors: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang
Publication: 25th August 2019 09:38
Downloads: 2023
Keywords: 


Abstract:

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. Erd\H{o}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 tight up to lower order terms.



ISSN 1433-8092 | Imprint