Georgia Institute of Technology College of Sciences

A permutation of the set {1,2,...,n} is connected if there is no k < n such that the set of the first k numbers is invariant as a set under the permutation. For each permutation, there is a corresponding graph whose vertices are the letters of the permutation and whose edges correspond to the inversions in the permutation. In this way, connected permutations correspond to connected permutation graphs. We find a growth process of a random permutation in which we start with the identity permutation on a fixed set of letters and increase the number of inversions one at a time. After the m-th step of the process, we obtain a random permutation s(n,m) that is uniformly distributed over all permutations of {1,2,...,n} with m inversions. We will discuss the evolution process, the connectedness threshold for the number of inversions of s(n,m), and the sizes of the components when m is near the threshold value. This study fits into the wider framework of random graphs since it is analogous to studying phase transitions in random graphs. It is a joint work with my adviser Boris Pittel.