Consider the following two metrics on permutations of $\{1,2,\dots,n\}$:
$d_{swap}(\sigma,\tau)$ is the minimum number of swaps of adjacent elements that are required to reach $\tau$ from $\sigma$ (or $\sigma$ from $\tau$). Alternatively, it is the number of discordant pairs for $\sigma$ and $\tau$. A pair of distinct elements $(x,y)$ is called a discordant pair for $\sigma$ and $\tau$ if $x$ and $y$ have different relative orderings in the two permutations. If I am not missing anything, $d_{swap}$ is identical to the Kendell tau distance.
$d_{sum}(\sigma, \tau)$ is given by $\sum_{i=1}^n |pos_{\sigma}(i) - pos_{\tau}(i)|$, where $pos_{\pi}$ indicates the position of $i$ in the permutation $\pi$.
I need to understand the relationship between these two metrics for another problem I am working on. In particular, I would like to know whether the following two conjectures I have are true:
- $d_{sum} \geq d_{swap}$
- there exists a constant $C < 1$, such that $d_{swap} \geq C \cdot d_{sum}$
While I am sure that these distances have been well studied, I did not manage to find the answer to these questions. If you know the answer or even any relevant literature feel free to help me out :)