Nearly Hamilton cycles in sublinear expanders, and applications
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918297309544448 |
|---|---|
| author | Letzter, Shoham Methuku, Abhishek Sudakov, Benny |
| author_facet | Letzter, Shoham Methuku, Abhishek Sudakov, Benny |
| contents | We develop novel methods for constructing nearly Hamilton cycles in sublinear expanders with good regularity properties, as well as new techniques for finding such expanders in general graphs. These methods are of independent interest due to their potential for various applications to embedding problems in sparse graphs. In particular, using these tools, we make substantial progress towards a twenty-year-old conjecture of Verstraëte, which asserts that for any given graph $F$, nearly all vertices of every $d$-regular graph $G$ can be covered by vertex-disjoint $F$-subdivisions. This significantly extends previous work on the conjecture by Kelmans, Mubayi and Sudakov, Alon, and Kühn and Osthus. Additionally, we present applications of our methods to two other problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_07147 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Nearly Hamilton cycles in sublinear expanders, and applications Letzter, Shoham Methuku, Abhishek Sudakov, Benny Combinatorics We develop novel methods for constructing nearly Hamilton cycles in sublinear expanders with good regularity properties, as well as new techniques for finding such expanders in general graphs. These methods are of independent interest due to their potential for various applications to embedding problems in sparse graphs. In particular, using these tools, we make substantial progress towards a twenty-year-old conjecture of Verstraëte, which asserts that for any given graph $F$, nearly all vertices of every $d$-regular graph $G$ can be covered by vertex-disjoint $F$-subdivisions. This significantly extends previous work on the conjecture by Kelmans, Mubayi and Sudakov, Alon, and Kühn and Osthus. Additionally, we present applications of our methods to two other problems. |
| title | Nearly Hamilton cycles in sublinear expanders, and applications |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2503.07147 |