The weak sunflower problem: estimate $m(n,k)$ forcing $k$ sets with equal pairwise intersections (Erdős #857)
Statement
Let $m=m(n,k)$ be minimal such that any collection of $m$ distinct sets $A_1,\ldots,A_m\subseteq\{1,\ldots,n\}$ must contain a sunflower of size $k$ — that is, some $k$ of the $A_i$ which pairwise have the same intersection (all $\binom{k}{2}$ pairwise intersections equal one common 'core', so the $k$ sets are pairwise disjoint outside the core). Estimate $m(n,k)$, or even better, give an asymptotic formula. Unlike the classical Erdős–Rado sunflower lemma setting, the sets here have arbitrary sizes and the parameter is the ground-set size $n$, not the uniformity.
Acceptance. FULLY RESOLVES: a proof of an asymptotic formula for $m(n,k)$ — at minimum, for each fixed $k\geq 3$, determining $\lim_n m(n,k)^{1/n}$ with matching upper bound and construction — as a complete written proof or machine-checkable (Lean, e.g. against the formal-conjectures statement). A computation alone cannot close this. ADVANCES: an upper bound on $m(n,3)$ with exponential base strictly below the Naslund–Sawin base stated in the background, with proof; an explicit sunflower-free family construction whose exponential base is proved to strictly exceed the best lower bound published in the literature (the submission must identify and cite that prior record, e.g. from the Erdős–Szemerédi line of work, and state it in words); the analogous exponent improvement for any fixed $k\geq 4$; or exact values of $m(n,3)$ for small $n$, each certified by an extremal family (witness file) plus an exhaustiveness certificate (SAT/orderly search transcript a program can re-check). Deliver the proof file, or the construction/witness files + search code + certificates.
Background
A problem of Erdős [Er70], repeated in [Er71, p.105] and studied with Szemerédi [ErSz78b]; listed as open on erdosproblems.com/857 (fetched 2026-07-13, status 'open'). This is sometimes called the weak sunflower problem; the strong (uniform) sunflower problem of Erdős–Rado is Erdős #20 (erdosproblems.com/20) — a closely related but distinct problem on 3-sunflower-free $n$-uniform families already appears on this venue, and Erdős #536 and #856 (erdosproblems.com/536, /856) are also related. In [Er70] Erdős posed the equivalent formulation with intersections replaced by unions. The trivial bound is $m(n,k)\leq 2^n+1$. For $k=3$ the problem is strongly connected to the cap set problem (the maximal size of subsets of $\mathbb{F}_3^n$ with no three-term arithmetic progression), as observed by Alon, Shpilka, and Umans [ASU13]; exploiting the Croot–Lev–Pach/Ellenberg–Gijswijt polynomial method, Naslund and Sawin [NaSa17] proved the exponential improvement $$m(n,3)\leq \left(\frac{3}{2^{2/3}}\right)^{(1+o(1))n}\approx 1.8899^{(1+o(1))n}.$$ Determining the correct exponential growth rate — even for $k=3$ — is open, mirroring the open gap in the cap set problem itself. A formal Lean statement exists in the google-deepmind/formal-conjectures repository (ErdosProblems/857.lean). The attacker's tool: slice-rank/polynomial-method refinements for upper bounds, cap-set-style product constructions for lower bounds, and exhaustive/SAT computation of exact values of $m(n,3)$ for small $n$ (no exact table appears in the literature or OEIS — a fresh checkable frontier).
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #857 (T. F. Bloom) | website |
| REF-02 | Formal Lean statement of Erdős #857 (google-deepmind/formal-conjectures) | website |
| REF-03 | Erdős Problem #20 — the strong (uniform) sunflower problem | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.