UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

New Turan densities for 3-graphs

Baber, R; Talbot, J; (2012) New Turan densities for 3-graphs. The Electronic Journal of Combinatorics , 19 (2) pp. 1-21.

Full text not available from this repository.


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 new exact Tur\'an 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\'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 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\'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 [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\'an problem forbidding $K_4^{(3)}$ and $E_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 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}$.

Type: Article
Title: New Turan densities for 3-graphs
Publisher version: http://www.combinatorics.org/ojs/index.php/eljc/ar...
Keywords: Turan problems, Hypergraphs
UCL classification: UCL > School of BEAMS
UCL > School of BEAMS > Faculty of Maths and Physical Sciences
URI: http://discovery.ucl.ac.uk/id/eprint/1361079
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item