  For a given permutation $\pi_n$ in $S_n$, a random permutation graph is
formed by including an edge between two vertices $i$ and $j$ if and only if $(i
- j) (\pi_n(i) - \pi_n (j)) < 0$. In this paper, we study various statistics of
random permutation graphs. In particular, the degree of a given node, the
number of nodes with a given degree, the number of isolated vertices, and the
number of cliques are analyzed. Further, explicit formulas for the
probabilities of having a given number of connected components and isolated
vertices are obtained.
