Permanent problem IDPPL 082
Graph theory
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 ≥ ((1/2)+o(1))n2^(n-1) many edges contains a C_4?
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 ≥ ((1/2)+o(1))n2^(n-1) many edges contains a C_4?
A solution must appear in a reputable journal, with documentation that Erdős offered the displayed amount. Claims are administered by the Combinatorics Foundation; erdosproblems.com does not pay awards.