On the connected components of a random permutation graph with a given number of edges

Huseyin Acan, Boris Pittel

A permutation of [n] induces a graph on [n] such that the edges of the graph correspond to inversion pairs of the permutation. This graph is connected if and only if the correspond…