Geodesic
Improved bounds for the Erdős-Rogers function
Advances in Combinatorics (2020)
Cet article a éte moissonné depuis la source Scholastica

Voir la notice de l'article

The Erdős-Rogers function $f_{s,t}$ measures how large a $K_s$-free induced subgraph there must be in a $K_t$-free graph on $n$ vertices. While good estimates for $f_{s,t}$ are known for some pairs $(s,t)$, notably when $t=s+1$, in general there are significant gaps between the best known upper and lower bounds. We improve the upper bounds when $s+2\leq t\leq 2s-1$. For each such pair we obtain for the first time a proof that $f_{s,t}\leq n^{α_{s,t}+o(1)}$ with an exponent $α_{s,t}1/2$, answering a question of Dudek, Retter and Rödl.
Publié le : 
@article{ADVC_2020_a7,
     author = {W. T. Gowers and O. Janzer},
     title = {Improved bounds for the {Erd\H{o}s-Rogers} function},
     journal = {Advances in Combinatorics},
     year = {2020},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/ADVC_2020_a7/}
}
TY  - JOUR
AU  - W. T. Gowers
AU  - O. Janzer
TI  - Improved bounds for the Erdős-Rogers function
JO  - Advances in Combinatorics
PY  - 2020
UR  - http://geodesic.mathdoc.fr/item/ADVC_2020_a7/
LA  - en
ID  - ADVC_2020_a7
ER  - 
%0 Journal Article
%A W. T. Gowers
%A O. Janzer
%T Improved bounds for the Erdős-Rogers function
%J Advances in Combinatorics
%D 2020
%U http://geodesic.mathdoc.fr/item/ADVC_2020_a7/
%G en
%F ADVC_2020_a7
W. T. Gowers; O. Janzer. Improved bounds for the Erdős-Rogers function. Advances in Combinatorics (2020). http://geodesic.mathdoc.fr/item/ADVC_2020_a7/