Papex

Open problem · Mathematics · since 1960

Sunflower conjecture

For a fixed r, does every family of more than Cᵏ sets of size k contain r sets that all share the same pairwise intersection?

Summary

A sunflower is a collection of sets that overlap only in one common core. Erdős and Rado conjectured in 1960 that an exponential bound forces one to appear; it is open even for three sets, though known bounds improved markedly around 2020.

Why it is open

A sunflower with r petals is a collection of r sets in which every pair has the same intersection, called the core [10]. Paul Erdős and Richard Rado, who called these collections Δ-systems, proved in 1960 that every family of more than k!(r − 1)^k sets of size k contains a sunflower with r petals, and gave a family of (r − 1)^k sets with none [1, 10]. Their upper bound is of the form k^(k(1+o(1))) [4]. They wrote that it was "not improbable" that the factorial could be replaced by an exponential, and that applications in number theory had prompted their work [1]. The sunflower conjecture is that every family of more than C^k such sets contains one, with C depending only on r [10].

Erdős offered $1,000 for a proof or disproof even in the case of three petals, which he expected "contains the whole difficulty"; he also wrote "I really do not see why this question is so difficult" [12]. A resolution would be a bound of the form C^k for every fixed r, or, for some r, sunflower-free families that grow faster than every exponential in k [10].

The conjecture is distinct from the weak sunflower problem of Erdős and Szemerédi, which concerns arbitrary subsets of an n-element set [3, 12]. No prize body sets conditions for the problem; the status here follows Wikipedia's list of unsolved problems in mathematics [13].

What is known

The classical bound (1960–2019). For three petals, A. Kostochka showed in 1997 that O(k!·(log log log k / log log k)^k) sets of size k force a sunflower [10]; Erdős awarded him a consolation prize of $100 for this o(k!) bound [12]. Ryan Alweiss, Shachar Lovett, Kewen Wu and Jiapeng Zhang wrote that after nearly 60 years of research the known bounds were still of the form k^(k(1+o(1))), even for three petals [4].

The 2019 breakthrough and its refinements (2019–2021). In 2019 Alweiss, Lovett, Wu and Zhang proved that every family of at least (C r³ log k log log k)^k sets of size k contains a sunflower with r petals, about (log k)^k for fixed r [4, 10]. They worked with robust sunflowers, a notion first studied by Benjamin Rossman: families whose sets, outside the common core, are spread enough that a random subset of the elements very likely contains one of them [4, 10]. Anup Rao used Shannon's noiseless coding theorem to give a simpler proof and the bound (α r log(rk))^k for a universal constant α [5]. Keith Frankston, Jeff Kahn, Bhargav Narayanan and Jinyoung Park refined the counting arguments, and Tolson Bell, Suchakree Chueluecha and Lutz Warnke recorded that (C r log k)^k sets suffice [6]. This is the best general bound reported in T. F. Bloom's database of Erdős problems and by Balogh and colleagues in 2025 [9, 12]. In Rao's words, the only difference between this bound and the conjecture "is the presence of the log k term" [10].

Special families (2021–2026). The Vapnik–Chervonenkis (VC) dimension of a family is the size of the largest set all of whose subsets arise as intersections with members of the family [9]. Jacob Fox, János Pach and Andrew Suk showed that families of k-sets with VC-dimension at most d contain an r-sunflower once they have at least 2^(10k(dr)^(2 log* k)) members, where log* is the iterated logarithm, and verified the conjecture for families of bounded Littlestone dimension and for some geometric set systems [8]. József Balogh, Anton Bernshteyn, Michelle Delcourt, Asaf Ferber and Huy Tuan Pham improved this to (C r (log d + log* k))^k and showed that for VC-dimension 1 the bound (r − 1)^k is sharp [9]. A July 2026 preprint by Gennian Ge, Jian Wang, Zixiang Xu and Xiaochen Zhao, not peer reviewed, claims the conjecture for every family of bounded VC-dimension, with fewer than 2(50dr)^k sets in a family without an r-sunflower [11].

Connections (1985–2022). Sunflowers are a tool in the approximation method of Alexander Razborov, who in 1985 gave the first superpolynomial lower bound for detecting cliques with monotone circuits, which have no negations; later arguments of this kind give exponential bounds, and Rao notes that similar bounds for general circuits would resolve P versus NP [7, 10]. Bruno Pasqualotto Cavalar, Mrinal Kumar and Rossman used the 2019 robust sunflower bound to prove an exp(n^(1/2−o(1))) lower bound on the monotone circuit size of an explicit function, improving exp(n^(1/3−o(1))) [7]. Noga Alon, Amir Shpilka and Christopher Umans showed that the conjecture, if true, answers negatively a question of Coppersmith and Winograd about one route to fast matrix multiplication [2]. The spread method of the 2019 paper also inspired Park and Pham's proof of the Kahn–Kalai conjecture [9].

Main approaches

Spread families and robust sunflowers. If no small set lies in too many members of the family, a random partition of the elements finds r disjoint members; otherwise the argument recurses on the members that contain such a set [6]. Strongest evidence: it took the bound from k^(k(1+o(1))) to (C r log k)^k [4, 6]. Main difficulty: the log k cannot be removed for robust sunflowers, since Alweiss and colleagues found families of Ω(log k)^(k−√k) sets without one; Rao writes that "it is quite possible" the conjecture still holds in its original form [10].

