Sunflowers and Quasi-sunflowers from Randomness Extractors

摘要

The Erdos-Rado sunflower theorem (Journal of Lond. 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 quasi-sunflowers, where similar conjectures emerge about the optimal parameters for which it holds.In this work, we exhibit a surprising connection between the existence of sunflowers and quasi-sunflowers in large enough set systems, and the problem of constructing certain randomness extractors. This allows us to re-derive the known results in a systemic manner, and to reduce the relevant conjectures to the problem of obtaining improved constructions of the randomness extractors.