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

Consider a finite graph $G$. I would like to define a random path between two vertices $s$ and $t$ of the graph $G$ by looking at a measure $\mu$ on all spanning trees. Then the probability of a given path $p$ (without cycles) between $x$ and $y$ to be chosen is $\mathbb{P}(p) = \mu(T \mid p \subset T)$.

For example, if $\mu$ is the uniform measure on all spanning trees, it seems this should coincide with the random path starting at $x$ and stopping at $y$ with potential cycles deleted. [I actually have no idea if this is the case and, if so, why, and would be grateful to anyone who has a nice argument or reference]. (EDIT: see explanation in J.W.'s answer below.)

It was pointed out to me that there is another interesting measure on the space of spanning trees, namely the "minimal" measure. My question is (apologies in advance if it is well-known)

$\mathbf{Question}$: what's a random path associated to the minimal measure on spanning trees?

I'll make an attempt at describing the "minimal measure" [EDIT: corrected, thanks to J.W.'s comment below]. Take an injective function $w$ from the set of edges $E$ to $[0,1]$. Let $T_w$ be the tree of minimal cost, if $w$ is thought of as the cost of an edge. Many constructions are possible. For example, an edge $e$ belongs to $T_w$ if any path between its endpoints ($e$ excluded) contains an edge $e'$ with $w(e')>w(e)$.

Next consider $w$ given by independent uniform $[0,1]$ random variables (one on each edge). The minimal measure on the spanning trees is that of $T_w$ (where $w$ is random), i.e. $\mu(T) = \mu(w \mid T = T_w)$.

share|improve this question
2  
The "minimal measure" is not quite as you describe. I think what you mean is to take the tree of minimal total weight under $w$ (this doesn't in general have the form $\{e\in E : w(e)<x\}$ for any $x$). It is worth pointing out that the resulting distribution on trees doesn't depend on taking the weights from uniform distribution on $[0,1]$, as long as they are i.i.d. An equivalent description is to consider the edges in random uniform order, and "accept" an edge iff it does not form a cycle together with already accepted edges, and "discard" if it does. –  Johan Wästlund Jul 1 '13 at 18:44
    
Of course, thanks for your correction... –  Antoine Jul 1 '13 at 19:12
add comment

1 Answer

You might be interested in Loop Erased Random Walks and David Wilson's algorithm, see for instance http://research.microsoft.com/en-us/um/people/schramm/memorial/usf-talk.ps

share|improve this answer
    
Thanks! I could only get a quick look just now, but this seems to completely answers the (bracketed sub-)question on the uniform measure. However, I must confess I fail to see how this helps about the minimal measure. –  Antoine Jul 1 '13 at 17:32
add comment

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.