Improved bounds for the sunflower lemma
Ryan Alweiss, Shachar Lovett, Kewen Wu, Jiapeng Zhang
Abstract
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.
Topics & Concepts
SunflowerLemma (botany)CombinatoricsIntersection (aeronautics)MathematicsUpper and lower boundsConjectureConstant (computer programming)Discrete mathematicsComputer scienceBotanyMathematical analysisEngineeringAerospace engineeringProgramming languageBiologyPoaceaeLimits and Structures in Graph TheoryComplexity and Algorithms in GraphsAdvanced Graph Theory Research