printable pdf
比利时vs摩洛哥足彩 ,
university of california san diego

****************************

nathanael berestycki

cornell university

phase transition and geometry of random transpositions

abstract:

we are originally motivated by a problem in genome rearrangement, which is to ask what is the rate of evolution induced by certain large-scale mutations called inversions. if we think of a chromosome as being made up of $n$ markers (the genes), a reversal is a mutation that chooses a segment of the chromosome and flips it around to reverse its order. traditionally, biologists have studied these questions with parsimony methods. however, it was observed numerically by bourque and pevzner that this method provides accurate results only if the number of mutations is small enough. \vskip .1in \noindent our work provides a theoretical explanation for this fact. we consider the cleaner but similar problem of random transpositions. let $\sigma_t$ be the composition of $t$ random uniform transpositions. $\sigma_t$ can be viewed as a random walk on some cayley graph of the symmetric group. if $d_t$ is the distance between $\sigma_t$ and its starting point, we prove that $d_t$ undergoes a phase transition at critical time $n/2$, from a linear to a sublinear behavior. we will then focus on the consequences of this result for the geometry of the graph. roughly speaking, our results say that the non-smooth behavior of the random walk can be associated with a change in the gromov hyperbolicity of the space. part of this talk is based on joint work with rick durrett.

host: pat fitzsimmons

january 27, 2005

9:00 am

ap&m 6438

****************************