  In this paper we study the degree sequence of the permutation graph
$G_{\pi_n}$ associated with a sequence $\pi_n\in S_n$ of random permutations.
Joint limiting distributions of the degrees are established using results from
graph and permutation limit theories. In particular, for the uniform random
permutation, the joint distribution of the degrees of the vertices labelled
$\lceil nr_1 \rceil, \lceil nr_2 \rceil, \ldots, \lceil nr_s \rceil$ converges
(after scaling by $n$) to independent random variables $D_1, D_2, \ldots, D_s$,
where $D_i\sim \text{Unif}(r_i, 1-r_i)$, for $r_i\in [0,1]$ and $i\in \{1, 2,
\ldots, s\}$. Moreover, the degree of the mid-vertex (the vertex labelled
$n/2$) has a central limit theorem, and the minimum degree converges to a
Rayleigh distribution after appropriate scalings. Finally, the limiting degree
distribution of the permutation graph associated with a Mallows random
permutation is determined, and interesting phase transitions are observed. Our
results extend to other exponential measures on permutations.

Probability;Combinatorics