Brown–Erdős–Sós conjecture: is the $o(n^2)$ threshold $d_r(e)=(r-2)e+3$? (Erdős #1178)
Statement
For $r\geq 3$ and $e\geq 3$, let $d_r(e)$ be the minimal $d$ such that $$\mathrm{ex}_r(n,\mathcal{F})=o(n^2),$$ where $\mathcal{F}$ is the family of all $r$-uniform hypergraphs on $d$ vertices with $e$ edges, and $\mathrm{ex}_r(n,\mathcal{F})$ is the maximum number of edges of an $r$-uniform hypergraph on $n$ vertices that contains no member of $\mathcal{F}$ (i.e. no $e$ edges spanning at most $d$ vertices). Prove that $$d_r(e)=(r-2)e+3$$ for all $r,e\geq 3$.
Acceptance. FULLY RESOLVES: a complete proof that $d_r(e)=(r-2)e+3$ for all $r,e\geq 3$; since the lower bound $d_r(e)\geq (r-2)e+3$ is already known [BES73], this reduces to proving the upper bound $d_r(e)\leq (r-2)e+3$ (machine-checkable preferred, otherwise a full written proof). ADVANCES (each independently checkable): (a) prove the $r=3$ conjecture $d_3(e)=e+3$ for a new value or an infinite family of $e$; (b) improve the general upper bound below the best stated in the background (currently $d_r(e)\leq (r-2)e+2+\lfloor\log_2 e\rfloor$, and $d_3(e)\leq e+O(\log e/\log\log e)$), with proof; (c) determine an exact new value $d_3(e)$ or $d_r(e)$ for specific small $e$ via a verified construction plus a matching upper bound; or (d) settle Erdős's $\mathrm{ex}_3(n,\mathcal{F})\asymp n\,r_{k-3}(n)$ question for a new $k$, with proof. Deliver the proof, the improved bound with proof, or the exact value with its certificate.
Background
A conjecture of Brown, Erdős, and Sós [BES73]; listed as open on erdosproblems.com/1178 (fetched 2026-07-13, status 'open', tagged 'graph theory | hypergraphs'). Brown, Erdős, and Sós proved the lower bound $d_r(e)\geq (r-2)e+3$, so the conjecture is equivalent to the matching upper bound. The problem is closely tied to the Ruzsa–Szemerédi $(6,3)$-theorem: Ruzsa and Szemerédi [RuSz78] proved $d_3(3)=6$, the celebrated $(6,3)$-result underpinning the triangle removal lemma and Roth-type corners theorems. Erdős, Frankl, and Rödl [EFR86] proved $d_r(3)=(r-2)\cdot 3+3=3r-3$ for all $r\geq 3$. Upper-bound progress toward the general case: Sárközy and Selkow [SaSe05] proved $d_r(e)\leq (r-2)e+2+\lfloor\log_2 e\rfloor$ for all $r,e\geq 3$; Solymosi and Solymosi [SoSo17] proved $d_3(10)\leq 14$; and Conlon, Gishboliner, Levanzov, and Shapira [CGLS23] proved $d_3(e)\leq e+O(\log e/\log\log e)$ for all $e\geq 3$ (the conjectured $r=3$ value being $d_3(e)=e+3$). Erdős [Er75b] further asked whether, for $\mathcal{F}$ the family of $3$-uniform hypergraphs on $k$ vertices with $k-3$ edges, $\mathrm{ex}_3(n,\mathcal{F})\asymp n\,r_{k-3}(n)$, where $r_m(n)$ is the largest size of a subset of $\{1,\ldots,n\}$ with no non-trivial $m$-term arithmetic progression (a Behrend-type quantity); Ruzsa proved the lower bound for $k=6,7,8$. The general-$r$ variant is Erdős #1157 (erdosproblems.com/1157). No Erdős prize is attached. Attacker's tool: Behrend-type and removal-lemma constructions plus exact / near-exact computation of $d_3(e)$ for small $e$ (as in the $d_3(10)\leq 14$ result), backed by flag-algebra and hypergraph-removal bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1178 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.