Email this article More about sparse halves in triangle-free graphs
- Authors: Razborov A.A.1,2
-
Affiliations:
- University of Chicago
- Steklov Mathematical Institute of Russian Academy of Sciences
- Issue: Vol 213, No 1 (2022)
- Pages: 119-140
- Section: Articles
- URL: https://journals.rcsi.science/0368-8666/article/view/133422
- DOI: https://doi.org/10.4213/sm9615
- ID: 133422
Cite item
Open Access
Access granted
Subscription Access
Abstract
One of Erdős's conjectures states that every triangle-free graph on $n$ vertices has an induced subgraph on $n/2$ vertices with at most $n^2/50$ edges. We report several partial results towards this conjecture. In particular, we establish the new bound $27n^2/1024$ on the number of edges in the general case. We completely prove the conjecture for graphs of girth $\geq 5$, for graphs with independence number $\geq 2n/5$ and for strongly regular graphs. Each of these three classes includes both known (conjectured) extremal configurations, the 5-cycle and the Petersen graph. Bibliography: 21 titles.
Keywords
About the authors
Alexander Alexandrovich Razborov
University of Chicago; Steklov Mathematical Institute of Russian Academy of Sciences
Email: razborov@mi-ras.ru
Doctor of physico-mathematical sciences, no status
References
- J. Balogh, F. C. Clemen, B. Lidicky, Max cuts in triangle-free graphs
- N. Biggs, Strongly regular graphs with no triangles
- A. E. Brouwer, “The uniqueness of the strongly regular graph on 77 points”, J. Graph Theory, 7:4 (1983), 455–461
- F. R. K. Chung, R. L. Graham, R. M. Wilson, “Quasi-random graphs”, Combinatorica, 9:4 (1989), 345–362
- P. Erdős, R. Faudree, J. Pach, J. Spencer, “How to make a graph bipartite”, J. Combin. Theory Ser. B, 45:1 (1988), 86–98
- P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp, “A local density condition for triangles”, Discrete Math., 127:1-3 (1994), 153–161
- P. Erdős, E. Győri, M. Simonovits, “How many edges should be deleted to make a triangle-free graph bipartite?”, Sets, graphs and numbers (Budapest, 1991), Colloq. Math. Soc. Janos Bolyai, 60, North-Holland, Amsterdam, 1992, 239–263
- P. Erdős, “Problems and results in graph theory and combinatorial analysis”, Proceedings of the 5th British combinatorial conference (Univ. Aberdeen, Aberdeen, 1975), Congressus Numerantium, 15, Utilitas Math., Winnipeg, MB, 1976, 169–192
- P. Erdős, “On some problems in graph theory, combinatorial analysis and combinatorial number theory”, Graph theory and combinatorics (Cambridge, 1983), Academic Press, London, 1984, 1–17
- P. Erdős, “Some old and new problems in various branches of combinatorics”, Discrete Math., 165/166 (1997), 227–231
- A. Gewirtz, “Graphs with maximal even girth”, Canadian J. Math., 21 (1969), 915–934
- A. Gewirtz, “The uniqueness of $g(2,2,10,56)$”, Trans. New York Acad. Sci., II Ser., 31:6 (1969), 656–675
- А. Л. Гаврилюк, А. А. Махнев, “О графах Крейна без треугольников”, Докл. РАН, 403:6 (2005), 727–730
- A. Grzesik, “On the maximum number of five-cycles in a triangle-free graph”, J. Combin. Theory Ser. B, 102:5 (2012), 1061–1066
- H. Hatami, J. Hladky, D. Kral, S. Norine, A. Razborov, “Non-three-colourable common graphs exist”, Combin. Probab. Comput., 21:5 (2012), 734–742
- H. Hatami, J. Hladky, D. Kral, S. Norine, A. Razborov, “On the number of pentagons in triangle-free graphs”, J. Combin. Theory Ser. A, 120:3 (2013), 722–732
- P. Kaski, P. Östergard, “There are exactly five biplanes with $k = 11$”, J. Combin. Des., 16:2 (2008), 117–127
- M. Krivelevich, “On the edge distribution in triangle-free graphs”, J. Combin. Theory Ser. B, 63:2 (1995), 245–260
- P. Keevash, B. Sudakov, “Sparse halves in triangle-free graphs”, J. Combin. Theory Ser. B, 96:4 (2006), 614–620
- S. Norin, L. Yepremyan, “Sparse halves in dense triangle-free graphs”, J. Combin. Theory Ser. B, 115 (2015), 1–25
- A. A. Razborov, “Flag algebras”, J. Symbolic Logic, 72:4 (2007), 1239–1282
Supplementary files
