The diameter of uniform spanning trees in high dimensions

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\ge 5$, the hypercube $\{0,1{\}}^m$, and small perturbations thereof.

29 pages