Permutation graph and the number of inversion statistics

94 Views Asked by At

Let $K_m$ be the number of m-cliques, $m \in N$, in a random permutation graph $G_n$ with $n$ vertices and $\pi_n$ is the corresponding permutation representation in $S_n$. I am looking for a basic explanation of the facts:

  1. $K_1=n$ and $K_2$ is the number of edges in $G_n$ is the number of inversions in $\pi_n$ (denoted by $Inv(\pi_n)$). Why so?

  2. Why the permutation statistic $Inv(\pi_n)$ satisfies the central limit theorem $$ \left| P\left( \frac{\mathrm{Inv}(\pi)-\frac 12{n\choose 2}}{\sqrt{n(n-1)(2n+5)/72}}\leq x\right)-\Phi(x)\right| \leq \frac{C}{\sqrt{n}}, $$ where $\Phi(x)$ denotes the standard normal distribution.

Any basic explanations on that topics are highly welcomed.

Reference: A study on random permutation graphs, part 2, page 4.