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 MIAN:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

This article is cited in 5 scientific papers (total in 5 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$.

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
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, Tr. 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 Tr. 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{http://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{http://elibrary.ru/item.asp?id=23959211}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84870915108}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  crossref  mathscinet  zmath  isi  elib
    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  crossref  mathscinet  zmath  isi  elib
    3. Razborov A.A., “On the Caccetta-Haggkvist Conjecture with Forbidden Subgraphs”, J. Graph Theory, 74:2 (2013), 236–248  crossref  mathscinet  zmath  isi  elib
    4. A. A. Razborov, “On Turán's $(3,4)$-Problem with Forbidden Subgraphs”, Math. Notes, 95:2 (2014), 247–254  mathnet  crossref  crossref  mathscinet  isi  elib  elib
    5. Glebov R., Kral D., Volec J., “A problem of Erdős and Sós on 3-graphs”, Isr. J. Math., 211:1 (2016), 349–366  crossref  mathscinet  zmath  isi  elib  scopus
  • Труды Математического института им. В. А. Стеклова Proceedings of the Steklov Institute of Mathematics
    Number of views:
    This page:304
    Full text:29
    References:42

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020