Maximum of absolute differences inequality Let $x_1 < x_2  < \cdots < x_q$ and $y_1 < y_2  < \cdots < y_q$ be two monotonic sequences of real numbers. Then, I want to show
\begin{align}
 \max_k |x_k - y_{\sigma(k)}| \geq   \max_k |x_k - y_k|, ~~~~~~~~~~~~~~~~~~~~~~~~~(1)
\end{align}where $\{y_{\sigma(1)}, y_{\sigma(2)}, \ldots, y_{\sigma(q)}\}$ is a permutation of $\{y_1, y_2, \ldots, y_q\}$.
I found out this solution, using which I can show \begin{align*}
 \left(\sum_{k=1}^q |x_k - y_{\sigma(k)}|^r\right)^{1/r} \geq  \left(\sum_{k=1}^q |x_k - y_k|^r \right)^{1/r} ~~~~~~~~~~~~~~~~~~~~~~~~~(2)
\end{align*} for all $r$. I cannot apply the mazorization theory to prove (1) directly as the maximum-absolute function is not convex. However, if I apply $r\to \infty$ on both the sides of (2), I can obtain (1).
My question: I am wondering if there is a way to directly prove (1) (without using r-norm and, possibly, mazorization theory)?
 A: The idea is the same as in the proof of the rearrangement inequality or in Inequality involving rearrangement: $ \sum_{i=1}^n |x_i - y_{\sigma(i)}| \ge \sum_{i=1}^n |x_i - y_i|. $: Show that if there are $i< j$ with $\sigma(i) > \sigma(j)$ then the left-hand side of $(1)$ does not increase if $\sigma(i)$ and $\sigma(j)$ are exchanged.
It then follows that the permutation which minimizes the left-hand side of $(1)$ and has the last possible number of inversions is necessarily the identity permutation.
In other words, it suffices to prove the inequality for $q=2$ and the permutation which exchanges indices $1$ and $2$. Actually we can prove strict inequality for $q=2$, but not for $q \ge 3$.

Let  $x_1 < x_2$ and $y_1 < y_2$. Then
$$ \tag{$*$}
 \max( |x_1 - y_1|, |x_2 - y_2|) < \max(|x_1-y_2|, |x_2-y_1|) \, .
$$

Case 1: $x_1 + x_2 \le y_1 + y_2$. Then
$$
 x_1 < \frac 12 (x_1+x_2) \le \frac 12 (y_1 + y_2) 
\implies |x_1 - y_1| < |x_1 - y_2|
$$
and
$$
 \frac 12 (x_1+x_2) \le \frac 12 (y_1 + y_2) < y_2 
\implies |y_2 - x_2| < |y_2 - x_1| \, .
$$
It follows that
$$
 \max( |x_1 - y_1|, |x_2 - y_2|) < |x_1 - y_2|
$$
and that implies $(*)$.
Case 2: $x_1 + x_2 > y_1 + y_2$ works similarly, now we get
$$
 \max( |x_1 - y_1|, |x_2 - y_2|) < |x_2 - y_1| 
$$
which again implies $(*)$.
Remark: The rearrangement inequality is strict if the $x_i$ and $y_i$ are distinct and $\sigma$ is not the identity permutation. That is not the case here if $q \ge 3$. An example is
$$
 (x_1, x_2, x_3) = (1, 2, 3) \\
 (y_1, y_2, y_3) = (1, 2, 5) 
$$
with
$$
 \max(|x_1-y_2|, |x_2-y_1, |x_3-y_3|) = 2 = \max(|x_1-y_1|, |x_2-y_2, |x_3-y_3|) \, .
$$
