PreprintarXiv licencearXiv
On the asymptotics of the Erdős-Rogers function
Abstract
The Erdős-Rogers function fℓ,s(n) is the largest order of a Kℓ-free induced subgraph guaranteed to exist in every Ks-free graph on n vertices. While this function is well understood for s=ℓ+1, the case where s is much larger than ℓ has remained wide open. A long-standing lower bound of Sudakov states that fℓ,s(n)≥ nℓ/2s+Oℓ(s−2), while a recent result of Bradač shows that fℓ,s(n)≤ n(ℓ−1)/(s−1)+o(1). In this paper, we close this gap asymptotically by proving that fℓ,s(n)= nℓ/2s+Oℓ(s−2). More precisely, we prove that for all 2≤ ℓ<s, we have fℓ,s(n)≤ nℓ/(2s−ℓ)+o(1). Our proof builds on Bradač's recent tight construction for off-diagonal Ramsey numbers, which can be viewed as the ℓ=2 case of our result.
Related
- Tight connectivity and shadow densities in generalized Erdős--Rogers problems
- Asymptotics of the Brown--Erdős--Sós problem at integer exponents
- On moments of the Erdős-Hooley Delta-function
- On the Kashaev--Luo--Vartanov Partition Function for Cusped 3-Manifolds: Asymptotics and a squared norm property
- Gaussian Fluctuations of the Gradient of the Fréchet Function and Nonstandard Asymptotics of Sample Fréchet Means
BibTeX
@misc{bradac2026asymptotics,
title = {{On the asymptotics of the Erdős-Rogers function}},
author = {Domagoj Bradač and Oliver Janzer and Rik Sarkar},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.37987},
eprint = {2609.37987},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.37987},
}
RIS
TY - UNPB
TI - On the asymptotics of the Erdős-Rogers function
AU - Domagoj Bradač
AU - Oliver Janzer
AU - Rik Sarkar
PY - 2026
DA - 2026/09/29
PB - arXiv
DO - 10.48550/arxiv.2609.37987
UR - https://arxiv.org/abs/2609.37987
AB - The Erdős-Rogers function f_ℓ,s(n) is the largest order of a K_ℓ-free induced subgraph guaranteed to exist in every K_s-free graph on n vertices. While this function is well understood for s=ℓ+1, the case where s is much larger than ℓ has remained wide open. A long-standing lower bound of Sudakov states that f_ℓ,s(n)≥ n^ℓ/2s+O_ℓ(s^−2), while a recent result of Bradač shows that f_ℓ,s(n)≤ n^(ℓ−1)/(s−1)+o(1). In this paper, we close this gap asymptotically by proving that f_ℓ,s(n)= n^ℓ/2s+O_ℓ(s^−2). More precisely, we prove that for all 2≤ ℓ<s, we have f_ℓ,s(n)≤ n^ℓ/(2s−ℓ)+o(1). Our proof builds on Bradač's recent tight construction for off-diagonal Ramsey numbers, which can be viewed as the ℓ=2 case of our result.
ER -