This page is still UNDER CONSTRUCTION. I apologize for the deficient presentation and the lack of details. More will be coming soon !



<center> 
<img src="rtrw.gif" align=center width=500>
</center>

We can view the symmetric group over n symbols (i.e., the set of all permutations of those n symbols) as a graph, where there is an edge between two permutations if they differ by a transposition. The graph that we obtain this way is called the Cayley graph of S_n associated with the set of generators given by all transpositions. The picture above represents the Cayley graph of S_n for n=5. There are 5!=120 vertices and 5!(5(5-1)/2)/2= 600 edges.

<p>

In my <a href="0403259.pdf">paper</a> with Rick Durrett, I have studied the simple random walk on this graph and proved that it exhibits a striking phase transition.

<p> The consequences of this result for the geometry of the graph are analyzed in my second <a href="geometry4.pdf">paper</a> which has just appeared on the arXiv. I prove that this phase transition is directly linked with the change of a quantity called the Gromov hyperbolic constant.

<p>It is interesting to contrast this picture with the case of <a href="adj.html">adjacent transpositions</a>: the picture shows a very different geometry, and  Rick Durrett and I will prove in a forthcoming paper that the behavior of the random walk is also very different.

<p>For more explanations, as well as motivation for studying this problem (we were originally motivated by a problem in genome rearrangement), see my <a href="r-stat.pdf"> research statement</a>.

<p> This picture is courtesy of <a href="http://www.math.cornell.edu/~armstron">Drew Armstrong</a> from Cornell University - many thanks to him