On random trees obtained from permutation graphs

A permutation w gives rise to a graph Gw; the vertices of Gw are the letters in the permutation and the edges of Gw are the inversions of w. We find that the number of trees among permutation graphs with nn vertices is 2n−22n−2 for n≥2n≥2. We then study TnTn, a uniformly random tree from this set of trees. In particular, we study the number of vertices of a given degree in TnTn, the maximum degree in TnTn, the diameter of TnTn, and the domination number of TnTn. Denoting the number of degree-kk vertices in TnTn by DkDk, we find that (D1,…,Dm)(D1,…,Dm) converges to a normal distribution for any fixed mm as n→∞n→∞. The vertex domination number of TnTn is also asymptotically normally distributed as n→∞n→∞. The diameter of TnTn shifted by −2−2 is binomially distributed with parameters n−3n−3 and 1/21/2. Finally, we find the asymptotic distribution of the maximum degree in TnTn, which is concentrated around log2nlog2n.