Turán densities of hypercubes

Abstract

In this paper we describe a number of extensions to Razborov's semidefinite flag algebra method. We will begin by showing how to apply the method to significantly improve the upper bounds of edge and vertex Turán density type results for hypercubes. We will then introduce an improvement to the method which can be applied in a more general setting, notably to 3-uniform hypergraphs, to get a new upper bound of 0.5615 for $\pi (K_4^3)$. For hypercubes we improve Thomason and Wagner's result on the upper bound of the edge Turán density of a 4-cycle free subcube to 0.60318 and Chung's result on forbidding 6-cycles to 0.36577. We also show that the upper bound of the vertex Turán density of $\mc{Q}_3$ can be improved to 0.76900, and that the vertex Turán density of $\mc{Q}_3$ with one vertex removed is precisely 2/3.

18 pages, 4 figures. Additional files: 3 C++ source code files, and 8 data text files for proof verification. Revised to include a new bound for π(K_4^3), improved bounds for the hypercube edge Turán density results, and a new extension of Razborov's method

References in corpus (2)

• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• On applications of Razborov's flag algebra calculus to extremal 3-graph theory

Cited by in corpus (11)

• Upper bounds on the size of 4- and 6-cycle-free subgraphs of the hypercube
• 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
• Multicolour containers and the entropy of decorated graph limits
• Infinite dimensional finitely forcible graphon
• A new bound for the 2/3 conjecture
• Finitely forcible graph limits are universal
• Finitely forcible graphons and permutons
• Multicolour containers, extremal entropy and counting
• A solution to the 2/3 conjecture