Abstract:
Fon-Der-Flaass (1988) presented a general construction that converts an arbitrary →C4-free oriented graph Γ into a Turán (3,4)-graph. He observed that all Turán–Brown–Kostochka examples result from his construction, and proved the lower bound 37(1−o(1)) on the edge density of any Turán (3,4)-graph obtainable in this way. In this paper we establish the optimal bound 49(1−o(1)) on the edge density of any Turán (3,4)-graph resulting from the Fon-Der-Flaass construction under any of the following assumptions on the undirected graph G underlying the oriented graph Γ: (i) G is complete multipartite; (ii) the edge density of G is not less than 23−ϵ for some absolute constant ϵ>0. We are also able to improve Fon-Der-Flaass's bound to 716(1−o(1)) without any extra assumptions on Γ.
Citation:
Alexander A. Razborov, “On the Fon-Der-Flaass interpretation of extremal examples for Turán's (3,4)-problem”, Algorithmic aspects of algebra and logic, Collected papers. Dedicated to Academician Sergei Ivanovich Adian on the occasion of his 80th birthday, Trudy Mat. Inst. Steklova, 274, MAIK Nauka/Interperiodica, Moscow, 2011, 269–290; Proc. Steklov Inst. Math., 274 (2011), 247–266
\Bibitem{Raz11}
\by Alexander~A.~Razborov
\paper On the Fon-Der-Flaass interpretation of extremal examples for Tur\'an's $(3,4)$-problem
\inbook Algorithmic aspects of algebra and logic
\bookinfo Collected papers. Dedicated to Academician Sergei Ivanovich Adian on the occasion of his 80th birthday
\serial Trudy Mat. Inst. Steklova
\yr 2011
\vol 274
\pages 269--290
\publ MAIK Nauka/Interperiodica
\publaddr Moscow
\mathnet{http://mi.mathnet.ru/tm3324}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2962945}
\elib{https://elibrary.ru/item.asp?id=16766488}
\transl
\jour Proc. Steklov Inst. Math.
\yr 2011
\vol 274
\pages 247--266
\crossref{https://doi.org/10.1134/S0081543811060150}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000295983200014}
\elib{https://elibrary.ru/item.asp?id=23959211}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84870915108}
Linking options:
https://www.mathnet.ru/eng/tm3324
https://www.mathnet.ru/eng/tm/v274/p269
This publication is cited in the following 11 articles:
L. N. Coregliano, A. A. Razborov, “Semantic limits of dense combinatorial objects”, Russian Math. Surveys, 75:4 (2020), 627–723
Miklós Simonovits, Endre Szemerédi, Bolyai Society Mathematical Studies, 28, Building Bridges II, 2019, 445
Glebov R., Kral D., Volec J., “A problem of Erdős and Sós on 3-graphs”, Isr. J. Math., 211:1 (2016), 349–366
A. A. Razborov, “On Turán's (3,4)-Problem with Forbidden Subgraphs”, Math. Notes, 95:2 (2014), 247–254
Oleg Pikhurko, “ON possible Turán densities”, Isr. J. Math., 201:1 (2014), 415
Hatami H., Hladky J., Kral D., Norine S., Razborov A., “On the Number of Pentagons in Triangle-Free Graphs”, J. Comb. Theory Ser. A, 120:3 (2013), 722–732
Falgas-Ravry V., Vaughan E.R., “Applications of the Semi-Definite Method to the Turan Density Problem for 3-Graphs”, Comb. Probab. Comput., 22:1 (2013), 21–54
Razborov A.A., “On the Caccetta-Haggkvist Conjecture with Forbidden Subgraphs”, J. Graph Theory, 74:2 (2013), 236–248
Alexander A. Razborov, The Mathematics of Paul Erdős II, 2013, 207
Roman Glebov, Daniel Králʼ, Jan Volec, “An application of flag algebras to a problem of Erdős and Sós”, Electronic Notes in Discrete Mathematics, 43 (2013), 171
Oleg Pikhurko, “The minimum size of 3-graphs without a 4-set spanning no or exactly three edges”, European Journal of Combinatorics, 32:7 (2011), 1142