Problem 86

Let $Q_n$ be the $n$ -dimensional hypercube graph (so that $Q_n$ has $2^n$ vertices and $n2^{n-1}$ edges). Is it true that every subgraph of $Q_n$ with

\geq \left(\frac{1}{2}+o(1)\right)n2^{n-1}

many edges contains a $C_4$ ?

Source: erdosproblems.com/86

Graph theory

Wiki page

Status

Open

No claim settles this problem.

BHLL14: Balogh, József and Hu, Ping and Lidický, Bernard and Liu, Hong, Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube. European J. Combin. (2014), 75-85.
BHN95: Brass, Peter and Harborth, Heiko and Nienborg, Hauke, On the maximum number of edges in a $C_4$ -free subgraph of $Q_n$ . J. Graph Theory (1995), 17-23.
Ba12b: R. Baber, Turán densities of hypercubes. arXiv:1201.3587 (2012).
Er91: Erdős, P., Problems and results in combinatorial analysis and combinatorial number theory. Graph theory, combinatorics, and applications, Vol. 1 (Kalamazoo, MI, 1988) (1991), 397-406.

Problem 86

Status

Proof claims

Discussion