Typesetting math: 100%
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 C4-free oriented graph Γ 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 37(1o(1)) on the edge density of any Turán (3,4)-graph obtainable in this way. In this paper we establish the optimal bound 49(1o(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 Γ: (i) G is complete multipartite; (ii) the edge density of G is not less than 23ϵ for some absolute constant ϵ>0. We are also able to improve Fon-Der-Flaass's bound to 716(1o(1)) without any extra assumptions on Γ.
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:
    1. L. N. Coregliano, A. A. Razborov, “Semantic limits of dense combinatorial objects”, Russian Math. Surveys, 75:4 (2020), 627–723  mathnet  crossref  crossref  mathscinet  zmath  adsnasa  isi  elib
    2. Miklós Simonovits, Endre Szemerédi, Bolyai Society Mathematical Studies, 28, Building Bridges II, 2019, 445  crossref
    3. 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
    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. Oleg Pikhurko, “ON possible Turán densities”, Isr. J. Math., 201:1 (2014), 415  crossref
    6. 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
    7. 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
    8. Razborov A.A., “On the Caccetta-Haggkvist Conjecture with Forbidden Subgraphs”, J. Graph Theory, 74:2 (2013), 236–248  crossref  mathscinet  zmath  isi  elib
    9. Alexander A. Razborov, The Mathematics of Paul Erdős II, 2013, 207  crossref
    10. Roman Glebov, Daniel Králʼ, Jan Volec, “An application of flag algebras to a problem of Erdős and Sós”, Electronic Notes in Discrete Mathematics, 43 (2013), 171  crossref
    11. Oleg Pikhurko, “The minimum size of 3-graphs without a 4-set spanning no or exactly three edges”, European Journal of Combinatorics, 32:7 (2011), 1142  crossref
    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:470
    Full-text PDF :77
    References:81
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2025