# Comparing two measures on trees on $n$ vertices

A standard measure on trees on $n$ vertices is the Uniform Spanning Tree (UST) on the complete graph. This is the measure where every tree has equal probability, $1 / n^{n-2}$ by Cayley's formula.

Here is another measure. Take an Erdős–Rényi (i.e. edge independent) random graph $G \in G(n,p)$ with $p$ large enough to ensure that $G$ is asymptotically almost surely connected, and then choose a UST on $G$.

Note that if $p = 1$ these two measures are identical. My guess is that they are close (say in total variation distance), even for much smaller $p$. In particular, suppose that $$p \ge \frac{\log n + \omega}{n},$$ where $\omega \to \infty$ arbitrarily slowly as $n \to \infty$. (This is barely sufficient to guarantee that the probability that $G$ is connected tends to one.)

Are these actually the same measure in disguise? If not, can we say that they are "close" to the same measure, for example, by putting an upper bound on the total variation distance between the two measures that tends to zero as $n \to \infty$?

-

It's a nice question that I don't know a complete answer to. However it can be seen that the measures are not exactly the same. Take $p$ to be very small. The most likely connected $G$ is a tree, and all trees are equally likely. The next most likely $G$ is a unicyclic graph, whose numbers of spanning trees vary. Calculating $K_{1,3}$ versus $P_4$ shows that $K_{1,3}$ is a little bit more likely.

The exact expression for the probability of a given $T$ is a polynomial in $p$, so if this polynomial is not constant for tiny $p$ it won't be constant for larger $p$ either.

It would be very interesting to know how much the distributions can differ in general.

-
Here I think you can try to generate the graph at the same time as the loop-erased random walks, which means that for a while you can couple a loop-erased random walk on the complete graph with one on $G(n,p)$. Not sure this method will allow you to go all the way to the connectivity threshsold $p = (1+ \epsilon) \log n / n$, though. Perhaps it would be easier to start with $p=1/2$ !