Long induced paths in $K_{s, s}$-free graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914016582959104 |
|---|---|
| author | Hunter, Zach Milojević, Aleksa Sudakov, Benny Tomon, István |
| author_facet | Hunter, Zach Milojević, Aleksa Sudakov, Benny Tomon, István |
| contents | More than 40 years ago, Galvin, Rival and Sands showed that every $K_{s, s}$-free graph containing an $n$-vertex path must contain an induced path of length $f(n)$, where $f(n)\to \infty$ as $n\to \infty$. Recently, it was shown by Duron, Esperet and Raymond that one can take $f(n)=(\log \log n)^{1/5-o(1)}$. In this note, we give a short self-contained proof that a $K_{s, s}$-free graphs with an $n$-vertex path contains an induced path of length at least $(\log \log n)^{1-o(1)}$. Combined with the recent remarkable example of Couëtoux, Defrain, and Raymond, which provides an upper bound of $O((\log \log n)^{1+o(1)})$, this essentially resolves this old problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_19173 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Long induced paths in $K_{s, s}$-free graphs Hunter, Zach Milojević, Aleksa Sudakov, Benny Tomon, István Combinatorics 05C38 More than 40 years ago, Galvin, Rival and Sands showed that every $K_{s, s}$-free graph containing an $n$-vertex path must contain an induced path of length $f(n)$, where $f(n)\to \infty$ as $n\to \infty$. Recently, it was shown by Duron, Esperet and Raymond that one can take $f(n)=(\log \log n)^{1/5-o(1)}$. In this note, we give a short self-contained proof that a $K_{s, s}$-free graphs with an $n$-vertex path contains an induced path of length at least $(\log \log n)^{1-o(1)}$. Combined with the recent remarkable example of Couëtoux, Defrain, and Raymond, which provides an upper bound of $O((\log \log n)^{1+o(1)})$, this essentially resolves this old problem. |
| title | Long induced paths in $K_{s, s}$-free graphs |
| topic | Combinatorics 05C38 |
| url | https://arxiv.org/abs/2411.19173 |