The local limit of the uniform spanning tree on dense graphs

Abstract

Let $G$ be a connected graph in which almost all vertices have linear degrees and let $T$ be a uniform spanning tree of $G$. For any fixed rooted tree $F$ of height $r$ we compute the asymptotic density of vertices $v$ for which the $r$-ball around $v$ in $T$ is isomorphic to $F$. We deduce from this that if $\{G_n\}$ is a sequence of such graphs converging to a graphon $W$, then the uniform spanning tree of $G_n$ locally converges to a multi-type branching process defined in terms of $W$. As an application, we prove that in a graph with linear minimum degree, with high probability, the density of leaves in a uniform spanning tree is at least $1/e-o(1)$, the density of vertices of degree $2$ is at most $1/e+o(1)$ and the density of vertices of degree $k\ge 3$ is at most $\frac{(k-2{)}^{k-2}}{(k-1)!e^{k-2}}+o(1)$. These bounds are sharp.

44 pages, error in Claim 4.1.3 fixed, as will appear in Journal of Statistical Physics, special issue devoted to Complex Networks