Department of
Applied
Mathematics

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

Bernard Lidickż

University of Illinois at Urbana-Champaign

Abstract

We present a slight modification of 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. Although it is far from the bound 0.5 conjectured by Erdos, the previous improvement was from 0.62284 to 0.6203. We also improve the upper bound on the number of edges for 6-cycle-free subgraphs of the n-dimensional hypercube from sqrt{2}-1 to 0.3755 times the number of its edges. The best known lower bound in this case is 1/3.

This is a joint work with József Balogh, Ping Hu and Hong Liu.