On the Fon-der-Flaass Interpretation of Extremal Examples for Turan's (3,4)-problem

Alexander Razborov

Published 2010-08-27Version 1

In 1941, Turan conjectured that the edge density of any 3-graph without independent sets on 4 vertices (Turan (3,4)-graph) is >= 4/9(1-o(1)), and he gave the first example witnessing this bound. Brown (1983) and Kostochka (1982) found many other examples of this density. Fon-der-Flaass (1988) presented a general construction that converts an arbitrary $\vec C_4$-free orgraph $\Gamma$ into a Turan (3,4)-graph. He observed that all Turan-Brown-Kostochka examples result from his construction, and proved the bound >= 3/7(1-o(1)) on the edge density of any Turan (3,4)-graph obtainable in this way. In this paper we establish the optimal bound 4/9(1-o(1)) on the edge density of any Turan (3,4)-graph resulting from the Fon-der-Flaass construction under any of the following assumptions on the undirected graph $G$ underlying the orgraph $\Gamma$: 1. $G$ is complete multipartite; 2. The edge density of $G$ is >= (2/3-epsilon) for some absolute constant epsilon>0. We are also able to improve Fon-der-Flaass's bound to 7/16(1-o(1)) without any extra assumptions on $\Gamma$.