Polynomial methods. By a theorem of Alon, Shpilka and Umans, the conjecture is equivalent to bounding, by a constant independent of D, the base c_D in the size c_D^n of sunflower-free sets in (Z/DZ)^n, a possible route that Eric Naslund and William Sawin pursue [3]. Strongest evidence: applying the polynomial method of Croot, Lev and Pach and of Ellenberg and Gijswijt to the weak problem, Naslund and Sawin showed that a family of subsets of {1, …, n} without a three-petal sunflower has at most (3/2^(2/3))^((1+o(1))n) members [3]. Main difficulty: in (Z/DZ)^n their version of the method with characters gives c_D = (3/2^(2/3))(D − 1)^(2/3), which depends on D [3].

Restricted families. Prove the conjecture for families with extra structure, such as bounded VC-dimension, bounded Littlestone dimension or geometric set systems [8, 9]. Strongest evidence: the sharp bound for VC-dimension 1 and the 2026 preprint claim for every bounded VC-dimension [9, 11]. Main difficulty: every family of k-sets has VC-dimension at most k, and Balogh and colleagues improve on the general bound only when d = k^(o(1)) [9].

Open sub-questions

  1. Combining the VC-dimension bounds. Does every family of k-sets with VC-dimension d and more than (C r log(d + 1))^k members contain an r-sunflower, removing both the log* k of Balogh and colleagues and the linear dependence on d in the 2026 preprint [9, 11]?
  2. Beyond robust sunflowers. Robust sunflowers cannot give a base below order log k [10]. Is there a weaker structure, still forcing an ordinary sunflower, that every family of more than (Cr)^k sets of size k contains [4, 10]?
  3. The algebraic constant. Can a slice-rank or character argument bound c_D for sunflower-free sets in (Z/DZ)^n by a constant independent of D [2, 3]?
  4. Monotone circuits beyond sunflowers. Cavalar, Kumar and Rossman see little room for better monotone lower bounds from sunflower approximations on p-biased distributions. Can another approximation method or test distribution give an explicit monotone function a lower bound beyond 2^(Ω(√n)) [7]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Erdős, P. & Rado, R. (1960). Intersection theorems for systems of sets. Journal of the London Mathematical Society s1-35(1), 85–90. 10.1112/jlms/s1-35.1.85 · Checked 16 Oct 2026
  2. Alon, N., Shpilka, A. & Umans, C. (2013). On sunflowers and matrix multiplication. computational complexity 22(2), 219–243. 10.1007/s00037-013-0060-1 · Checked 16 Oct 2026
  3. Naslund, E. & Sawin, W. (2017). Upper bounds for sunflower-free sets. Forum of Mathematics, Sigma 5, e15. 10.1017/fms.2017.12 · Checked 16 Oct 2026
  4. Alweiss, R., Lovett, S., Wu, K. & Zhang, J. (2021). Improved bounds for the sunflower lemma. Annals of Mathematics 194(3), 795–815. 10.4007/annals.2021.194.3.5 · Checked 16 Oct 2026
  5. Rao, A. (2020). Coding for sunflowers. Discrete Analysis 2020:2. 10.19086/da.11887 · Checked 16 Oct 2026
  6. Bell, T., Chueluecha, S. & Warnke, L. (2021). Note on sunflowers. Discrete Mathematics 344(7), 112367. 10.1016/j.disc.2021.112367 · Checked 16 Oct 2026
  7. Cavalar, B. P., Kumar, M. & Rossman, B. (2022). Monotone circuit lower bounds from robust sunflowers. Algorithmica 84(12), 3655–3685. 10.1007/s00453-022-01000-3 · Checked 16 Oct 2026
  8. Fox, J., Pach, J. & Suk, A. (2023). Sunflowers in set systems of bounded dimension. Combinatorica 43(1), 187–202. 10.1007/s00493-023-00012-z · Checked 16 Oct 2026
  9. Balogh, J., Bernshteyn, A., Delcourt, M., Ferber, A. & Pham, H. T. (2025). Sunflowers in set systems with small VC-dimension. Combinatorica 45(6), 58. 10.1007/s00493-025-00186-8 · Checked 16 Oct 2026
  10. Rao, A. (2026). The story of sunflowers. Journal of the London Mathematical Society 113(1), e70380. 10.1112/jlms.70380 · Checked 16 Oct 2026
  11. Ge, G., Wang, J., Xu, Z. & Zhao, X. (2026). Bounded VC-dimension implies the Erdős–Rado sunflower conjecture. Preprint, arXiv:2609.18995 (version 1, 17 July 2026), not peer reviewed. Source · Checked 16 Oct 2026
  12. Bloom, T. F. Erdős Problem #20 (page last edited 7 March 2026) and Erdős Problem #857. Erdős Problems database. Source · Checked 16 Oct 2026
  13. Wikipedia. List of unsolved problems in mathematics (revision of 15 October 2026). Source · Checked 16 Oct 2026

Page reviewed 16 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.