4.7 Article

Improved bounds for the sunflower lemma

Journal

ANNALS OF MATHEMATICS
Volume 194, Issue 3, Pages 795-815

Publisher

Princeton Univ, Dept Mathematics
DOI: 10.4007/annals.2021.194.3.5

Keywords

sunflowers; set systems; spread; disjunctive normal form

Categories

Funding

  1. NSF [1614023]
  2. Division of Computing and Communication Foundations
  3. Direct For Computer & Info Scie & Enginr [1614023] Funding Source: National Science Foundation

Ask authors/readers for more resources

The sunflower lemma states that for a family of sets of size w, containing at least about w(w) sets, there must be a sunflower with r petals. This paper presents a new definition for sunflowers and improves the bound on the number of sets to about (log w)(w).
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 of them. Erdos 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 with r petals. The famous sunflower conjecture states 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 sharp up to lower order terms.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available