pith. sign in

arxiv: 1911.12319 · v1 · pith:SRV4IYOPnew · submitted 2019-11-27 · 🧮 math.PR · math.CO

The diameter of uniform spanning trees in high dimensions

classification 🧮 math.PR math.CO
keywords diameterspanningappliescertainconditionsconnecteddimensiondimensions
0
0 comments X
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.