Applications of the Semi-Definite Method to the Turán Density Problem for 3-Graphs
- 7 December 2012
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 22 (1) , 21-54
Abstract
In this paper, we prove several new Turán density results for 3-graphs with independent neighbourhoods. We show: \begin{align*} \pi (K_4^-, C_5, F_{3,2})=12/49, \pi (K_4^-, F_{3,2})=5/18 \textrm {and} \pi (J_4, F_{3,2})=\pi (J_5, F_{3,2})=3/8, \end{align*} whereJtis the 3-graph consisting of a single vertexxtogether with a disjoint setAof sizetand all $\binom{|A|}{2}$ 3-edges containingx. We also prove two Turán density results where we forbid certain induced subgraphs: \begin{align*} \pi (F_{3,2}, \textrm { induced }K_4^-)=3/8 \textrm {and} \pi (K_5, 5\textrm {-set spanning exactly 8 edges})=3/4. \end{align*} The latter result is an analogue forK5of Razborov's result that \begin{align*} \pi (K_4, 4\textrm {-set spanning exactly 1 edge})=5/9. \end{align*} We give several new constructions, conjectures and bounds for Turán densities of 3-graphs which should be of interest to researchers in the area. Our main tool is ‘Flagmatic’, an implementation of Razborov's semi-definite method, which we are making publicly available. In a bid to make the power of Razborov's method more widely accessible, we have tried to make Flagmatic as user-friendly as possible, hoping to remove thereby the major hurdle that needs to be cleared before using the semi-definite method. Finally, we spend some time reflecting on the limitations of our approach, and in particular on which problems we may be unable to solve. Our discussion of the ‘complexity barrier’ for the semi-definite method may be of general interest.
Keywords
This publication has 29 references indexed in Scilit:
- Turán $H$-Densities for 3-GraphsThe Electronic Journal of Combinatorics, 2012
- New Turán Densities for 3-GraphsThe Electronic Journal of Combinatorics, 2012
- More Constructions for Turán's (3,4)-ConjectureThe Electronic Journal of Combinatorics, 2008
- On the Turán Number of Triple SystemsJournal of Combinatorial Theory, Series A, 2002
- The Turan Density of Triple Systems Is Not PrincipalJournal of Combinatorial Theory, Series A, 2002
- The Maximum Size of 3-Uniform Hypergraphs Not Containing a Fano PlaneJournal of Combinatorial Theory, Series B, 2000
- What we know and what we do not know about Turán numbersGraphs and Combinatorics, 1995
- Method for construction of (3, 4)-graphsMathematical Notes, 1988
- A new generalization of the Erdős-Ko-Rado theoremCombinatorica, 1983
- On an open problem of Paul Turán concerning 3-graphs1983