The hyperbolic geometry of random transpositions

Details The hyperbolic geometry of random transpositions The hyperbolic geometry of random transpositions

2004-10-31

arxiv.org/abs/math/0411011v3

Annals of Probability 2006, Vol. 34, No. 2, 429-467

Mathematics

Probability

Published at http://dx.doi.org/10.1214/009117906000000043 in the Annals of Probability (http://www.imstat.org/aop/) by the Ins

Scientific paper

10.1214/009117906000000043

Turn the set of permutations of $n$ objects into a graph $G_n$ by connecting two permutations that differ by one transposition, and let $\sigma_t$ be the simple random walk on this graph. In a previous paper, Berestycki and Durrett [In Discrete Random Walks (2005) 17--26] showed that the limiting behavior of the distance from the identity at time $cn/2$ has a phase transition at $c=1$. Here we investigate some consequences of this result for the geometry of $G_n$. Our first result can be interpreted as a breakdown for the Gromov hyperbolicity of the graph as seen by the random walk, which occurs at a critical radius equal to $n/4$. Let $T$ be a triangle formed by the origin and two points sampled independently from the hitting distribution on the sphere of radius $an$ for a constant $00$, whereas it is always O(n)-thick when $a>1/4$. We also show that the hitting distribution of the sphere of radius $an$ is asymptotically singular with respect to the uniform distribution. Finally, we prove that the critical behavior of this Gromov-like hyperbolicity constant persists if the two endpoints are sampled from the uniform measure on the sphere of radius $an$. However, in this case, the critical radius is $a=1-\log2$.

Affiliated with

Also associated with

No associations

Rating

The hyperbolic geometry of random transpositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The hyperbolic geometry of random transpositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The hyperbolic geometry of random transpositions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-286661