Mathematics – Combinatorics
Scientific paper
2011-10-19
Mathematics
Combinatorics
16 pages, 4 figures. Additional files: C++ source code for proof verification and generation; 39 proof files. Revised to inclu
Scientific paper
If $\mathcal{F}$ is a family of graphs then the Tur\'an density of $\mathcal{F}$ is determined by the minimum chromatic number of the members of $\mathcal{F}$. The situation for Tur\'an densities of 3-graphs is far more complex and still very unclear. Our aim in this paper is to present some new exact Tur\'an densities for individual and finite families of 3-graphs. As well as providing new examples of individual 3-graphs with Tur\'an densities equal to 2/9, 4/9, 5/9 and 3/4 we also give examples of irrational Tur\'an densities for finite families, disproving a conjecture of Chung and Graham. (Pikhurko has independently disproved this conjecture by a different method.) A central question in this area, known as Tur\'an's problem, is to determine the Tur\'an density of $K_4^{(3)}=\{123, 124, 134, 234\}$. Tur\'an conjectured that this should be 5/9. Razborov showed that if we consider the induced Tur\'an problem forbidding $K_4^{(3)}$ and $G_1$, the 3-graph with 4 vertices and a single edge, then the Tur\'an 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\'an densities. Our work is mainly computational: making use of Razborov's flag algebra framework. However all our 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\'an densities over an appropriate quadratic extension of $\mathbb{Q}$.
Baber Rahil
Talbot John
No associations
LandOfFree
New Turán densities for 3-graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with New Turán densities for 3-graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Turán densities for 3-graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-597421