Spanning trees of bounded degree in random geometric graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913853299752960 |
|---|---|
| author | Anastos, Michael Diskin, Sahar Ignasiak, Dawid Lichev, Lyuben Sha, Yetong |
| author_facet | Anastos, Michael Diskin, Sahar Ignasiak, Dawid Lichev, Lyuben Sha, Yetong |
| contents | We determine the sharp threshold for the containment of all $n$-vertex trees of bounded degree in random geometric graphs with $n$ vertices. This provides a geometric counterpart of Montgomery's threshold result for binomial random graphs, and confirms a conjecture of Espuny Díaz, Lichev, Mitsche, and Wesolek. Our proof is algorithmic and adapts to other families of graphs, in particular graphs with bounded genus or tree-width. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_16818 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Spanning trees of bounded degree in random geometric graphs Anastos, Michael Diskin, Sahar Ignasiak, Dawid Lichev, Lyuben Sha, Yetong Combinatorics Metric Geometry Probability We determine the sharp threshold for the containment of all $n$-vertex trees of bounded degree in random geometric graphs with $n$ vertices. This provides a geometric counterpart of Montgomery's threshold result for binomial random graphs, and confirms a conjecture of Espuny Díaz, Lichev, Mitsche, and Wesolek. Our proof is algorithmic and adapts to other families of graphs, in particular graphs with bounded genus or tree-width. |
| title | Spanning trees of bounded degree in random geometric graphs |
| topic | Combinatorics Metric Geometry Probability |
| url | https://arxiv.org/abs/2505.16818 |