{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T07:39:34Z","timestamp":1780385974804,"version":"3.54.1"},"reference-count":42,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2012,12,7]],"date-time":"2012-12-07T00:00:00Z","timestamp":1354838400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,1]]},"abstract":"<jats:p>In this paper, we prove several new Tur\u00e1n density results for 3-graphs with independent neighbourhoods. We show:<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548312000508_eqnU1\"\/><jats:tex-math>\\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*}<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>where<jats:italic>J<\/jats:italic><jats:sub><jats:italic>t<\/jats:italic><\/jats:sub>is the 3-graph consisting of a single vertex<jats:italic>x<\/jats:italic>together with a disjoint set<jats:italic>A<\/jats:italic>of size<jats:italic>t<\/jats:italic>and all<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548312000508_inline1\"\/><jats:tex-math>$\\binom{|A|}{2}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>3-edges containing<jats:italic>x<\/jats:italic>. We also prove two Tur\u00e1n density results where we forbid certain induced subgraphs:<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548312000508_eqnU2\"\/><jats:tex-math>\\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*}<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>The latter result is an analogue for<jats:italic>K<\/jats:italic><jats:sub>5<\/jats:sub>of Razborov's result that<jats:disp-formula-group><jats:disp-formula><jats:alternatives><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" orientation=\"portrait\" mime-subtype=\"gif\" mimetype=\"image\" position=\"float\" xlink:type=\"simple\" xlink:href=\"S0963548312000508_eqnU3\"\/><jats:tex-math>\\begin{align*} \\pi (K_4, 4\\textrm {-set spanning exactly 1 edge})=5\/9. \\end{align*}<\/jats:tex-math><\/jats:alternatives><\/jats:disp-formula><\/jats:disp-formula-group>We give several new constructions, conjectures and bounds for Tur\u00e1n densities of 3-graphs which should be of interest to researchers in the area. Our main tool is \u2018Flagmatic\u2019, 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 \u2018complexity barrier\u2019 for the semi-definite method may be of general interest.<\/jats:p>","DOI":"10.1017\/s0963548312000508","type":"journal-article","created":{"date-parts":[[2012,12,7]],"date-time":"2012-12-07T15:43:24Z","timestamp":1354895004000},"page":"21-54","source":"Crossref","is-referenced-by-count":37,"title":["Applications of the Semi-Definite Method to the Tur\u00e1n Density Problem for 3-Graphs"],"prefix":"10.1017","volume":"22","author":[{"given":"VICTOR","family":"FALGAS-RAVRY","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"EMIL R.","family":"VAUGHAN","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2012,12,7]]},"reference":[{"key":"S0963548312000508_ref38","doi-asserted-by":"publisher","DOI":"10.1134\/S0081543811060150"},{"key":"S0963548312000508_ref37","doi-asserted-by":"publisher","DOI":"10.1137\/090747476"},{"key":"S0963548312000508_ref36","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1203350785"},{"key":"S0963548312000508_ref35","unstructured":"Pikhurko O. (2012) On possible Tur\u00e1n densities. arXiv:1204.4423"},{"key":"S0963548312000508_ref31","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2002.3284"},{"key":"S0963548312000508_ref29","unstructured":"Mubayi D. Personal communication."},{"key":"S0963548312000508_ref28","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579317"},{"key":"S0963548312000508_ref27","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000678"},{"key":"S0963548312000508_ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2012.04.001"},{"key":"S0963548312000508_ref26","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139004114.004"},{"key":"S0963548312000508_ref21","doi-asserted-by":"crossref","first-page":"R137","DOI":"10.37236\/861","article-title":"More constructions for Tur\u00e1n's (3, 4)-conjecture","volume":"15","author":"Frohmader","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S0963548312000508_ref13","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1999.1938"},{"key":"S0963548312000508_ref11","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805765"},{"key":"S0963548312000508_ref9","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(74)90105-8"},{"key":"S0963548312000508_ref8","doi-asserted-by":"publisher","DOI":"10.1006\/jcta.2002.3285"},{"key":"S0963548312000508_ref4","first-page":"429","volume-title":"46th Annual IEEE Symposium on Foundations of Computer Science, 2005","author":"Alon","year":"2005"},{"key":"S0963548312000508_ref3","first-page":"700","volume-title":"Proc. 35th Annual ACM Symposium on Theory of Computing","author":"Alon","year":"2003"},{"key":"S0963548312000508_ref1","unstructured":"JSON standard. http:\/\/tools.ietf.org\/html\/rfc4627."},{"key":"S0963548312000508_ref32","unstructured":"Pikhurko O. Personal communication."},{"key":"S0963548312000508_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548310000222"},{"key":"S0963548312000508_ref41","unstructured":"Simonovits M. (1968) A method for solving extremal problems in graph theory, stability problems. In Theory of Graphs: Proc. Colloq., Tihany, 1966, Academic, pp. 279\u2013319."},{"key":"S0963548312000508_ref16","unstructured":"Falgas-Ravry V. and Vaughan E. R. (2011) On applications of Razborov's flag algebra calculus to extremal 3-graph theory. arXiv:1110.1623"},{"key":"S0963548312000508_ref17","doi-asserted-by":"crossref","unstructured":"Falgas-Ravry V. and Vaughan E. R. (2012) Tur\u00e1n H-densities for 3-graphs. Electron. J. Combin. 19 #40.","DOI":"10.37236\/2733"},{"key":"S0963548312000508_ref33","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2010.07.002"},{"key":"S0963548312000508_ref23","doi-asserted-by":"crossref","unstructured":"Goldberg D. (1991) What every computer scientist should know about floating-point arithmetic. ACM Computing Surveys (CSUR) 23 5\u201348.","DOI":"10.1145\/103162.103163"},{"key":"S0963548312000508_ref30","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2007.08.040"},{"key":"S0963548312000508_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000319"},{"key":"S0963548312000508_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-5438-2_9"},{"key":"S0963548312000508_ref40","doi-asserted-by":"publisher","DOI":"10.1007\/BF01929486"},{"key":"S0963548312000508_ref34","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.03.006"},{"key":"S0963548312000508_ref25","unstructured":"Hirst J. (2011) The inducibility of graphs on four vertices. arXiv:1109.1592"},{"key":"S0963548312000508_ref2","unstructured":"The on-line encyclopedia of integer sequences. http:\/\/oeis.org."},{"key":"S0963548312000508_ref18","doi-asserted-by":"publisher","DOI":"10.1007\/BF01158925"},{"key":"S0963548312000508_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579190"},{"key":"S0963548312000508_ref15","unstructured":"Falgas-Ravry V. and Vaughan E. R. A note on stability and the semi-definite method. Preprint."},{"key":"S0963548312000508_ref20","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(84)90058-X"},{"key":"S0963548312000508_ref42","unstructured":"Vaughan E. R. (2012) Flagmatic User's Guide, version 1.0. http:\/\/maths.qmul.ac.uk\/~ev\/flagmatic\/usersguide.pdf."},{"key":"S0963548312000508_ref22","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548305006905"},{"key":"S0963548312000508_ref5","unstructured":"Baber R. (2011) Some results in extremal combinatorics. PhD thesis, University College London."},{"key":"S0963548312000508_ref7","doi-asserted-by":"crossref","unstructured":"Baber R. and Talbot J. (2012) New Tur\u00e1n densities for 3-graphs. Electron. J. Combin. 19 #19.","DOI":"10.37236\/2360"},{"key":"S0963548312000508_ref39","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-009-2320-x"},{"key":"S0963548312000508_ref14","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1946-08715-7"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548312000508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,18]],"date-time":"2020-07-18T08:30:35Z","timestamp":1595061035000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548312000508\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,7]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["S0963548312000508"],"URL":"https:\/\/doi.org\/10.1017\/s0963548312000508","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,12,7]]}}}