OPENHARDgraph theoryextremal graph theory
Is it true that every subgraph of $Q_n$ (the $n$-dimensional hypercube) with $\geq (\frac{1}{2}+o(1))n2^{n-1}$ many edges contains a $C_4$?
Notes: Best upper bound: f(n) <= 0.60318 * n * 2^{n-1} by Baber. Best lower bound: f(n) >= (1/2 + c/sqrt(n)) * n * 2^{n-1} by Brass, Harborth, and Nienborg.
AI Status: NONE · 0 total attempts