The diameter of uniform spanning trees in high dimensions
classification
🧮 math.PR
math.CO
keywords
diameterspanningappliescertainconditionsconnecteddimensiondimensions
read the original abstract
We show that the diameter of a uniformly drawn spanning tree of a connected graph on $n$ vertices which satisfies certain high-dimensionality conditions typically grows like $\Theta(\sqrt{n})$. In particular this result applies to expanders, finite tori $\mathbb{Z}_m^d$ of dimension $d \geq 5$, the hypercube $\{0,1\}^m$, and small perturbations thereof.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.