Erdős–Rado sunflower conjecture: removing the log k factor from the (C r log k)^k bound
Sixty-six years old with a $1000 prize, and the 2019–2020 spread method stops exactly one log k factor short with no idea for removing it, so 71: above union-closed sets (66) and below diagonal Ramsey (78). Application value 12.5 is the highest among the combinatorics problems because sunflower bounds feed circuit and data-structure lower bounds. Leverage 40: the spread lemma already reshaped the threshold-conjecture line (Park–Pham).
The problem
How many equal-size sets force a sunflower, sets sharing exactly the same overlap? The best bound is nearly but not exactly right.
- 1Sunflower: sets sharing the same core
- 2A big pile of k-sets must contain one
- 3Old bound: about k factorial
- 4Now (c r log k) to the k; remove the log
Definitions. A sunflower with petals is a family of sets whose pairwise intersections are all the same set (the or core). Equivalently, the sets have for , so after removing the are disjoint. Let be the least such that every family of more than sets, each of size , contains a sunflower with petals.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- SAT solving (CDCL)Algorithm
- Step 4
- Extremal and probabilistic combinatoricsTheory · host
- Then
- Erdős–Rado sunflower conjecture: removing the log k factor from the (C r log k)^k boundThe problem
State of the art
Open. Kostochka (1997) improved Erdős–Rado to o(k!) for fixed r. Alweiss, Lovett, Wu and Zhang (arXiv:1908.08483, Annals 2021) proved with a spread-lemma argument; Rao (arXiv:1909.04774) simplified it with a coding argument, Tao and Frankston–Kahn–Narayanan–Park gave further proofs, and Bell, Chueluecha and Warnke (arXiv:2009.09327) obtained , the current record. Special cases are known: Mishra (arXiv:2606.02667) proves the conjecture for shifted families, and Ge, Wang, Xu and Zhao (arXiv:2609.18995) for families of bounded VC-dimension (both 2026 preprints, unrefereed). The Erdős problems site lists the problem (#20) as open with no claimed proof.
Realistic applications
Sunflower bounds enter monotone circuit lower bounds (Razborov’s method), DNF and junta approximation, randomness extraction and data-structure lower bounds; the 2019 improvement immediately strengthened several of these. A full resolution would sharpen them further but change no deployed system.
What counts as solved
A refereed proof that f(k,r) ≤ C(r)^k for every fixed r (or for r = 3), or a construction showing superexponential growth in k.
How it gets verified
Lean proofA formal proof checked by Lean 4 / Mathlib.
Statement: Erdos20.erdos_20 in ErdosProblems/20.lean (Formal Conjectures pinned at commit e754a78 (17 October 2026); Wikipedia/ErdosRadoSunflowerConjecture.lean points there): there are constants c_k with f(n,k) < c_k^n for all n > 0, where f(n,k) is the sunflower threshold for families of n-element sets and k petals, defined in the file with the corpus' Sunflower helpers. A proof is accepted when it compiles against the pinned corpus and passes Comparator; the current best bound (C·k·log n)^n leaves the log n factor to remove (the pack writes the same bound with k and r swapped).
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
A new combinatorial or information-theoretic idea is needed; computation only checks small cases.
Bottlenecks
ranked by votes- #1TheoryThe log k loss in the spread lemma
Every known proof finds a sunflower via a spread (pseudorandom) subfamily, and the probabilistic covering step inherently loses a log k factor per level.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Jul 17, 2026Bounded VC-dimension case (preprint)source
Ge–Wang–Xu–Zhao; with Mishra’s shifted-family case, the 2026 claims cover special classes only.
- Sep 20, 2020(Cr log k)^ksource
Bell–Chueluecha–Warnke, building on Rao.
- Aug 22, 2019Spread-lemma breakthroughsource
Alweiss–Lovett–Wu–Zhang reach (log k)^k-type bounds.
- Jan 1, 1960Erdős–Rado sunflower lemmasource
f(k,r) ≤ k!(r−1)^k and the conjecture (date approximate to the year).