An extremal theorem in the hypercube (Q986719): Difference between revisions

Summary: 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 \(\text{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 \(\text{ex}(Q_n,H)= o(e(Q_n))\). In particular, our method gives a unified approach to proving that \(\text{ex}(Q_n,C_{2t})= o(e(Q_n))\) for all \(t\geq 4\) other than 5.