Sorry for the non suggestive title, I wasn't able to find a more suitable one.
Let $n\geq 1$ be an integer and consider the symmetric group $\mathfrak S_n$. For $\pi\in \mathfrak S_n$ we define its graph $\Gamma(\pi):=\{(\pi(j),j)\,|\,j\in [1,n]\}$. For $0\leq i,j \leq n$, let us define $d_{i,j}=d_{i,j}(\pi)$ as the cardinality of the set $\Gamma(\pi)\cap [1,i]\times [1,j]$. Given two permutations $\pi$ and $\pi'$, we write $\pi \leq \pi'$ whenever for all $0\leq i,j \leq n$, we have $d_{i,j}(\pi)\geq d_{i,j}(\pi')$.
On the other hand, given $\pi$ and $\pi'$ in $\mathfrak S_n$, we write $\pi \rightarrow \pi'$ whenever there exists $1\leq i < j \leq n$ such that $\pi(i)<\pi(j)$ and $\pi' = \pi\circ (i\;\;j)$.
Claim: Assume that $\pi\leq \pi'$. Then prove that there exists $k\geq 0$ and permutations $\pi_1,\ldots ,\pi_{k-1}$ in $\mathfrak S_n$ such that $$\pi = \pi_0 \rightarrow \pi_1 \rightarrow \ldots \rightarrow \pi_{k-1} \rightarrow \pi_k = \pi'$$ Here, the case $k=0$ means that $\pi = \pi'$.
I am trying to solve the exercise above but I face some troubles. I am looking for a hint rather than a complete solution. Let me now write down what I have found.
First of all, it is clear that $0\leq d_{i,j} \leq \min(i,j)$ for all $0\leq i,j \leq n$. Moreover, we also observe that $d_{i,j}(\pi)-d_{i,j-1}(\pi)$ is the cardinality of $\Gamma(\pi)\cap [1,i]\times\{j\}$. If we look at the sequence $(d_{i,j}(\pi)-d_{i,j-1}(\pi))$ for $0\leq i \leq n$, then it is a nondecreasing sequence taking values $0$ or $1$, with first value $0$ and last value $1$, and the index where the value goes from $0$ to $1$ is no other than $\pi(j)$, ie. $$\pi(j) = \min \{i\,|\,1\leq i \leq n \text{ such that } d_{i,j}(\pi)-d_{i,j-1}(\pi)=1\}$$
Given $\pi\leq \pi'$ as in the claim, let me denote $d_{i,j}:=d_{i,j}(\pi)$ and $d'_{i,j}:=d_{i,j}(\pi')$. Then, I consider the quantity $$N:= \sum_{0\leq i,j \leq n} d_{i,j}-d'_{i,j}$$ My strategy is to prove the claim by induction on the integer $N\geq 0$.
I was able to prove the case $N=0$ and the case $N=1$.
- When $N=0$ then $d_{i,j}=d'_{i,j}$ for all $i$ and $j$, and thus we have $\pi = \pi'$.
- When $N=1$ then only one $d_{i,j}$ differs from $d'_{i,j}$ and they differ by $1$. In this case, I proved that $\pi' = \pi\circ (j\;\;j+1)$ along with $\pi(j)=i$ and $\pi(j+1)=i+1$, so that we do have $\pi\rightarrow \pi'$.
For the induction hypothesis, I give myself a pair of permutations $\pi\leq \pi'$ whose associated number $N$ is at least $1$ (or even $2$ is ok). My objective is to build a permutation $\sigma$ such that $\pi \rightarrow \sigma$ and $\sigma\leq \pi'$ with an associated number strictly less than $N$.
I fix $(i,j)$ as the minimal couple such that $d_{i,j}>d'_{i,j}$ where the minimality is considered with respect to the lexicographic order with priority on the second component, ie. $$(a,b)\leq (a',b') \iff b<b' \text{ or } (b=b' \text{ and }a\leq a')$$ With such a choice, we have $d_{k,l} = d'_{k,l}$ for all $0\leq k \leq n$ and $0\leq l \leq j-1$. It follows that $\pi$ and $\pi'$ agree on $\{1,\ldots ,j-1\}$.
Moreover, one proves that $d_{i,j} = d'_{i,j}+1$, that $\pi(j)=i$ and that $\pi'(j)\geq i+1$. These are about all the information that I could find.
I tried to build $\sigma$ under the form $\sigma = \pi\circ (j\;\;t)$ for a well chosen $t>j$ such that $\pi(t)>\pi(j)=i$. I tried to consider for instance $t$ as the preimage of $\pi'(j)$.
Given such a $\sigma$, I have found that
$$d_{r,s}=\left\{
\begin{array}{ll}
d_{r,s}(\sigma) + 1& \text{whenever }j\leq s < t \text{ and }\pi(j)\leq r < \pi(t).\\
d_{r,s}(\sigma)& \text{otherwise}.\\
\end{array}
\right.$$
So the stake would be to prove that $\sigma\leq \pi'$, ie. that for every $r$ and $s$ with $j\leq s < t$ and $\pi(j)\leq r < \pi(t)$, we have $d_{r,s}>d'_{r,s}$. That is precisely where I am stuck : I can't coin down what choice of $t$ would succeed.