The hyperbolic geometry of random transpositions

DOI10.1214/009117906000000043zbMATH Open1105.60073arXivmath/0411011OpenAlexW2076428246MaRDI QIDQ2496953FDOQ2496953

Authors: Nathanaël Berestycki 

Publication date: 26 July 2006

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: Turn the set of permutations of $n$ objects into a graph $G_n$ by connecting two permutations that differ by one transposition, and let $sigm{a}_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 $0<a<1$. Then when $a<1/4$, if the geodesics are suitably chosen, with high probability $T$ is $delta$-thin for some $delta>0$, 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$.

Full work available at URL: https://arxiv.org/abs/math/0411011

Recommendations

• Limiting behavior for the distance of a random walk
• On the Diameter of Random Cayley Graphs of the Symmetric Group
• Emergence of giant cycles and slowdown transition in random transpositions and \(k\)-cycles

zbMATH Keywords

phase transitionCayley graphsrandom walksrandom graphsGromov hyperbolic spaces

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Sums of independent random variables; random walks (60G50) Combinatorial probability (60C05)

Cites Work

• Probability. Theory and examples.
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Logarithmic combinatorial structures: A probabilistic approach
• Poisson–Dirichlet and GEM Invariant Distributions for Split-and-Merge Transformations of an Interval Partition
• Compositions of random transpositions
• Title not available (Why is that?)
• Random Oxford graphs

Cited In (4)

• Gibbs measures on permutations over one-dimensional discrete point sets
• Cayley graphs and complexity geometry
• Gibbs distributions for random partitions generated by a fragmentation process
• Cutoff for conjugacy-invariant random walks on the permutation group

This page was built for publication: The hyperbolic geometry of random transpositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2496953)