Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question
add comment

2 Answers

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.

share|improve this answer
add comment

It's a nice question. The following is not an answer but too long to put in comment. I think in general you want to ask "how much can you tell of the underlying graph given a sample from the uniform spanning tree". There is a great algorithm due to David Wilson to sample the UST, which consists in growing the tree by successively running loop-erased random walks. See eg http://en.wikipedia.org/wiki/Loop-erased_random_walk.

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$ !

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.