Anticoncentration of random spanning trees in almost regular graphs

Abstract

The celebrated formula of Otter \emph{[Ann. of Math. (2) 49 (1948), 583--599]} asserts that the complete graph contains exponentially many non-isomorphic spanning trees. In this paper, we show that every connected almost regular graph with sufficiently large degree already contains exponentially many non-isomorphic spanning trees. Indeed, we prove a stronger statement: for every fixed $n$-vertex tree $T$, $$\mathrm{Pr}\left[\mathcal{T}{\simeq }_{\mathrm{iso}}T\right]=e^{-\hat{I}\text{c◯}(n)},$$ where $\mathcal{T}$ is a uniformly random spanning tree of a connected $n$-vertex almost regular graph with sufficiently large degree. To prove this, we introduce a graph-theoretic variant of the classical balls--into--bins model, which may be of independent interest.

17 pages