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






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


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
References:
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
English version:
Proceedings of the Steklov Institute of Mathematics, 2011, Volume 274, Pages 247–266
DOI: https://doi.org/10.1134/S0081543811060150
Bibliographic databases:
Document Type: Article
UDC: 519.176+519.179.1
Language: Russian
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
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://mathscinet.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{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&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}
Linking options:
  • https://www.mathnet.ru/eng/tm3324
  • https://www.mathnet.ru/eng/tm/v274/p269
  • This publication is cited in the following 11 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Труды Математического института имени В. А. Стеклова Proceedings of the Steklov Institute of Mathematics
    Statistics & downloads:
    Abstract page:436
    Full-text PDF :65
    References:69
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024