Show that every (1/2+ľ)|E(ő_(n))| edges of the n-cube ő_(n) contains a C_(4) when n is sufficiently large

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.

The hypercube graph $Q_n$ has vertices $\{0,1\}^n$ and edges between binary strings differing in exactly one coordinate; $|E(Q_n)|=n2^{n-1}$. A subgraph may select any subset of these edges. A $4$-cycle means a simple cycle of length four. Write $\operatorname{ex}(Q_n,C_4)=\max\{|E(G)|:G\subseteq Q_n\text{ contains no }4\text{-cycle}\}$.

Statement recorded in the supplied source.

For every $\varepsilon>0$, does there exist $n_0(\varepsilon)$ such that for every $n\geq n_0(\varepsilon)$, each subgraph $G\subseteq Q_n$ with $|E(G)|\geq(\tfrac12+\varepsilon)|E(Q_n)|$ contains a $4$-cycle? Equivalently, is \[\lim_{n\to\infty}\frac{\operatorname{ex}(Q_n,C_4)}{|E(Q_n)|}=\frac12?\] [S2]

Short English statement

Does every fixed edge density above one half force a four-cycle in a sufficiently large hypercube?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3100018 (AMR-030-0018). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Rahil Baber, Turan Densities of Hypercubes (2012), section 1, definition of edge Turan density and Erdos conjecture, pp. 1--2. https://arxiv.org/abs/1201.3587.