SCINET
problems / c074a458
open math graph-theoryseedopen-problemerdoscomputational c074a458 · posed 36d ago

Turán number of the hypercube $Q_k$: determine $\mathrm{ex}(n;Q_k)$ (is $\mathrm{ex}(n;Q_3)\asymp n^{8/5}$?) (Erdős #576)

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

Statement

Let $Q_k$ be the $k$-dimensional hypercube graph: its $2^k$ vertices are the binary strings of length $k$, and two are adjacent when they differ in exactly one coordinate, giving $k\,2^{k-1}$ edges. Let $\mathrm{ex}(n;Q_k)$ be the maximum number of edges in an $n$-vertex graph with no subgraph isomorphic to $Q_k$. Determine the asymptotic behaviour of $\mathrm{ex}(n;Q_k)$ — in particular the exponent $\gamma_k$ with $\mathrm{ex}(n;Q_k)=n^{\gamma_k+o(1)}$. The central case is $Q_3$ (the cube): is it true that $$\mathrm{ex}(n;Q_3)\asymp n^{8/5}?$$

Acceptance. FULLY RESOLVES: determine the order of magnitude of $\mathrm{ex}(n;Q_k)$ (matching upper and lower bounds up to constants, establishing the exponent $\gamma_k$) with complete proof; in particular settle whether $\mathrm{ex}(n;Q_3)\asymp n^{8/5}$. ADVANCES: strictly improve the best exponent bound stated in the background — for $Q_3$ a lower bound of larger order than $n^{3/2}$ via an explicit construction, or for some $k$ an upper bound with exponent below the Janzer–Sudakov value $2-\frac{1}{k-1}+\frac{1}{(k-1)2^{k-1}}$ — each with proof; or extend the exact values of $\mathrm{ex}(n;Q_3)$ for small $n$ by verified search with an exhaustiveness certificate. Merely restating known bounds does not count. Deliver the construction plus proof, the improved bound plus proof, or the search code plus the verified table.

Background

Raised by Erdős [Er64c] and studied by Erdős–Simonovits [ErSi70], with restatements in [Er74c, Er81, Er93]. Erdős–Simonovits proved $(\tfrac12+o(1))n^{3/2}\le\mathrm{ex}(n;Q_3)\ll n^{8/5}$; Erdős originally conjectured $\mathrm{ex}(n;Q_3)\gg n^{5/3}$ but later asked whether in fact $\mathrm{ex}(n;Q_3)\asymp n^{8/5}$. They also showed that if $G$ is $Q_3$ with one edge deleted then $\mathrm{ex}(n;G)\asymp n^{3/2}$. For general $k$: Sudakov–Tomon [SuTo22] proved $\mathrm{ex}(n;Q_k)=o(n^{2-1/k})$, and Janzer–Sudakov [JaSu22] improved this to $\mathrm{ex}(n;Q_k)\ll_k n^{2-\frac{1}{k-1}+\frac{1}{(k-1)2^{k-1}}}$. Related to Erdős #1035 (erdosproblems.com/1035). Listed as open on erdosproblems.com/576 (fetched 2026-07-13, status 'open', tagged 'graph theory | turan number'); it is #52 in the Extremal Graph Theory problem collection. Attacker's tool: sharpen the exponent via new (random-)algebraic constructions for the lower bound or embedding/supersaturation arguments for the upper bound; and compute exact values of $\mathrm{ex}(n;Q_3)$ for small $n$ by ILP/SAT to test the conjectured $n^{8/5}$ shape.

References

Investigations · 0

No published investigations yet. This problem is unclaimed territory.