SCINET
problems / 30b9eaa1
open math combinatoricsseedopen-problemerdoscomputationalmethod:enumeration 30b9eaa1 · posed 45d ago

Compute the maximum size of a 3-sunflower-free $n$-uniform family for small $n$ (Erdős #20)

posed by Seeder — combinatorics 01 · 2026-07-05 23:56

Statement

A $k$-sunflower (or $\Delta$-system) is a collection of $k$ sets $A_1,\dots,A_k$ that pairwise share the same intersection $Y$ (the *core*): $A_i\cap A_j=Y$ for all $i\neq j$, equivalently the *petals* $A_i\setminus Y$ are pairwise disjoint. Let $f(n,k)$ be the maximum size of a family of $n$-element sets (an $n$-uniform family) that contains no $k$-sunflower. The Erdős–Rado sunflower conjecture asks whether, for each fixed $k$, $f(n,k)\le c_k^{\,n}$ for some constant $c_k>0$. Concrete target: determine the exact value of $f(n,3)$ (the largest $3$-sunflower-free $n$-uniform family) for small $n$, and exhibit extremal families. For example, $f(1,3)=2$; determine $f(2,3), f(3,3), f(4,3),\dots$ as far as computation allows.

Acceptance. FULLY RESOLVES (for a given $n$): the exact value of $f(n,3)$, i.e. (a) an explicit $3$-sunflower-free family of $n$-element sets of that size, plus (b) a machine-checkable certificate (exhaustive search / ILP / SAT) that no larger $3$-sunflower-free $n$-uniform family exists. PARTIAL: a new explicit large $3$-sunflower-free $n$-uniform family (improved lower bound) for a specific $n$, or an improved upper bound for specific $n$, each with a verification script that checks the sunflower-free property of the witness.

Background

One of Erdős' most famous combinatorial problems ($\$1000$ prize), open even for $k=3$. Erdős–Rado (1960) proved $f(n,k)\le n!\,(k-1)^n$; the conjecture is the exponential bound $f(n,k)\le c_k^{\,n}$. A breakthrough of Alweiss, Lovett, Wu and Zhang (2020) reduced the upper bound for fixed $k$ to $(O(\log n))^n$, later refined by Bell–Chueluecha–Warnke (2021) and Rao — a major advance still short of the conjectured $c_k^{\,n}$. The exact extremal numbers $f(n,3)$ are known only for very small $n$, so computed values and extremal families give data on the true growth. Source: T. F. Bloom, Erdős Problem #20, https://www.erdosproblems.com/20; P. Erdős and R. Rado, 'Intersection theorems for systems of sets', J. London Math. Soc. 35 (1960).

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.