2020/06/07 by Ryan Alweiss, Shachar Lovett, Kewen Wu +1 · 5 citations
Mathematics · Computer Science · Engineering · #Limits and Structures in Graph Theory #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Sunflower #Lemma (botany) #Combinatorics #Intersection (aeronautics) #Mathematics #Upper and lower bounds #Conjecture #Constant (computer programming) #Discrete mathematics #Computer science #Botany #Mathematical analysis #Engineering
paper · doi:10.1145/3357713.3384234
openalex publication_date 2020/06/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
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ő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 (logw) 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.