On generalization of rearrangement inequality

Question

In fact, I'm intrested in such a question:

---

If $\sigma$ and $\pi$ are two permutations of $\{1,2,\ldots,n\}$ what is necessary and sufficient condition to be the following statement true. For all $a_1\geqslant a_2\geqslant \ldots \geqslant a_n$ and $b_1\geqslant b_2\geqslant \ldots \geqslant b_n$ $$ a_1b_{\sigma(1)}+a_2b_{\sigma(2)}+\ldots+a_nb_{\sigma(n)}\geqslant a_1b_{\pi(1)}+a_2b_{\pi(2)}+\ldots+a_nb_{\pi(n)} $$

---

Consider graph $G$ with elements of $S_n$ as a vertices and connect $\sigma$ and $\pi$ from $\sigma$ to $\pi$ when $\sigma(i)=\pi(i)$ for all $i\in \{1,2,\ldots,n\}\setminus \{k,l\}$, $\sigma(k)=\pi(l)$, $\sigma(l)=\pi(k)$ and $\sigma(k)>\sigma(l)$.

Then for all $a_1\geqslant a_2\geqslant \ldots \geqslant a_n$ and $b_1\geqslant b_2\geqslant \ldots \geqslant b_n$ we have $$ a_kb_{\sigma(k)}+a_lb_{\sigma(l)}-a_kb_{\pi(k)}-a_l{\pi(l)}= (a_k-a_l)(b_{\sigma(k)}-b_{\sigma(l)})\geqslant 0 $$

In fact, if we can go from $\sigma$ to $\pi$ in $G$ then we can with certainty state that the inequality holds.

On the other hand, let's consider $\sigma$, $\pi\in S_3$: $\sigma(1)=1$, $\sigma(2)=3$, $\sigma(3)=2$ and $\sigma(1)=2$, $\sigma(2)=1$, $\sigma(3)=3$. Then $$ 1\cdot 1+0\cdot 0+0\cdot 0\geqslant 1\cdot 0+0\cdot 1+0\cdot 0 $$ and $$ 0\cdot 0+0\cdot (-1)+(-1)\cdot 0\leqslant 0\cdot 0+0\cdot 0+(-1)\cdot (-1) $$

So, I have no idea what to do in most general case.

Answer 1

Necessary and sufficient condition is the following: for all $k\in \{1,\dots,n\}$, the sequence $\sigma(1),\dots,\sigma(k)$ strongly minorates $\pi(1),\dots,\pi(k)$, that means: if $u_1\leqslant \dots \leqslant u_k$ is increasing permutation of $\sigma(1),\dots,\sigma(k)$ and $v_1\leqslant \dots \leqslant v_k$ is increasing permutation of $\pi(1),\dots,\pi(k)$, then $u_i\leqslant v_i$ for all $i=1,\dots,k$.

At first, why is it necessary. Assume that it fails for some $k$, choose such a $k$ and set $a_1=\dots=a_i=1$, $a_{i+1}=\dots=a_n=0$. We get $b_{\sigma(1)}+\dots+b_{\sigma(k)}\geqslant b_{\pi(1)}+\dots+b_{\pi(k)}$. Fix $i\leqslant k$ such that $u_i>v_i$ and consider a sequence $b_m=\chi_{m\leqslant v_i}$. Then $b_{\pi(1)}+\dots+b_{\pi(k)}=i$, $b_{\sigma(1)}+\dots+b_{\sigma(k)}\leqslant i-1$, a contradiction.

Now why is it sufficient. As usual in such situations, we apply Abel transform. Denote $a_k=a_n+(c_{k}+\dots+c_{n-1})$ for $k=1,\dots,n-1$. Then $c_i\geqslant 0$ and we have $$ \sum a_ib_{\sigma(i)}=a_n\sum b_i+\sum_{k=1}^{n-1} c_k(b_{\sigma(1)}+\dots+b_{\sigma(k)}). $$ Rewrite analogously $\sum a_ib_{\pi(i)}$ and note that for each $k$ $$ b_{\sigma(1)}+\dots+b_{\sigma(k)}=b_{u_1}+\dots+b_{u_k}\geqslant b_{v_1}+\dots+b_{v_k}=b_{\pi(1)}+\dots+b_{\pi(k)}. $$