Improved bounds for the Erdős-Rogers function
Advances in Combinatronics (2020)
Voir la notice de l'article provenant de la source Advances in Combinatronics website
The Erd\H{o}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^{\alpha_{s,t}+o(1)}$ with an exponent $\alpha_{s,t}1/2$, answering a
question of Dudek, Retter and R\"{o}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 Combinatronics},
publisher = {mathdoc},
year = {2020},
language = {en},
url = {http://geodesic.mathdoc.fr/item/ADVC_2020_a7/}
}
W. T. Gowers; O. Janzer. Improved bounds for the Erdős-Rogers function. Advances in Combinatronics (2020). http://geodesic.mathdoc.fr/item/ADVC_2020_a7/