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

Suppose you take a $G(n,p)$ random graph for a fixed probability $p$ and find a spanning tree using Kruskal's algorithm. If you now repeat this process indefinitely, will every tree on $n$ vertices appear with the same frequency?

In other word: are some trees more likely than others to be spanning trees of a random graph?

share|improve this question
    
I assume you're considering labeled trees/graphs. Here's an answer for an easier version of the question, which maybe you have already considered: suppose you choose each connected graph on n vertices with equal probability, and suppose you choose from it a random spanning tree. Then it seems clear to me that all trees are equally likely. –  Sam Hopkins Jan 25 '13 at 0:03
    
@SamHopkins: Actually, I was thinking about unlabelled... –  Felix Goldberg Jan 25 '13 at 0:30
    
@SamHopkins. There are $38$ connected subgraphs of $K_4$. If I pick, choosing uniformly among them, and then pick uniformly among the spanning trees of that subgraph , then the probability of getting a star is 41/152. If I pick a spanning tree by randomly weighting the edges and then taking the minimal cost spanning tree then the probabilities are something else but almost surely not uniform. –  Aaron Meyerowitz Jan 25 '13 at 20:58
    
@AaronMeyerowitz: I now see why this question is more difficult than I thought at first. Thanks. –  Sam Hopkins Jan 25 '13 at 22:23
    
Obviously more difficult than I thought also. –  Aaron Meyerowitz Jan 26 '13 at 6:04

1 Answer 1

up vote 3 down vote accepted

This is an interesting question and more subtle than it first appears. One question is the behavior of minimal cost spanning tree for the complete graph. For the question at hand it is worth first considering the behavior for $G(n,m)$ the random graph with $n$ vertices and $m$ edges. Then the model $G(n,p)$ gives a weighted average over the various $G(n,m)$ concentrated around $m=np$. Exact results seem difficult to give although as $m$ or $p$ increases a star is more likely than a path. Perhaps in trees with small diameter and more leaves are favored.

Let $G$ be a graph with $n$ vertices. A spanning forest is any cycle-free subgraph $H$ with the same vertices. An ordered spanning forest is one with a linear order on the edges. If $H$ has $n-c$ edges then it has $c$ connected components. We mainly are concerned with the case $c=1$ when $G$ is connected and $H$ is a spanning tree. There are methods to enumerate the spanning trees of a labelled graph $G.$ The complete graph $K_n$ has $n^{n-2}$ labelled spanning trees. It is not trivial to uniformly choose a member of $\mathcal{T}(G)$, the set of spanning trees of $G$ unless the set is small enough to list. It appears that a process involving loop erased random walks can be used to choose uniformly, I'm not sure what the expected stopping time is.

A simple method for choosing a spanning tree is to first randomly assign each edge of $G$ a distinct weight weight and then consider them in order of increasing weight accepting each edge if it creates a spanning forest with those previously selected , rejecting it if it would create a cycle, and stopping when a spanning tree has been created. This is the Kruskal algorithm for the minimal cost spanning tree (MCST). This is really just choosing a random permutation on the edges, but there are reasons to describe it this way. If we keep track of the order then we have an ordered spanning tree which is the last member of a sequence of ordered spanning forests.

We pause to consider application of this method to the complete graph $K_n.$ It might be thought to give the uniform distribution on $\mathcal{F}(K_n)$ but it does not. Two ways to see that this can not be uniform are

  • The probability of attaining any given spanning tree $T$ will be a fraction $\frac{c(T)}{\binom{n}{2}!}.$ When $n \gt 3$ is an odd prime, the highest power of $n$ dividing the denominator is $n^{(n-1)/2} \lt n^{n-2}.$

  • By direct computation, of the $16$ spanning trees of $K_4$, each of the four stars occurs with probability $3/6 \cdot 2/5 \cdot 1/3=1/15=12/180$ and each of the $12$ paths with probability $11/180.$

