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?


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.