Turán Problem for $10$-Cycles in the Hypercube

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For $d\geq1$, the hypercube $Q_d$ has vertices $\{0,1\}^d$ and edges joining strings that differ in one coordinate. A copy of $C_{10}$ is an ordinary, not necessarily induced, cycle on ten distinct vertices. Define \[\operatorname{ex}(Q_d,C_{10})=\max\{|E(F)|:F\subseteq Q_d\text{ is a spanning subgraph with no }C_{10}\}.\]

Statement recorded in the supplied source.

Find sharp upper and lower bounds on $\operatorname{ex}(Q_d,C_{10})$, in particular its asymptotic size compared with $|E(Q_d)|=d2^{d-1}$. The historical qualitative question asks whether $\operatorname{ex}(Q_d,C_{10})=o(d2^{d-1})$ as $d\to\infty$. [S2]

Short English statement

Determine how many edges a hypercube subgraph can retain while avoiding every ten-cycle, including the historical question of whether its edge density must tend to zero.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3056 (OPG-60006). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Erdos, Paul, Turán Problem for $10$-Cycles in the Hypercube, Open Problem Garden, node 60006. Complete problem, discussion and bibliography (including mathematical image alt text). https://www.openproblemgarden.org/op/turan_problem_for_10_cycles_in_the_hypercube.