0
$\begingroup$

Let T be uniform spanning tree on complete graph $K_n$ (Or equivalently, uniform tree on n-vertices.) Suppose, I choose two vertices, say $u$ and $v$, and look at the graph distance between them in T. Then I can write an explicit formula for the distribution of this new random variable $D_2$. After a suitable scaling it can also be shown that this distribution converges to Rayleigh distribution. Now, if I start with three vertices (as leaves), and I want to understand the joint distribution of the distance between $(v_1,v_2), (v_2,v_3), (v_1,v_3)$. In order to do this, we change the question a little bit by observing that if a tree has 3 leaves, it must have exactly 3 legs. And, we can ask for the joint distribution of length of legs. I wrote an explicit formula for the case when we have 3 leaves and 3 legs. It is already well-known that the joint distribution of graph distance between k vertices converges in distribution (after scaling) to a distribution called $F_k$. The proof is given in a paper due to Peres. But, since the complete graph is relatively easier case, I am interested in knowing the explicit joint distribution of the graph distance between vertices. For more than 3 legs, I could not write an explicit description. Can someone suggest me a place where I can look it up, or can someone hint at what should the joint distribution look like?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.