An Extremal Theorem in the Hypercube

Abstract

The hypercube Q_n is the graph whose vertex set is {0, 1}^n and where two vertices are adjacent if they differ in exactly one coordinate. For any subgraph H of the cube, let ex(Q_(n), H) be the maximum number of edges in a subgraph of Q_n which does not contain a copy of H. We find a wide class of subgraphs H, including all previously known examples, for which ex(Q_(n), H) = o(e(Q_n)). In particular, our method gives a unified approach to proving that ex(Q_(n), C_(2t)) = o(e(Q_n)) for all t ≥ 4 other than 5.

Files

Additional details