Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube

József Balogh, Ping Hu, Bernard Lidický, Hong Liu

Research output: Contribution to journalArticlepeer-review

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 4-cycle-free subgraph of the n-dimensional hypercube is at most 0.6068 times the number of its edges. We also improve the upper bound on the number of edges for 6-cycle-free subgraphs of the n-dimensional hypercube from 2-1 to 0.3755 times the number of its edges. Additionally, we show that if the n-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(nimg src=⌊n/2⌋).

Original languageEnglish (US)
Pages (from-to)75-85
Number of pages11
JournalEuropean Journal of Combinatorics
Volume35
DOIs
StatePublished - Jan 2014

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube'. Together they form a unique fingerprint.

Cite this