An extremal theorem in the hypercube

Publication date 12 August 2010

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1005.0582, https://eudml.org/doc/233597, http://www.emis.de/journals/EJC/Volume_17/Abstracts/v17i1r111.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Extremal combinatorics (05D99)

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.

Review text

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.

Recommendations

Cited in

(41)

This page was built for publication: An extremal theorem in the hypercube

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q986719)