×

zbMATH — the first resource for mathematics

Applications of the semi-definite method to the Turán density problem for 3-graphs. (English) Zbl 1257.05077
Summary: In this paper, we prove several new Turán density results for 3-graphs with independent neighbourhoods. We show:
\[ \pi(K_{4}^{-}, C_{5}, F_{3,2})=12/49,\;\;\pi(K_{4}^{-}, F_{3,2})=5/18\;\text{and}\;\pi(J_{4}, F_{3,2})=\pi(J_{5}, F_{3,2})=3/8, \]
where \(J_t\) is the 3-graph consisting of a single vertex \(x\) together with a disjoint set \(A\) of size \(t\) and all \(|A| \choose 2\) 3-edges containing \(x\). We also prove two Turán density results where we forbid certain induced subgraphs:
\[ \pi(F_{3,2},\text{induced}\;K_{4}^{-})=3/8\;\text{and}\;\pi(K_{5},5-\text{set spanning exactly 8 edges})=3/4. \]
The latter result is an analogue for \(K_5\) of Razborov’s result that
\[ \pi(K_{4},4-\text{set spanning exactly 1 edge})=5/9. \]
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.

MSC:
05C42 Density (toughness, etc.)
05D05 Extremal set theory
05C65 Hypergraphs
68R10 Graph theory (including graph drawing) in computer science
Software:
Flagmatic
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] DOI: 10.1016/j.disc.2010.07.002 · Zbl 1208.05059 · doi:10.1016/j.disc.2010.07.002
[2] DOI: 10.1137/090747476 · Zbl 1223.05204 · doi:10.1137/090747476
[3] DOI: 10.1016/j.disc.2007.08.040 · Zbl 1165.05022 · doi:10.1016/j.disc.2007.08.040
[4] DOI: 10.1007/BF02579190 · Zbl 0529.05001 · doi:10.1007/BF02579190
[5] DOI: 10.1007/BF01158925 · Zbl 0766.05061 · doi:10.1007/BF01158925
[6] DOI: 10.1016/0012-365X(74)90105-8 · Zbl 0291.05114 · doi:10.1016/0012-365X(74)90105-8
[7] DOI: 10.1090/S0002-9904-1946-08715-7 · Zbl 0063.01277 · doi:10.1090/S0002-9904-1946-08715-7
[8] DOI: 10.1006/jcta.2002.3285 · Zbl 1013.05039 · doi:10.1006/jcta.2002.3285
[9] DOI: 10.1006/jctb.1999.1938 · Zbl 1027.05073 · doi:10.1006/jctb.1999.1938
[10] DOI: 10.2178/jsl/1203350785 · Zbl 1146.03013 · doi:10.2178/jsl/1203350785
[11] DOI: 10.1017/S0963548310000222 · Zbl 1213.05184 · doi:10.1017/S0963548310000222
[12] DOI: 10.1080/10556789908805765 · Zbl 0973.90524 · doi:10.1080/10556789908805765
[13] DOI: 10.1017/S0963548311000319 · Zbl 1293.05381 · doi:10.1017/S0963548311000319
[14] 46th Annual IEEE Symposium on Foundations of Computer Science, 2005 pp 429– (2005)
[15] DOI: 10.1007/BF01929486 · Zbl 0839.05050 · doi:10.1007/BF01929486
[16] Proc. 35th Annual ACM Symposium on Theory of Computing pp 700– (2003)
[17] DOI: 10.1007/BF02579317 · Zbl 0502.05046 · doi:10.1007/BF02579317
[18] DOI: 10.1017/S0963548311000678 · Zbl 1242.05131 · doi:10.1017/S0963548311000678
[19] DOI: 10.1016/j.jctb.2012.04.001 · Zbl 1252.05093 · doi:10.1016/j.jctb.2012.04.001
[20] DOI: 10.1017/S0963548305006905 · Zbl 1079.05062 · doi:10.1017/S0963548305006905
[21] Electron. J. Combin. 15 pp R137– (2008)
[22] DOI: 10.1016/0012-365X(84)90058-X · Zbl 0538.05050 · doi:10.1016/0012-365X(84)90058-X
[23] DOI: 10.1007/s00493-009-2320-x · Zbl 1212.05133 · doi:10.1007/s00493-009-2320-x
[24] DOI: 10.1134/S0081543811060150 · Zbl 1296.05099 · doi:10.1134/S0081543811060150
[25] DOI: 10.1006/jcta.2002.3284 · Zbl 1009.05074 · doi:10.1006/jcta.2002.3284
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.