To see why the distribution is not uniform it helps to consider ordered spanning forests. Given an (ordered) spanning forest $S$ with $c$ connected components having $n_1 \ge n_2 \ge \cdots \ge n_c$ vertices there are $q(S)=\sum_{i \lt j}n_i n_j$ ways to chose an edge giving a spanning forest $S'$ with $c-1$ components. $q(s) \ge (2n-c)(c-1)/2$ with equality exactly when $n_2=\cdots=n_c=1.$ The probability that the MCST method arrives at $S'$ is $p(S')=\frac{p(S)}{q(S)}$. The probability that the MCST arrives at an (unordered) labelled spanning tree $T$ of $K_n$ is the sum of $p(T^*)$ over the $(n-1)!$ orders of the edges of $T.$ Each of the $(n-1)!$ terms is of the form $\prod_{j=0}^{n-2}\frac{1}{q(S_j)}$ where $S_j$ is an ordered spanning tree with $n-j$ components. The largest this term can be is $\frac{2^{n-1}}{(2n-2)!}$ for those orders which have all edges in the same component at each stage. So the spanning trees with the highest probability are the $n$ stars which occur with probability $\frac{2^{n-1}(n-1)!}{(2n-2)!}.$ To find the probability of other spanning trees would be more complicated because different edge orders give different terms.

An article by David Aldous discusses this process in some detail.

We might first somehow choose a "random" subgraph of $H$ of $K_n$ with less edges and then choose a "random" spanning tree of $H$ either uniformly or using the MCST method. We will assume that if the chosen graph $H$ is not connected then we just choose again by the same process and repeat until we get a connected $H.$

Consider first choosing a random (connected) member of $G(n,m)$ the set of $m$-edge subgraphs of $K_n$, then choosing a spanning tree. In the extreme case $m=n-1$ we are directly (and uniformly) choosing a spanning tree although it will take a super exponential number of trials. For $m \gt n-1$ we need to specify how we choose a spanning tree. Let $G(n,m)(T)$ be the set of such graphs in $G(n,m)$ containing a given spanning tree $T$. When $m \gt \binom{n-1}{2}$ all the graphs in $G(n,m)$ are connected, The number of connected graphs in $G(n,m)$ is fairly easy to compute for $m$ only slightly less that that or only slightly more than $n-1.$ Otherwise it might be a bit hard. However, each set $G(n,m)(T)$ has the same size, the number of ways to choose $m-(n-1)$ of the $\binom{n}{2}-(n-1)$ other edges. The chance that first choosing a random connected member of $G(n,m)$ and then uniformly choosing a spanning subtree leads to $T$ is proportional to $$\sum_{H \in G(n,m)(T)}\frac{1}{|\mathcal{T}(H)|}.$$ At the lower end , $m=n-1$, the chance of a specific star (or any other given spanning tree) is $\frac{1}{n^{n-2}}.$ For $m=n$ we see that (for uniform or MCST selection) the probability of a given star is proportional to $\binom{n-1}{2}/3=O(n^2)$ while a given path has probability proportional to $\sum_1^{n-2}\frac{j}{n+1-j}=O(n\ln{n}).$ I suspect that , uniformly selecting a spanning tree, the probability of a star increases and of a path decreases monotonically with $m$ . For larger $m$ I suspect less difference between $G(n,m)$ and $G(n,m+1)$. If we use the MCST method to choose a spanning tree then things will be different (once $m \gt n$) although I still suspect the same thing.

Finally we get to the question: What about the model $G(n,p)$ wherewe choose each edge with probability $p$? Then the number of edges selected will be $m$ with probability $\binom{N}{m}p^m(1-p)^{N-m}$ where $N=\binom{n}{2}.$ However the requirement to choose a connected subgraph will bias against small $m.$ I suspect that as $p$ goes to zero we will approach the uniform distribution on spanning trees, this is definitely true for $n=4.$ For $p \gt 2\ln{n}/n$ we are almost sure to have a connected subgraph. So we have some combination of the distributions from $G(n,m)$ concentrated around $m=np.$

We can reverse the order in this two step process of choosing a random subgraph and then the MCST of that subgraph. First randomly weight the edges of $K_n$ uniformly from $(0,1).$ In the G(n,m) model we (may as well) retain only the $m$ lowest weight edges. In the $G(n,p)$ model we retain only those edges with weight $p$ or less. Since we already have an edge weights we can utilize them for the MCST, provided we have a connected graph. The reverse order is to first find the MCST. Then we accept it or start over according as the edges of that tree are among the first $m$ (or have weights no larger than $p$.) For any spanning tree it is possible that it is not completely chosen until we have rejected $\binom{n-2}{2}$ edges. However we have seen that the expected number of rejected edges before completion is greater for some trees than for others. When $m$ or $p$ is large, a tree with a lower expected rejection rate is favored. When $m$ or $p$ is small we are allowed fewer rejects before resetting and the distribution is more uniform.

share|improve this answer
    
I don't see why each labelled tree is equally likely. Although each tree is a spanning tree for an equal number of graphs, trees which tend to be spanning trees for graphs with fewer spanning trees in total will be more likely to be chosen. Consider for example the case where $n=4$. If we condition on the graph having $3$ edges, all trees are equally likely. The same holds true if we condition on $G$ having $5$ or $6$ edges. But suppose we condition on $G$ having $4$ edges (continued in next comment). –  Kevin P. Costello Jan 25 '13 at 5:52
2  
Then there's a $1/5$ chance that $G$ is a $4-$cycle (in which case all four spanning trees are paths), and a $4/5$ chance that $G$ is a triangle with one edge added (in which case there are only three spanning trees, one star and two paths). Combining, each of the $12$ paths has a $11/180$ chance of being chosen, while each of the $4$ stars has a $1/15=12/180$ chance. –  Kevin P. Costello Jan 25 '13 at 5:55
1  
Aldous points out in the first line of this article (stat-www.berkeley.edu/~aldous/Papers/me49.pdf) that the distribution is not the uniform distribution. –  Louigi Addario-Berry Jan 25 '13 at 13:28
    
(First paragraph, I mean.) –  Louigi Addario-Berry Jan 25 '13 at 13:28
    
@Kevin I'm not so sure about your claim conditioned on $6$ (or $5$) edges. The Aldous paper should still apply. For $K_4$ I think your $1/15, 11/180$ probabilities still apply. I suppose the fact that $n^{n-2}$ is not a multiple of $\binom{n}{2}!$ for prime $n \gt 3$ is a clue. –  Aaron Meyerowitz Jan 25 '13 at 20:12

Your Answer

 
discard

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.