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

Abstrakt

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.

Klíčová slova

• hypercube
• subgraphs