A study on random permutation graphs

Abstract

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.

21 pages, 1 figure

References in corpus (1)

• Normal approximation for nonlinear statistics using a concentration inequality approach