Anastos, M., Diskin, S., Ignasiak, D. J., Lichev, L. S., & Sha, Y. (2025). Spanning trees of bounded degree in random geometric graphs. arXiv. https://doi.org/10.48550/arXiv.2505.16818
universality; bounded-degree trees; random geometric graphs
en
Abstract:
We determine the sharp threshold for the containment of all 𝑛-vertex trees of bounded degree in random geometric graphs with 𝑛 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.
