New Turán densities for 3-graphs
type: Item
instance of: scholarly article
title: New Turán densities for 3-graphs
zbMATH Open document ID: 1244.05122
author: Rahil Baber
author: John Talbot
published in: The Electronic Journal of Combinatorics
publication date: 2012-06-12T00:00:00Z
full work available at URL: https://arxiv.org/abs/1110.4287
full work available at URL: v19i2p22
review text: Summary: 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\). \textit{A. A. Razborov} [``On 3-hypergraphs with forbidden 4-vertex configurations'', SIAM J. Discrete Math. 24, No. 3, 946--963 (2010; Zbl 1223.05204)] 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}\).
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6045715
zbMATH Keywords: hypergraph
zbMATH Keywords: Turán problem
describes a project that uses: SDPA
describes a project that uses: CSDP
describes a project that uses: DensityChecker
describes a project that uses: ExactDensityBounder
MaRDI profile type: Publication
arXiv ID: 1110.4287
Recommended article: Turán \(H\)-densities for 3-graphs
Recommended article: On the Turán density of \(\{1, 3\}\)-hypergraphs
Recommended article: On Turán densities of small triple graphs
Recommended article: Q3699700
Recommended article: Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
Recommended article: Q3348933
Recommended article: On the Density of Non-simple 3-Planar Graphs
Recommended article: A note on the structure of Turán densities of hypergraphs
Recommended article: An exact Turán result for tripartite 3-graphs
Recommended article: The vertex Turán density in 3-ary \(n\)-cubes
description: scientific article; zbMATH DE number 6045715