Trudy Matematicheskogo Instituta imeni V.A. Steklova
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Guidelines for authors License agreement Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Trudy Mat. Inst. Steklova: Year: Volume: Issue: Page: Find

 Trudy Mat. Inst. Steklova, 2011, Volume 274, Pages 269–290 (Mi tm3324)

On the Fon-Der-Flaass interpretation of extremal examples for Turá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 Turán $(3,4)$-graph. He observed that all Turán–Brown–Kostochka examples result from his construction, and proved the lower bound $\frac37(1-o(1))$ on the edge density of any Turá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 Turá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$.

Full text: PDF file (341 kB)
References: PDF file   HTML file

English version:
Proceedings of the Steklov Institute of Mathematics, 2011, 274, 247–266

Bibliographic databases:

UDC: 519.176+519.179.1

Citation: Alexander A. Razborov, “On the Fon-Der-Flaass interpretation of extremal examples for Turá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

Citation in format AMSBIB
\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://www.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{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&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} 

• http://mi.mathnet.ru/eng/tm3324
• http://mi.mathnet.ru/eng/tm/v274/p269

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. 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
2. 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
3. Razborov A.A., “On the Caccetta-Haggkvist Conjecture with Forbidden Subgraphs”, J. Graph Theory, 74:2 (2013), 236–248
4. A. A. Razborov, “On Turán's $(3,4)$-Problem with Forbidden Subgraphs”, Math. Notes, 95:2 (2014), 247–254
5. Glebov R., Kral D., Volec J., “A problem of Erdős and Sós on 3-graphs”, Isr. J. Math., 211:1 (2016), 349–366
6. L. N. Coregliano, A. A. Razborov, “Semantic limits of dense combinatorial objects”, Russian Math. Surveys, 75:4 (2020), 627–723
•  Number of views: This page: 342 Full text: 46 References: 46