×

zbMATH — the first resource for mathematics

On Turán’s \((3,4)\)-problem with forbidden subgraphs. (English. Russian original) Zbl 1310.05126
Math. Notes 95, No. 2, 245-252 (2014); translation from Mat. Zametki 95, No. 2, 271-281 (2014).
Summary: We identify three 3-graphs on five vertices that are missing in all known extremal configurations for Turán’s \((3,4)\)-problem and prove Turán’s conjecture for 3-graphs that are additionally known not to contain any induced copies of these 3-graphs. Our argument is based on an (apparently) new technique of “indirect interpretation” that allows us to retrieve additional structure from hypothetical counterexamples to Turán’s conjecture, but in rather loose and limited sense. We also include two miscellaneous calculations in flag algebras that prove similar results about some other additional forbidden subgraphs.

MSC:
05C35 Extremal problems in graph theory
05C65 Hypergraphs
Software:
Flagmatic
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] W. Mantel, ”Vraagstuk XXVIII,” Wiskundige Opgaven 10, 60–61 (1907). · JFM 38.0270.01
[2] P. Turán, ”Egy gráfelméleti szélsöértékfeladatról,” Mat.és Fiz. Lapok 48, 436–452 (1941).
[3] P. Keevash, ”Hypergraph Turán Problems,” in London Math. Soc. Lecture Note Ser., Vol. 392: Surveys in Combinatorics (Cambridge Univ. Press, Cambridge, 2011), pp. 83–139. · Zbl 1244.05159
[4] D. de Caen, ”The current status of Turán problem on hypergraphs,” in Bolyai Soc. Math. Stud., Vol. 3: Extremal Problems for Finite Sets (János BolyaiMath. Soc., Budapest, 1991), pp. 187–197.
[5] F. Chung and L. Lu, ”An upper bound for the Turán number t 3(n, 4),” J. Combin. Theory Ser. A 87(2), 381–389 (1999). · Zbl 0946.05063 · doi:10.1006/jcta.1998.2961
[6] A. A. Razborov, ”On 3-hypergraphs with forbidden 4-vertex configurations,” SIAMJ. DiscreteMath. 24(3), 946–963 (2010). · Zbl 1223.05204
[7] V. Falgas-Ravry and E. R. Vaughan, ”Applications of the semi-definite method to the Turán density problem for 3-graphs,” Combin. Probab. Comput. 22(1), 21–54 (2013). · Zbl 1257.05077 · doi:10.1017/S0963548312000508
[8] W. G. Brown, ”On an open problem of Paul Turán concerning 3-graphs,” in Studies in Pure Mathematics (Birkhäuser Verlag, Basel, 1983), pp. 91–93.
[9] A. V. Kostochka, ”A class of constructions for Turán’s (3, 4)-problem,” Combinatorica 2(2), 187–192 (1982). · Zbl 0502.05046 · doi:10.1007/BF02579317
[10] D. G. Fon-Der-Flaass, ”Method for construction of (3, 4)-graphs,” Mat. Zametki 44(4), 546–550 (1988) [Math. Notes 44 (4), 781–783 (1988)]. · Zbl 0727.05042
[11] A. A. Razborov, ”On the Fon-Der-Flaas interpretation of extremal examples for Turán’s (3, 4)-problem,” in Trudy Mat. Inst. Steklov, Vol. 274: Algebraic Problems of Algebra and Logic, Collection of papers dedicated to the memory of Academician Sergei Ivanovich Adyan (MAIK, Moscow, 2011), pp. 269–290 [in Russian]; [Proc. Steklov Inst. Math. 274, 247–266 (2011)].
[12] O. Pikhurko, ”The minimum size of 3-graphs without a 4-set spanning no or exactly three edges,” European J. Combin. 32(7), 1142–1155 (2011). · Zbl 1229.05154 · doi:10.1016/j.ejc.2011.03.006
[13] A. A. Razborov, ”Flag algebras,” J. Symbolic Logic 72(4), 1239–1282 (2007). · Zbl 1146.03013 · doi:10.2178/jsl/1203350785
[14] R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey Theory, in Wiley-Intersci. Ser. Discrete Math. Optim. (John Wiley & Sons, New York, 1990).
[15] Z. Füredi, O. Pikhurko, and M. Simonovits, ”The Turán density of the hypergraph abc, ade, bde, cde,” Electron. J. Combin. 10(Research Paper 18) (2003). · Zbl 1011.05031
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.