Geodesic
On the Fon-Der-Flaass interpretation of extremal examples for Tur\'an's $(3,4)$-problem
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 269-290.

Voir la notice de l'article provenant de la source Math-Net.Ru

Fon-Der-Flaass (1988) presented a general construction that converts an arbitrary $\vec C_4$-free oriented graph $\Gamma$ 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 $\frac37(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 $\frac49(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 $\Gamma$: (i) $G$ is complete multipartite; (ii) the edge density of $G$ is not less than $\frac23-\epsilon$ for some absolute constant $\epsilon>0$. We are also able to improve Fon-Der-Flaass's bound to $\frac7{16}(1-o(1))$ without any extra assumptions on $\Gamma$. 
@article{TM_2011_274_a14,
     author = {Alexander A. Razborov},
     title = {On the {Fon-Der-Flaass} interpretation of extremal examples for {Tur\'an's} $(3,4)$-problem},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {269--290},
     publisher = {mathdoc},
     volume = {274},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TM_2011_274_a14/}
}
TY  - JOUR
AU  - Alexander A. Razborov
TI  - On the Fon-Der-Flaass interpretation of extremal examples for Tur\'an's $(3,4)$-problem
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2011
SP  - 269
EP  - 290
VL  - 274
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TM_2011_274_a14/
LA  - ru
ID  - TM_2011_274_a14
ER  - 
%0 Journal Article
%A Alexander A. Razborov
%T On the Fon-Der-Flaass interpretation of extremal examples for Tur\'an's $(3,4)$-problem
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2011
%P 269-290
%V 274
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TM_2011_274_a14/
%G ru
%F TM_2011_274_a14
Alexander A. Razborov. On the Fon-Der-Flaass interpretation of extremal examples for Tur\'an's $(3,4)$-problem. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 269-290. http://geodesic.mathdoc.fr/item/TM_2011_274_a14/

[1] Fon-Der-Flaass D.G., “Ob odnom sposobe postroeniya $(3,4)$-grafov”, Mat. zametki, 44:4 (1998), 546–550 | MR

[2] Brown W.G., “On an open problem of Paul Turán concerning 3-graphs”, Studies in pure mathematics, Birkhäuser, Basel, 1983, 91–93 | DOI | MR

[3] de Caen D., “The current status of Turán's problem on hypergraphs”, Extremal problems for finite sets, Visegrád (Hungary), 1991, Bolyai Soc. Math. Stud., 3, János Bolyai Math. Soc., Budapest, 1994, 187–197 | Zbl

[4] Chung F., Lu L., “An upper bound for the Turán number $t_3(n,4)$”, J. Comb. Theory A, 87 (1999), 381–389 | DOI | MR | Zbl

[5] Fisher D.C., “Lower bounds on the number of triangles in a graph”, J. Graph Theory, 13:4 (1989), 505–512 | DOI | MR | Zbl

[6] Goodman A.W., “On sets of acquaintances and strangers at any party”, Amer. Math. Mon., 66:9 (1959), 778–783 | DOI | MR | Zbl

[7] Kostochka A.V., “A class of constructions for Turán's $(3,4)$-problem”, Combinatorica, 2:2 (1982), 187–192 | DOI | MR | Zbl

[8] Lovász L., Simonovits M., “On the number of complete subgraphs of a graph. II”, Studies in pure mathematics, Birkhäuser, Basel, 1983, 459–495 | DOI | MR

[9] Lovász L., Szegedy B., “Limits of dense graph sequences”, J. Comb. Theory B, 96:6 (2006), 933–957 | DOI | MR | Zbl

[10] Mantel W., “Vraagstuk XXVIII”, Wiskundige Opgaven, 10 (1907), 60–61 | Zbl

[11] Nikiforov V., The number of cliques in graphs of given order and size, E-print, 2007, arXiv: 0710.2305v2 | MR

[12] Pikhurko O., The minimum size of 3-graphs without a 4-set spanning no or exactly three edges, Manuscript, Carnegie Mellon Univ., Pittsburgh, 2009 http://www.math.cmu.edu/~pikhurko/Papers/ExactG0G3.pdf | MR

[13] Razborov A.A., “Flag algebras”, J. Symb. Log., 72:4 (2007), 1239–1282 | DOI | MR | Zbl

[14] Razborov A.A., “On the minimal density of triangles in graphs”, Comb. Probab. and Comput., 17:4 (2008), 603–618 | DOI | MR | Zbl

[15] Razborov A.A., “On 3-hypergraphs with forbidden 4-vertex configurations”, SIAM J. Discr. Math., 24:3 (2010), 946–963 | DOI | MR | Zbl

[16] Sidorenko A., “What we know and what we do not know about Turán numbers”, Graphs and Comb., 11 (1995), 179–199 | DOI | MR | Zbl

[17] Turán P., “Egy gráfelméleti szélsöértékfeladatról”, Mat. és Fiz. Lapok., 48 (1941), 436–452 | MR | Zbl