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

preprint2012arXivOpen access

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 the square root of 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 times n choose n/2.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.