A Caltech Library Service

An Extremal Theorem in the Hypercube

Conlon, David (2010) An Extremal Theorem in the Hypercube. Electronic Journal of Combinatorics, 17 . Art. No. R111. ISSN 1077-8926.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Erratum
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Conlon, David0000-0001-5899-1829
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.
Funding AgencyGrant Number
St. John's College, CambridgeUNSPECIFIED
Classification Code:05C35, 05C38, 05D99
Record Number:CaltechAUTHORS:20190819-163059223
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98014
Deposited By: Melissa Ray
Deposited On:19 Aug 2019 23:41
Last Modified:03 Oct 2019 21:37

Repository Staff Only: item control page