Discrete Mathematics & Theoretical Computer Science |

- 1 Department of Mathematics [Cornell]
- 2 École normale supérieure - Paris

Our work is motivated by Bourque-Pevzner's simulation study of the effectiveness of the parsimony method in studying genome rearrangement, and leads to a surprising result about the random transposition walk in continuous time on the group of permutations on $n$ elements starting from the identity. Let $D_t$ be the minimum number of transpositions needed to go back to the identity element from the location at time $t$. $D_t$ undergoes a phase transition: for $0 < c ≤ 1$, the distance $D_cn/2 ~ cn/2$, i.e., the distance increases linearly with time; for $c > 1$, $D_cn/2 ~ u(c)n$ where u is an explicit function satisfying $u(x) < x/2$. Moreover we describe the fluctuations of $D_{cn/2}$ about its mean at each of the three stages (subcritical, critical and supercritical). The techniques used involve viewing the cycles in the random permutation as a coagulation-fragmentation process and relating the behavior to the Erdős-Rényi random graph model.

Source: HAL:hal-00001309v3

Volume: DMTCS Proceedings vol. AC, Discrete Random Walks (DRW'03)

Section: Proceedings

Published on: January 1, 2003

Imported on: May 10, 2017

Keywords: random transposition,random graphs,phase transition,coagulation-fragmentation,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

This page has been seen 174 times.

This article's PDF has been downloaded 296 times.