An extremal theorem in the hypercube (Q986719)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An extremal theorem in the hypercube |
scientific article |
Statements
An extremal theorem in the hypercube (English)
0 references
12 August 2010
0 references
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.
0 references