Long induced paths in expanders
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915181890633728 |
|---|---|
| author | Draganić, Nemanja Keevash, Peter |
| author_facet | Draganić, Nemanja Keevash, Peter |
| contents | We prove that any bounded degree regular graph with sufficiently strong spectral expansion contains an induced path of linear length. This is the first such result for expanders, strengthening an analogous result in the random setting by Draganić, Glock and Krivelevich. More generally, we find long induced paths in sparse graphs that satisfy a mild upper-uniformity edge-distribution condition. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_02256 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Long induced paths in expanders Draganić, Nemanja Keevash, Peter Combinatorics We prove that any bounded degree regular graph with sufficiently strong spectral expansion contains an induced path of linear length. This is the first such result for expanders, strengthening an analogous result in the random setting by Draganić, Glock and Krivelevich. More generally, we find long induced paths in sparse graphs that satisfy a mild upper-uniformity edge-distribution condition. |
| title | Long induced paths in expanders |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2402.02256 |