Skip to main content
Article
Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
European Journal of Combinatorics (2014)
  • József Balogh, University of Illinois, Urbana-Champaign
  • Ping Hu, University of Illinois, Urbana-Champaign
  • Bernard Lidicky, University of Illinois, Urbana-Champaign
  • Hong Liu, University of Illinois, Urbana-Champaign
Abstract
In this paper we modify slightly Razborov’s flag algebra machinery to be suitable for the hypercube. We use this modified method to show that the maximum number of edges of a -cycle-free subgraph of the -dimensional hypercube is at most times the number of its edges. We also improve the upper bound on the number of edges for -cycle-free subgraphs of the -dimensional hypercube from to times the number of its edges. Additionally, we show that if the -dimensional hypercube is considered as a poset then the maximum vertex density of three middle layers in an induced subgraph without 4-cycles is at most 2.15121.
Publication Date
January, 2014
DOI
10.1016/j.ejc.2013.06.003
Publisher Statement
This is a manuscript of an article published as Balogh, József, Ping Hu, Bernard Lidický, and Hong Liu. "Upper bounds on the size of 4-and 6-cycle-free subgraphs of the hypercube." European Journal of Combinatorics 35 (2014): 75-85.. doi: 10.1016/j.ejc.2013.06.003 Copyright © 2013 Elsevier Ltd. 
Citation Information
József Balogh, Ping Hu, Bernard Lidicky and Hong Liu. "Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube" European Journal of Combinatorics Vol. 35 (2014) p. 75 - 85
Available at: http://works.bepress.com/bernard-lidicky/16/