Problem Statement
Let $Q_k$ be the $k$-dimensional hypercube graph (so that $Q_k$ has $2^k$ vertices and $k2^{k-1}$ edges). Determine the behaviour of\[\mathrm{ex}(n;Q_k).\]
Categories:
Graph Theory Turan Number
Progress
Erdős and Simonovits [ErSi70] proved that\[(\tfrac{1}{2}+o(1))n^{3/2}\leq \mathrm{ex}(n;Q_3) \ll n^{8/5}.\](In [ErSi70] they mention that Erdős had originally conjectured that $ \mathrm{ex}(n;Q_3)\gg n^{5/3}$.) Erdős and Simonovits also proved that, if $G$ is the graph $Q_3$ with a missing edge, then $\mathrm{ex}(n;G)\asymp n^{3/2}$.In [Er74c], [Er81], and [Er93] Erdős asked whether it is $\mathrm{ex}(n;Q_3)\asymp n^{8/5}$.
A theorem of Sudakov and Tomon [SuTo22] implies\[\mathrm{ex}(n;Q_k)=o(n^{2-\frac{1}{k}}).\]Janzer and Sudakov [JaSu22] have improved this to\[\mathrm{ex}(n;Q_k)\ll_k n^{2-\frac{1}{k-1}+\frac{1}{(k-1)2^{k-1}}}.\]See also the entry in the graphs problem collection and [1035].
Source: erdosproblems.com/576 | Last verified: January 15, 2026