OP-0011Partially solvedCombinatorics$1,000 prize

The Erdős–Rado sunflower conjecture

How large must a family of k-sets be before it must contain three sets meeting pairwise in the same core?

Inferred from the community field; finer classification has not been reviewed.

Source reports OPENAs of 2026-09-08Source & evidence ↓

0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

A sunflower with $r$ petals is a family of sets $A_1,\dots,A_r$ such that $A_i \cap A_j$ is the same set $Y$ for all $i \ne j$ . Conjecture: for every $r$ there is $C = C(r)$ such that any family of more than $C^k$ sets, each of size $k$ , contains a sunflower with $r$ petals.

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

Erdős and Rado proved in 1960 that $k!\,(r-1)^k$ sets suffice. Closing the gap between $k!\,(r-1)^k$ and $C^k$ has been open ever since; Erdős offered US $1,000 for the case$ r = 3$.

Why it matters

Sunflower-free families appear as obstructions in circuit lower bounds, in matrix multiplication algorithms via the Coppersmith–Winograd framework, and in the analysis of DNF formulas.

Progress & source assessment

Alweiss, Lovett, Wu and Zhang (2019) proved a bound of $(O(r\log k))^k$ , an enormous improvement and the first to be quasi-polynomially close to the conjecture. Subsequent refinements by Rao and by Bell–Chueluecha–Warnke tightened the constant.
The remaining gap is the $\log k$ factor in the base.

References

[1]R. Alweiss, S. Lovett, K. Wu, J. Zhang, Improved bounds for the sunflower lemma, STOC 2020. link

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.