1. ## Inversions

Hello!

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

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

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

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

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

I can't see why this is wrong, $\displaystyle \pi(1)=2$ and $\displaystyle \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 $\displaystyle \{(i,j)\mid\pi(i)=j\}$? If $\displaystyle (i, j)$ is an inversion according to your definition, it is not required that $\displaystyle \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 $\displaystyle \pi$, denoted $\displaystyle G[\pi]$, has $\displaystyle \{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).