Improved bounds for the Erdős-Rogers $(s,s+2)$-problem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911770569867264 |
|---|---|
| author | Janzer, Oliver Sudakov, Benny |
| author_facet | Janzer, Oliver Sudakov, Benny |
| contents | For $2\leq s<t$, the Erdős-Rogers function $f_{s,t}(n)$ measures how large a $K_s$-free induced subgraph there must be in a $K_t$-free graph on $n$ vertices. There has been an extensive amount of work towards estimating this function, but until very recently only the case $t=s+1$ was well understood. A recent breakthrough of Mattheus and Verstraëte on the Ramsey number $r(4,k)$ states that $f_{2,4}(n)\leq n^{1/3+o(1)}$, which matches the known lower bound up to the $o(1)$ term. In this paper we build on their approach and generalize this result by proving that $f_{s,s+2}(n)\leq n^{\frac{2s-3}{4s-5}+o(1)}$ holds for every $s\geq 2$. This comes close to the best known lower bound, improves a substantial body of work and is the best that any construction of similar kind can give. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_05441 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Improved bounds for the Erdős-Rogers $(s,s+2)$-problem Janzer, Oliver Sudakov, Benny Combinatorics For $2\leq s<t$, the Erdős-Rogers function $f_{s,t}(n)$ measures how large a $K_s$-free induced subgraph there must be in a $K_t$-free graph on $n$ vertices. There has been an extensive amount of work towards estimating this function, but until very recently only the case $t=s+1$ was well understood. A recent breakthrough of Mattheus and Verstraëte on the Ramsey number $r(4,k)$ states that $f_{2,4}(n)\leq n^{1/3+o(1)}$, which matches the known lower bound up to the $o(1)$ term. In this paper we build on their approach and generalize this result by proving that $f_{s,s+2}(n)\leq n^{\frac{2s-3}{4s-5}+o(1)}$ holds for every $s\geq 2$. This comes close to the best known lower bound, improves a substantial body of work and is the best that any construction of similar kind can give. |
| title | Improved bounds for the Erdős-Rogers $(s,s+2)$-problem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2307.05441 |