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)
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
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #576 (T. F. Bloom) | website |
| REF-02 | Turán number of the cube — Extremal Graph Theory problem collection #52 | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.