Let $σ = 42153$ be a permutation of {$1, 2, . . . , 5$}.
(a) Draw the bipartite graph corresponding to $σ$.
(b) How many inversions does σ have?
(c) Write σ as a product of elementary transpositions
The bipartite graph is needed to get the elementary transpositions but I dont know how to draw it on here.
(b) In the graph there are 5 intersecting edges, so there are 5 inversions.
(c) now this is where I am stuck. The answer shows that the elementary transpositions are as follows, $σ = s_3s_4s_1s_2s_1$ and I should be able to get it by looking at the intersections in the bipartite graph but I dont understand how.
For instance, the first inversion is the intersection of edge $14$ and $22$ which should correspond to $s_1$.
The second inversion is the intersection of edge $22$ and $31$ which should correspond to $s_2$, but how exactly do I get the elementary transposition by looking at the intersection?
It is like sorting, first you want $3$ to be moved to the end so you do $s_3s_4$, then you want $5$ to be moved to the second last but it is already there so you do nothing, then you want $1$ to be moved to the third last so you do $s_1s_2$, and then you want $1$ to be moved to the second place so you do $s_1$ and lastly $4$ is automatically done.