Tightness of the Kővári–Sós–Turán bound: is $\mathrm{ex}(n;K_{r,r})\gg n^{2-1/r}$? (Erdős #714)
Statement
Let $K_{r,r}$ be the complete bipartite graph with $r$ vertices on each side, and let $\mathrm{ex}(n;K_{r,r})$ be the maximum number of edges in an $n$-vertex graph with no $K_{r,r}$ subgraph. The Kővári–Sós–Turán theorem gives the upper bound $\mathrm{ex}(n;K_{r,r})\ll n^{2-1/r}$. Is this tight — that is, is $$\mathrm{ex}(n;K_{r,r})\gg n^{2-1/r}$$ (so that $\mathrm{ex}(n;K_{r,r})=\Theta(n^{2-1/r})$) for every integer $r\ge 2$?
Acceptance. FULLY RESOLVES: prove $\mathrm{ex}(n;K_{r,r})\gg n^{2-1/r}$ for every $r\ge 2$ — for each $r$, an explicit family of $K_{r,r}$-free $n$-vertex graphs with $\gg n^{2-1/r}$ edges, with proofs of both the edge count and the $K_{r,r}$-freeness — OR prove the bound fails for some $r$ (an upper bound $\mathrm{ex}(n;K_{r,r})=o(n^{2-1/r})$ with proof). ADVANCES: settle a new specific diagonal case $r\ge 4$ (most saliently $r=4$) with an explicit construction and proof, improving on the cases $r\le 3$ known in the background; or raise the best rigorous lower-bound exponent for the diagonal $K_{r,r}$ problem for some $r$, with proof. Deliver the construction as an explicit graph family or algebraic recipe together with proofs of its density and $K_{r,r}$-freeness, or the new bound with its proof.
Background
A problem of Erdős [Er64c, Er67b, Er69, Er71, Er74c, Er75, Er81, Er93]. The upper bound $\mathrm{ex}(n;K_{r,r})\ll n^{2-1/r}$ is due to Kővári–Sós–Turán [KST54]. A matching lower bound is known only for small $r$: for $r=2$, $\mathrm{ex}(n;K_{2,2})=\mathrm{ex}(n;C_4)=(\tfrac12+o(1))n^{3/2}$ (Erdős–Rényi–Sós / Brown, via projective planes; see Erdős #768, erdosproblems.com/768), and for $r=3$ the conjectured lower bound was proved by Brown [Br66] and independently by Erdős–Rényi–Sós [ERS66] via explicit algebraic constructions. The diagonal cases $r\ge 4$ are open. For the off-diagonal problem $K_{r,s}$ with $s$ large ($s>(r-1)!$), the Kollár–Rónyai–Szabó and Alon–Rónyai–Szabó norm-graph constructions give $\mathrm{ex}(n;K_{r,s})\gg n^{2-1/r}$, but these do not settle the balanced $K_{r,r}$ for $r\ge4$. Related to Erdős #147 (erdosproblems.com/147); the hypergraph generalisation is Erdős #1158 (erdosproblems.com/1158). Listed as open on erdosproblems.com/714 (fetched 2026-07-13, status 'open', tagged 'graph theory | turan number'). Attacker's tool: explicit algebraic constructions (norm graphs, projective-norm graphs, incidence structures) that are $K_{r,r}$-free yet reach edge density $\gg n^{2-1/r}$; for a fixed small target such as $r=4$, computer-assisted/algebraic construction and verification of dense $K_{4,4}$-free graphs.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #714 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.