13
$\begingroup$

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

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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