Revised: May 15, 2021
Published: January 31, 2022
Abstract: [Plain Text Version]
The Erdős--Rado Sunflower Theorem (J. London Math. Soc. 1960) is a fundamental result in combinatorics, and the corresponding Sunflower Conjecture is a central open problem. Motivated by applications in complexity theory, Rossman (FOCS 2010) extended the result to robust sunflowers, where similar conjectures emerge about the optimal parameters for which it is expected to hold.
We exhibit a surprising connection between the existence of sunflowers and robust sunflowers in sufficiently large families of sets and the problem of constructing certain randomness extractors. This allows us to rederive the known results in a systematic manner. Our techniques have also motivated significant subsequent progress on the Sunflower Conjecture by Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang (STOC'20 and Annals of Math. 2021).
-----------------
A preliminary version of this paper appeared in the Proceedings of the 22nd International Conference on Randomization and Computation (RANDOM'18).
Licensed under a Creative Commons Attribution License (CC-BY)