Publication at Faculty of Mathematics and Physics |
2014
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 root(2) - 1 to 0.3755 times the number of its edges.