Degree sequence of random permutation graphs

In this paper, we study the asymptotics of the degree sequence of permutation graphs associated with a sequence of random permutations. The limiting finite-dimensional distributions of the degree proportions are established using results from graph and permutation limit theories. In particular, we show that for a uniform random permutation, the joint distribution of the degree proportions of the vertices labeled .nr.., .nr.., ..., .nrs. in the associated permutation graph converges to independent random variables D(r.), D(r.), ..., D(rs), where D(ri) ~ Unif(ri, 1 - ri, for ri . [0, 1] and i . {1, 2, ..., s}. Moreover, the degree proportion of the mid-vertex (the vertex labeled n/2) has a central limit theorem, and the minimum degree converges to a Rayleigh distribution after an appropriate scaling. Finally, the asymptotic finite-dimensional distributions of the permutation graph associated with a Mallows random permutation is determined, and interesting phase transitions are observed. Our results extend to other nonuniform measures on permutations as well.