On random trees obtained from permutation graphs

Abstract

A permutation $\mathbf{w}$ gives rise to a graph $G_{\mathbf{w}}$; the vertices of $G_{\mathbf{w}}$ are the letters in the permutation and the edges of $G_{\mathbf{w}}$ are the inversions of $\mathbf{w}$. We find that the number of trees among permutation graphs with $n$ vertices is $2^{n-2}$ for $n\ge 2$. We then study $T_n$, a uniformly random tree from this set of trees. In particular, we study the number of vertices of a given degree in $T_n$, the maximum degree in $T_n$, the diameter of $T_n$, and the domination number of $T_n$. Denoting the number of degree-$k$ vertices in $T_n$ by $D_k$, we find that $(D_1,\dots ,D_m)$ converges to a normal distribution for any fixed $m$ as $n\to \infty$. The vertex domination number of $T_n$ is also asymptotically normally distributed as $n\to \infty$. The diameter of $T_n$ shifted by $-2$ is binomially distributed with parameters $n-3$ and $1/2$. Finally, we find the asymptotic distribution of the maximum degree in $T_n$, which is concentrated around ${\log }_{2}n$.

arXiv comment17 pages

References in corpus (1)

• On Degrees in the Hasse Diagram of the Strong Bruhat Order