Geodesic
More about sparse halves in triangle-free graphs
Sbornik. Mathematics, Tome 213 (2022) no. 1, pp. 109-128 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 $\geqslant 5$, for graphs with independence number $\geqslant 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: extremal graph theory, triangle-free graphs. 
@article{SM_2022_213_1_a4,
     author = {A. A. Razborov},
     title = {More about sparse halves in triangle-free graphs},
     journal = {Sbornik. Mathematics},
     pages = {109--128},
     year = {2022},
     volume = {213},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_2022_213_1_a4/}
}
TY  - JOUR
AU  - A. A. Razborov
TI  - More about sparse halves in triangle-free graphs
JO  - Sbornik. Mathematics
PY  - 2022
SP  - 109
EP  - 128
VL  - 213
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/SM_2022_213_1_a4/
LA  - en
ID  - SM_2022_213_1_a4
ER  - 
%0 Journal Article
%A A. A. Razborov
%T More about sparse halves in triangle-free graphs
%J Sbornik. Mathematics
%D 2022
%P 109-128
%V 213
%N 1
%U http://geodesic.mathdoc.fr/item/SM_2022_213_1_a4/
%G en
%F SM_2022_213_1_a4
A. A. Razborov. More about sparse halves in triangle-free graphs. Sbornik. Mathematics, Tome 213 (2022) no. 1, pp. 109-128. http://geodesic.mathdoc.fr/item/SM_2022_213_1_a4/

[1] J. Balogh, F. C. Clemen, B. Lidický, Max cuts in triangle-free graphs, arXiv: 2103.14179

[2] N. Biggs, Strongly regular graphs with no triangles, arXiv: 0911.2160

[3] A. E. Brouwer, “The uniqueness of the strongly regular graph on 77 points”, J. Graph Theory, 7:4 (1983), 455–461 | DOI | MR | Zbl

[4] F. R. K. Chung, R. L. Graham, R. M. Wilson, “Quasi-random graphs”, Combinatorica, 9:4 (1989), 345–362 | DOI | MR | Zbl

[5] 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 | DOI | MR | Zbl

[6] 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 | DOI | MR | Zbl

[7] 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. János Bolyai, 60, North-Holland, Amsterdam, 1992, 239–263 | MR | Zbl

[8] 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 | MR | Zbl

[9] 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 | MR | Zbl

[10] P. Erdős, “Some old and new problems in various branches of combinatorics”, Discrete Math., 165/166 (1997), 227–231 | DOI | MR | Zbl

[11] A. Gewirtz, “Graphs with maximal even girth”, Canadian J. Math., 21 (1969), 915–934 | DOI | MR | Zbl

[12] A. Gewirtz, “The uniqueness of $g(2,2,10,56)$”, Trans. New York Acad. Sci., II Ser., 31:6 (1969), 656–675 | DOI | Zbl

[13] A. L. Gavrilyuk, A. A. Makhnev, “On Krein graphs without triangles”, Dokl. Math., 72:1 (2005), 591–594 | MR | Zbl

[14] A. Grzesik, “On the maximum number of five-cycles in a triangle-free graph”, J. Combin. Theory Ser. B, 102:5 (2012), 1061–1066 | DOI | MR | Zbl

[15] H. Hatami, J. Hladký, D. Král, S. Norine, A. Razborov, “Non-three-colourable common graphs exist”, Combin. Probab. Comput., 21:5 (2012), 734–742 | DOI | MR | Zbl

[16] H. Hatami, J. Hladký, D. Král, S. Norine, A. Razborov, “On the number of pentagons in triangle-free graphs”, J. Combin. Theory Ser. A, 120:3 (2013), 722–732 | DOI | MR | Zbl

[17] P. Kaski, P. Östergard, “There are exactly five biplanes with $k = 11$”, J. Combin. Des., 16:2 (2008), 117–127 | DOI | MR | Zbl

[18] M. Krivelevich, “On the edge distribution in triangle-free graphs”, J. Combin. Theory Ser. B, 63:2 (1995), 245–260 | DOI | MR | Zbl

[19] P. Keevash, B. Sudakov, “Sparse halves in triangle-free graphs”, J. Combin. Theory Ser. B, 96:4 (2006), 614–620 | DOI | MR | Zbl

[20] S. Norin, L. Yepremyan, “Sparse halves in dense triangle-free graphs”, J. Combin. Theory Ser. B, 115 (2015), 1–25 | DOI | MR | Zbl

[21] A. A. Razborov, “Flag algebras”, J. Symbolic Logic, 72:4 (2007), 1239–1282 | DOI | MR | Zbl