CaltechAUTHORS
  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. https://resolver.caltech.edu/CaltechAUTHORS:20190819-163059223

[img] PDF - Published Version
See Usage Policy.

114Kb
[img] PDF - Erratum
See Usage Policy.

120Kb
[img] PDF - Submitted Version
See Usage Policy.

115Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20190819-163059223

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.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r111PublisherArticle
https://arxiv.org/abs/1005.0582arXivDiscussion Paper
ORCID:
AuthorORCID
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.
Funders:
Funding AgencyGrant Number
St. John's College, CambridgeUNSPECIFIED
Classification Code:05C35, 05C38, 05D99
Record Number:CaltechAUTHORS:20190819-163059223
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20190819-163059223
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:98014
Collection:CaltechAUTHORS
Deposited By: Melissa Ray
Deposited On:19 Aug 2019 23:41
Last Modified:03 Oct 2019 21:37

Repository Staff Only: item control page