Fixed forests in the minimum spanning tree and cubic volume growth

Abstract

Let $M_n$ be the minimum spanning tree of the complete graph $K_n$ with i.i.d.\ uniform edge weights. For a fixed forest $F$ with connected components $T_1,\dots ,T_d$, we show that there exists a function $\Psi$ on finite trees such that $$n^{|E(F)|}{\mathbb{P}}_n(F\subseteq M_n)⟶\prod _{i=1}^d\Psi (T_i).$$ We give a recursive description of $\Psi$ and calculate it explicitly for several small trees. For the star $S_k$ and the path $P_k$, we prove that $\Psi (S_k)\sim \zeta (2{)}^k$ and $\Psi (P_k)\sim k^2/12$, respectively. We also show that the expected size of a ball of radius $r$ is asymptotic to $r^3/36$, and give exponential tail bounds.

29 pages, 1 figure. Comments are welcome!