Why are there no cycles in this "1234-graph" on the permutations

Question

Fix $n\in\mathbb N$, and consider the following directed graph whose vertices are the permutations of length $n$:

For a permutation $p=[p_1,..., p_j, ..., p_k, .., .p_n]$ with if $p_j+j=k$, then there is an edge from $p$ to $[p_1, ..., p_k, ..., p_j, ..., p_n]$. In words: In the list that is the permutation, a number $x$ can swap its position with the number $x$ places to its right.

For example, for n=6 there are edges from 123456 to 213456, to 143256, and to 126453.

The whole 1234-graph¹ looks like this for n=3:

123 → 213 → 312 → 321
       ↓     ↑
      231 → 132

_{¹) I'll name it 1234-graph, since it is really nice for n=4, and planar too. In fact, it is just the right degree of difficult to draw in the plane that it makes a nice half-an-hour puzzle.}

It appears that, regardless of $n$, this graph has no cycles; and it sure feels like there should be a relatively simple reason, for example a half-ordering / monovariant based on the contents. Or an inductive proof reducing the question to the smaller graph on permutations of length $n-1$. Why are there no cycles?

Answer 1

The terminal of the graph is always $$ (n \ n-1 \ n-2 \ \dots \ 3 \ 2 \ 1) $$ as this is the only permutation in which no symbol can be swapped.

There is no edge whose reverse is already in the graph. That is, there are no bidirectional edges. Such a pair of directed edges would require that the two swapped symbols be the same, which cannot happen, so there is at most one directed edge between any two permutations.

A trail in the graph is a sequence of shellsort moves (of differing gap), eventually pushing small symbols to the right and large symbols to the left. Consider the graph of a permutation. (The graph of the points $(i,p_i)$ with line segments drawn between points with successive $i$s.) A line of slope $-1$ corresponds to the final state, the permutation displayed above. Any position in the permutation whose point is on or above that line contains a number too big to swap to its right. Any position whose point is below that line can swap to the right -- any such swap reduces the area of the graph above the line. That area strictly monotonically decreases along any trail in the graph, so there can be no cycles in the graph.

Answer 2

Actually, for n=5, this is a cycle:

$13254→14253→14352→41352→21354→23154→13254$

And copies of this cycle appear in all graphs for larger $n$.