New Turán densities for 3-graphs

zbMATH Open1244.05122arXiv1110.4287MaRDI QIDQ426895FDOQ426895

Authors: Rahil Baber, John Talbot 

Publication date: 12 June 2012

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: If $mathcalF$ is a family of graphs then the Tur'an density of $mathcalF$ is determined by the minimum chromatic number of the members of $mathcalF$. 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 $mathbbQ$ or in the case of irrational Tur'an densities over an appropriate quadratic extension of $mathbbQ$.

Full work available at URL: https://arxiv.org/abs/1110.4287

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Turán \(H\)-densities for 3-graphs
• On the Turán density of \(\{1, 3\}\)-hypergraphs
• On Turán densities of small triple graphs
• scientific article; zbMATH DE number 3924792
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
• scientific article; zbMATH DE number 4200237
• On the density of non-simple 3-planar graphs
• A note on the structure of Turán densities of hypergraphs
• An exact Turán result for tripartite 3-graphs
• The vertex Turán density in 3-ary \(n\)-cubes

zbMATH Keywords

hypergraphTurán problem

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Hypergraphs (05C65)

Cited In (25)

• Tournaments, 4-uniform hypergraphs, and an exact extremal result
• On local Turán problems
• An extension of the Motzkin-Straus theorem to non-uniform hypergraphs and its applications
• Turán problems on non-uniform hypergraphs
• On the algebraic and topological structure of the set of Turán densities
• On possible Turán densities
• Triangle-degrees in graphs and tetrahedron coverings in 3-graphs
• Hypergraph Turán densities can have arbitrarily large algebraic degree
• An irrational Turán density via hypergraph Lagrangian densities
• Turán \(H\)-densities for 3-graphs
• The codegree threshold for 3-graphs with independent neighborhoods
• An exact Turán result for tripartite 3-graphs
• On Turán densities of small triple graphs
• Lagrangian-perfect hypergraphs
• A hypergraph Turán theorem via Lagrangians of intersecting families
• A class of graphs of zero Turán density in a hypercube
• Lagrangian densities of 4-uniform matchings and degree stability of extremal hypergraphs
• On graphs embeddable in a layer of a hypercube and their extremal numbers
• Stability of the potential function
• Minimum Number of Monotone Subsequences of Length 4 in Permutations
• On Density of \(\boldsymbol{\mathbb{Z}_3}\) -Flow-Critical Graphs
• The Turán density of triple systems is not principal
• An irrational Lagrangian density of a single hypergraph
• Almost similar configurations
• Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs

Uses Software

• CSDP
• SDPA
• DensityChecker
• ExactDensityBounder

This page was built for publication: New Turán densities for 3-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q426895)