1. ## Inversions

Hello!

I'm not quite understanding this idea of inversions. I know that if $\pi$ is a permutation, then a pair $(i,j)$ is an inversion if $(i-j)(\pi (i)- \pi (j))<0$.

The graph of $\pi$ has $i$ and $j$ as adjacent iff $(i,j)$ is an inversion.

I think I understand that. I have this big problem though:

Suppose $\pi=(1234)$. These are the points $1,2,3,4$ connected in a square shape. Clearly $1$ and $2$ are adjacent.

But, the formula gives for $(1,2)$ (this is just a pair, it isn't permutation notation?), $(1-2)(2-3)>0$.

I can't see why this is wrong, $\pi(1)=2$ and $\pi(2)=3$ since we're just following the path around the square.

Can someone explain why this is wrong?

2. I think we need to double-check the definitions. This statement looks suspicious:

The graph of has and as adjacent iff is an inversion.
What is the graph of a permutation? Is it the directed graph with edges $\{(i,j)\mid\pi(i)=j\}$? If $(i, j)$ is an inversion according to your definition, it is not required that $\pi(i)=j$.

By the way, how do you write permutations? E.g., is (1234) the identity permutation or a cycle 1->2->3->4->1?

3. I normally write permutations as cycles. It was how I first learnt how to do them, and I think they usually show cycles better (or at least I think so anyway!).

I have the definition in front of me:

"The graph of permutation $\pi$, denoted $G[\pi]$, has $\{1,2, \ldots , n \}$ as it's vertex set with i and j being adjacent iff (i,j) is an inversion.

So if i'm calculating inversions properly, the graph (1,2,3,4) (as a cycle) wouldn't be a permutation graph. Maybe that's what's going wrong? =S

4. the graph (1,2,3,4) (as a cycle) wouldn't be a permutation graph.
Yes, according to this definition, the graph of the permutation (1234) has edges (1,4), (2,4) and (3,4).