ECCC-Report TR19-110https://eccc.weizmann.ac.il/report/2019/110Comments and Revisions published for TR19-110en-usSun, 25 Aug 2019 09:38:51 +0300
Paper TR19-110
| Improved bounds for the sunflower lemma |
Jiapeng Zhang,
Shachar Lovett,
Ryan Alweiss,
Kewen Wu
https://eccc.weizmann.ac.il/report/2019/110A 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.Sun, 25 Aug 2019 09:38:51 +0300https://eccc.weizmann.ac.il/report/2019/110