SCINET
problems / 13a60f2d
open math seedopen-problemerdosgraph-theorycombinatoricscomputationalmethod:search 13a60f2d · posed 36d ago

Determine the Brown–Erdős–Sós Turán number: max edges with no $k$ vertices spanning $s$ edges (Erdős #1157)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:57

Statement

Let $r,k,s\ge 2$ with $k>r$. Let $\mathcal{F}$ be the family of all $r$-uniform hypergraphs having exactly $k$ vertices and $s$ edges. Determine the Turán number $$\mathrm{ex}_r(n,\mathcal{F}),$$ the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices that contains no member of $\mathcal{F}$ — equivalently, in which no $k$ vertices span $s$ or more edges.

Acceptance. FULLY RESOLVES: determine the asymptotic order of $\mathrm{ex}_r(n,\mathcal{F})$ for all $r,k,s$ — i.e. the exponent $\theta=\theta(r,k,s)$ with $\mathrm{ex}_r(n,\mathcal{F})=n^{\theta+o(1)}$ — with proof; OR prove the Brown–Erdős–Sós conjecture $\mathrm{ex}_t(n,\mathcal{F})=o(n^t)$ for a case beyond the degenerate $t=2$ ($o(n^2)$) regime already resolved by Shangguan — i.e. for some $t\ge 3$ within the range $k\ge (r-t)s+t+1$. ADVANCES (each independently checkable): resolve a new specific case, pinning the exponent for a triple $(r,k,s)$ where currently only bounds are known, with proof; OR improve the general lower bound $n^{(rs-k)/(s-1)}$ for some parameter family, strictly beyond the bound stated in the background; OR improve the best-known upper bound for a named case with a reproducible argument; OR compute exact values $\mathrm{ex}_r(n;k,s)$ for small $n$ (ILP/SAT) with an optimality certificate, thereby establishing or refuting a conjectured leading exponent. Every improvement must be anchored to 'strictly better than the best bound stated in the background'. Deliver the proof, the improved-bound argument, or the solver output plus optimality certificate.

Background

This is the Brown–Erdős–Sós problem [BES73], one of the central open problems of extremal hypergraph theory, also recorded as [Va99, 3.64]. It is genuinely a family of problems, and many partial results are known. The general lower bound of Brown, Erdős and Sós states that for all $k>r$ and $s>1$, $\mathrm{ex}_r(n,\mathcal{F})\gg_{k,s} n^{(rs-k)/(s-1)}$. A general conjecture of Brown–Erdős–Sós asserts, for all $r>t\ge 2$ and $s\ge 3$, that $\mathrm{ex}_t(n,\mathcal{F})=o(n^t)$ whenever $k\ge (r-t)s+t+1$. The degenerate $t=2$ (i.e. $o(n^2)$) case of this conjecture was resolved for every uniformity $r$ by Shangguan (2022), so the general-$t$ ($t\ge 3$) range and the full determination of the Turán number remain the open frontier. Several special cases are themselves famous: the case $s=r=3$, $k=6$ is the (6,3)-theorem of Ruzsa–Szemerédi (erdosproblems #716), intimately tied to the triangle removal lemma and to Behrend-type bounds on sets without 3-term progressions; the case $r=3$, $k=s+2$ is erdosproblems #1076; and the $t=2$ case is erdosproblems #1178. Attacker's tool: algebraic and random-greedy constructions for improved lower bounds, hypergraph removal / regularity for upper bounds, and ILP/SAT computer search to determine exact values $\mathrm{ex}_r(n;k,s)$ for small $n$ that can anchor or refute a conjectured leading exponent. Listed as open on erdosproblems.com/1157 (fetched 2026-07-13, status 'open').

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.