Name
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*} where Jt is the 3-graph consisting of a single vertex x together with a disjoint set A of size t and all $\binom{|A|}{2}$ 3-edges containing x. 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 for K5 of 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1017/S0963548312000508 | Combinatorics, Probability & Computing |
Keywords | Field | DocType |
pi j_4,n density result,new tur,pi j_5,certain induced subgraphs,n density,semi-definite method,pi f,pi k_5,n density problem,pi k_4,mathematics | Discrete mathematics,Graph,Combinatorics,Disjoint sets,Vertex (geometry),Clearance,Mathematics | Journal |
Volume | Issue | ISSN |
22 | 1 | 0963-5483 |
Citations | PageRank | References |
13 | 0.86 | 20 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Victor Falgas-Ravry | 1 | 28 | 7.46 |
| Emil R. Vaughan | 2 | 40 | 3.49 |