Embedding induced trees in sparse expanding graphs
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_ | 1866917686644047872 |
|---|---|
| author | Girão, António Hurley, Eoin |
| author_facet | Girão, António Hurley, Eoin |
| contents | Inspired by the network routing literature \cite{aggarwal1996efficient}, we develop what we call a ``Pre-Emptive Greedy Algorithm" to embed bounded degree induced trees in sparse expanders.
This generalises a powerful and central result of Friedman and Pippenger to the induced setting.
As corollaries we obtain that a sparse random graph contains all bounded degree trees of linear order (whp) and that the induced and size induced Ramsey numbers of bounded degree trees are linear. No such linear bounds were previously known. We also prove a nearly-tight result on induced forests in bounded degree countable expanders. We expect that our new result will find many more applications. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_04260 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Embedding induced trees in sparse expanding graphs Girão, António Hurley, Eoin Combinatorics Inspired by the network routing literature \cite{aggarwal1996efficient}, we develop what we call a ``Pre-Emptive Greedy Algorithm" to embed bounded degree induced trees in sparse expanders. This generalises a powerful and central result of Friedman and Pippenger to the induced setting. As corollaries we obtain that a sparse random graph contains all bounded degree trees of linear order (whp) and that the induced and size induced Ramsey numbers of bounded degree trees are linear. No such linear bounds were previously known. We also prove a nearly-tight result on induced forests in bounded degree countable expanders. We expect that our new result will find many more applications. |
| title | Embedding induced trees in sparse expanding graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.04260 |