Introductory Workshop: Probability and Statistics of Discrete Structures: The largest common subtree of uniform attachment trees
Presenter
January 30, 2025
Keywords:
- Network models and random graphs
- statistcal learning and network inference
- counting and sampling discrete structures
- dynamics on networks
- probabilistic analysis of network algorithms
MSC:
- 05C80 - Random graphs (graph-theoretic aspects)
- 60C05 - Combinatorial probability
Abstract
Consider two independent uniform attachment trees with n nodes each -- how large is their largest common subtree? Our main result gives a lower bound of n^{0.83}. We also give some upper bounds and bounds for general random tree growth models. This is based on joint work with Johannes Bäumler, Bas Lodewijks, James Martin, Emil Powierski, and Anirudh Sridhar.