|
Trudy Matematicheskogo Instituta imeni V.A. Steklova, 2011, Volume 274, Pages 269–290
(Mi tm3324)
|
|
|
|
This article is cited in 11 scientific papers (total in 11 papers)
On the Fon-Der-Flaass interpretation of extremal examples for Turán's $(3,4)$-problem
Alexander A. Razborovab a University of Chicago, Chicago, IL, USA
b Steklov Mathematical Institute, Russian Academy of Sciences, Moscow, Russia
Abstract:
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$.
Received in October 2010
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
Linking options:
https://www.mathnet.ru/eng/tm3324 https://www.mathnet.ru/eng/tm/v274/p269
|
Statistics & downloads: |
Abstract page: | 436 | Full-text PDF : | 65 | References: | 69 |
|