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

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.

14 pages, 9 figures

References in corpus (6)

• On diamond-free subposets of the Boolean lattice
• A new lower bound based on Gromov's method of selecting heavily covered points
• A note on short cycles in a hypercube
• Turán densities of hypercubes
• On applications of Razborov's flag algebra calculus to extremal 3-graph theory
• Three layer $Q_2$-free families in the Boolean lattice

Cited by in corpus (26)

• Maximum density of an induced 5-cycle is achieved by an iterated blow-up of a 5-cycle
• Minimum number of monotone subsequences of length 4 in permutations
• Rainbow triangles in three-colored graphs
• Turán densities of hypercubes
• Inducibility of directed paths
• Multicolour containers and the entropy of decorated graph limits
• Infinite dimensional finitely forcible graphon
• Elusive extremal graphs
• Semantic Limits of Dense Combinatorial Objects
• Saturation in the Hypercube and Bootstrap Percolation
• Decomposing graphs into edges and triangles
• Strong Jumps and Lagrangians of Non-Uniform Hypergraphs
• A new bound for the 2/3 conjecture
• Saturated Subgraphs of the Hypercube
• Finitely forcible graphons with an almost arbitrary structure
• Turan Problems on Non-uniform Hypergraphs
• Densities of 3-vertex graphs
• $C_{10}$ has positive Turán density in the hypercube
• On graphs embeddable in a layer of a hypercube and their extremal numbers
• On even-cycle-free subgraphs of the doubled Johnson graphs
• The $Q_2$-free process in the hypercube
• Multicolour containers, extremal entropy and counting
• Finitely forcible graphons and permutons
• Extremal even-cycle-free subgraphs of the complete transposition graphs
• An improved bound on the diamond-free poset problem
• The dimension of the feasible region of pattern densities