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⌋).
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics