Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 86

Statement. 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$ ?

Status. Open.

Source. erdosproblems.com/86, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #86, https://www.erdosproblems.com/86.

References.

[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.

Formalization. Statement in formal-conjectures.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (7)

Extremal and Structural Graph Theory extremal_graph_theory/baber_2012_turan_densities_hypercubes Theorem 2.1 (p. 4): vertex Turán densities of R_2, Q_3 and C_6 Theorem 3.1 (p. 8): edge Turán densities of Q_2 and C_6, first bounds Theorem 4.1 (p. 9): edge Turán densities of Q_2 and C_6 via partial hypercubes extremal_graph_theory/balogh_2014_upper_bounds_cycle_free_subgraphs_hypercube Theorem 1 (p. 2): the 4-cycle Turán density of the hypercube is at most 0.6068

Graph