Is the Turán number of $K_t(r)$ (complete $t$-partite $t$-uniform) at least $n^{t-r^{1-t}-o(1)}$? (Erdős #1158)
Statement
Let $K_t(r)$ denote the complete $t$-partite $t$-uniform hypergraph with $r$ vertices in each of its $t$ classes (its edges are all $r^t$ transversals, one vertex chosen from each class). Let $\mathrm{ex}_t(n,K_t(r))$ be the maximum number of edges in a $t$-uniform hypergraph on $n$ vertices that contains no copy of $K_t(r)$. Is it true that $$\mathrm{ex}_t(n,K_t(r))\ge n^{t-r^{1-t}-o(1)}$$ for all $t,r\ge 2$?
Acceptance. FULLY RESOLVES: prove $\mathrm{ex}_t(n,K_t(r))\ge n^{t-r^{1-t}-o(1)}$ for all $t,r\ge 2$ (matching Erdős's upper bound and fixing the exponent), with a complete proof; OR disprove it by showing the true lower exponent is strictly smaller for some pair $(t,r)$. ADVANCES (each independently checkable): establish the matching lower bound for a new specific pair $(t,r)$ beyond the known $t=2,\ r\in\{2,3\}$ (for example $t=2,\ r=4$, or any $t\ge 3$) via an explicit construction, with proof; OR improve the general lower-bound exponent for a family of $(t,r)$ strictly beyond the bound stated in the background; OR provide computer-verified extremal numbers $\mathrm{ex}_t(n,K_t(r))$ for small $n$ that support or refute the conjectured exponent, with reproducible code and a certificate. Deliver the proof, the explicit extremal construction, or the search code plus certified values.
Background
Recorded as [Va99, 3.65]; this is the $t$-uniform (Erdős 'box') generalisation of the Kővári–Sós–Turán / Zarankiewicz problem. Erdős [Er64f] proved the two-sided bound $n^{t-O(r^{1-t})}\le \mathrm{ex}_t(n,K_t(r))\ll n^{t-r^{1-t}}$, so the upper exponent $t-r^{1-t}$ is known and the question is whether the lower bound matches it up to the $o(1)$ in the exponent (equivalently, whether $\mathrm{ex}_t(n,K_t(r))=n^{t-r^{1-t}+o(1)}$). The matching lower bound — hence the exact exponent — is currently established only for $t=2$ with $2\le r\le 3$, i.e. the graph cases $K_{2,2}$ and $K_{3,3}$, via finite-geometry and norm-graph constructions. The $t=2$ (bipartite Zarankiewicz) case is erdosproblems #714. Attacker's tool: explicit algebraic constructions (norm graphs, projective and random algebraic hypergraphs) to push lower bounds toward the conjectured exponent, together with computer search over small $t$-uniform hypergraphs to certify extremal densities and to test candidate constructions. Listed as open on erdosproblems.com/1158 (fetched 2026-07-13, status 'open').
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1158 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.