New Turán densities for 3-graphs

Abstract

If $\mathcal{F}$ is a family of graphs then the Turán density of $\mathcal{F}$ is determined by the minimum chromatic number of the members of $\mathcal{F}$. The situation for Turán densities of 3-graphs is far more complex and still very unclear. Our aim in this paper is to present new exact Turán densities for individual and finite families of 3-graphs, in many cases we are also able to give corresponding stability results. As well as providing new examples of individual 3-graphs with Turán densities equal to 2/9,4/9,5/9 and 3/4 we also give examples of irrational Turán densities for finite families of 3-graphs, disproving a conjecture of Chung and Graham. (Pikhurko has independently disproved this conjecture by a very different method.) A central question in this area, known as Turán's problem, is to determine the Turán density of $K_4^{(3)}=\{123,124,134,234\}$. Turán conjectured that this should be 5/9. Razborov [On 3-hypergraphs with forbidden 4-vertex configurations, in SIAM J. Disc. Math. 24 (2010), 946-963] showed that if we consider the induced Turán problem forbidding $K_4^{(3)}$ and $E_1$, the 3-graph with 4 vertices and a single edge, then the Turán density is indeed 5/9. We give some new non-induced results of a similar nature, in particular we show that $\pi (K_4^{(3)},H)=5/9$ for a 3-graph $H$ satisfying $\pi (H)=3/4$. We end with a number of open questions focusing mainly on the topic of which values can occur as Turán densities. Our work is mainly computational, making use of Razborov's flag algebra framework. However all proofs are exact in the sense that they can be verified without the use of any floating point operations. Indeed all verifying computations use only integer operations, working either over $\mathbb{Q}$ or in the case of irrational Turán densities over an appropriate quadratic extension of $\mathbb{Q}$.

arXiv comment17 pages, 4 figures. Additional files: C++ source code for proof verification and generation; 39 proof files. Revised to include stability theorems