Geodesic
More about sparse halves in triangle-free graphs
Sbornik. Mathematics, Tome 213 (2022) no. 1, pp. 109-128

Voir la notice de l'article provenant de la source Math-Net.Ru

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},
     publisher = {mathdoc},
     volume = {213},
     number = {1},
     year = {2022},
     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
PB  - mathdoc
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
%I mathdoc
%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/