Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-110 | 23rd August 2019 06:47

Improved bounds for the sunflower lemma


Authors: Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang
Publication: 25th August 2019 09:38
Downloads: 874


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