Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 9, 2010 | Submitted + Erratum + Published
Journal Article Open

An Extremal Theorem in the Hypercube


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.

Additional Information

© 2010 Electronic Journal of Combinatorics. Submitted May 4, 2010; accepted Jul 18, 2010; published Aug 9, 2010. Conlon supported by a Junior Research Fellowship at St John's College. I would like to thank Eoin Long for reading carefully through an earlier version of this note.

Attached Files

Published - EJC17.R111.pdf

Submitted - 1005.0582.pdf

Erratum - HyperCycleErratum.pdf


Files (359.3 kB)
Name Size Download all
123.7 kB Preview Download
118.5 kB Preview Download
117.1 kB Preview Download

Additional details

August 19, 2023
October 18, 2023