The sunflower conjecture

Three sets form a sunflower when every two of them meet in the same common core. Erdős and Rado asked whether exponentially many sets of size $n$ already force a sunflower, where their classical argument needs about $n!$ of them. The question is central to extremal set theory and is even connected to fast matrix multiplication.

Problem

A family of $k$ distinct sets $S_1,\dots,S_k$ is a $k$-sunflower if there is a set $Y$, the core, with $S_i\cap S_j=Y$ for all $i\neq j$; the petals $S_i\setminus Y$ are then pairwise disjoint. Let $f(n,k)$ be the least integer such that every family of at least $f(n,k)$ distinct $n$-element sets contains a $k$-sunflower.

Is it true that for every $k\ge 3$ there is a constant $c_k$ such that

$$f(n,k) < c_k^{\,n} \quad \text{for all } n\ge 1?$$

Erdős offered $1000 for a proof or disproof even in the case $k=3$, which he expected to contain the whole difficulty.

Background

Erdős and Rado studied these configurations, then called $\Delta$-systems, in 1960 and proved the sunflower lemma: any family of more than $(k-1)^n n!$ sets of size $n$ contains a $k$-sunflower. Erdős returned to the question of replacing $n!$ by an exponential in many problem papers and wrote that he did not see why it is so difficult. Alon, Shpilka and Umans (2013) showed that variants of the conjecture, if true, would rule out certain proposed routes to fast matrix multiplication.

What is known

• Upper bounds. Kostochka (1997) improved the Erdős–Rado bound slightly, to $o(n!)$, for which Erdős paid a $100 consolation prize, but the bound stayed of the form $n^{(1+o(1))n}$ until Alweiss, Lovett, Wu and Zhang (2021) broke the factorial barrier with $f(n,k) < (Ck\log n\log\log n)^n$. Refinements by Rao (2020), Frankston, Kahn, Narayanan and Park (2021) and Bell, Chueluecha and Warnke (2021) give the current record

  $$f(n,k) < (Ck\log n)^n$$

  for an absolute constant $C$.
• The other regime. When $n$ is fixed and $k$ grows, Kostochka, Rödl and Talysheva (1999) showed $f(n,k)=(1+O_n(k^{-1/2^n}))\,k^n$.
• Special cases. In 2026 Ge, Wang, Xu and Zhao proved the conjecture for families of bounded VC-dimension (arXiv:2609.18995, preprint).
• The non-uniform version. Erdős and Szemerédi asked the analogous question for arbitrary subsets of $\{1,\dots,n\}$: must a family with no $k$-sunflower have at most $c_k^n$ members for some $c_k<2$? The case $k=3$ follows from the cap-set method, and in October 2026 Bucić, He and Lee posted a proof for every $k$ (arXiv:2610.26686, preprint). This is a different problem from the one above, which remains open.

What would count as progress

• A proof that $f(n,3)\le C^n$ for an absolute constant $C$, or any improvement of $(Ck\log n)^n$ for fixed $k$, for example replacing $\log n$ by $(\log n)^{1-\varepsilon}$.
• A disproof: families of $n$-element sets with no 3-sunflower whose size grows faster than every exponential.
• Exact values or new constructions for small $n$, given as explicit set families whose sunflower-freeness a program can check.
• A formal proof against the Lean statement in formal-conjectures.

References

1. P. Erdős and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc. 35 (1960), 85–90. doi:10.1112/jlms/s1-35.1.85
2. R. Alweiss, S. Lovett, K. Wu and J. Zhang, Improved bounds for the sunflower lemma, Ann. of Math. 194 (2021), 795–815. doi:10.4007/annals.2021.194.3.5
3. A. Rao, Coding for sunflowers, Discrete Analysis (2020). arXiv:1909.04774
4. T. Bell, S. Chueluecha and L. Warnke, Note on sunflowers, Discrete Math. 344 (2021), 112367. doi:10.1016/j.disc.2021.112367
5. A. V. Kostochka, V. Rödl and L. A. Talysheva, On systems of small sets with no large $\Delta$-subsystems, Combin. Probab. Comput. 8 (1999), 265–268. doi:10.1017/S0963548399003818
6. N. Alon, A. Shpilka and C. Umans, On sunflowers and matrix multiplication, Comput. Complexity 22 (2013), 219–243. doi:10.1007/s00037-013-0060-1

Source

Imported from Erdős Problems 20, curated by Thomas Bloom. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.