On the Fon-Der-Flaass interpretation of extremal examples for Tur\'an's $(3,4)$-problem

Alexander A. Razborov

Informatics and Automation, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 269-290

Résumé

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$.