2
$\begingroup$

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 :)

$\endgroup$
5
  • $\begingroup$ Are your permutations in "line form" like if $n=4$ then $1432$ maps 1 and 3 to themselves and interchanges 2 and 4? [Or in cycle form or etc.] $\endgroup$
    – coffeemath
    Nov 11, 2021 at 11:21
  • 1
    $\begingroup$ They are in line form. $\endgroup$
    – reservoir
    Nov 11, 2021 at 11:25
  • $\begingroup$ math.stackexchange.com/q/2492954 $\endgroup$
    – Jean Marie
    Nov 11, 2021 at 11:44
  • $\begingroup$ I had found that post. It is interesting, but does not appear to address any of my questions. $\endgroup$
    – reservoir
    Nov 11, 2021 at 11:49
  • $\begingroup$ About the first conjecture $d_{sum} \ge d_{swap}$: For which small $n$ have you checked it? E.g. checked for $n\le 10$. It seems a program could be made to check it, I wonder when the checking time gets unmanagably long in terms of $n$. [That likely depends on software used.] $\endgroup$
    – coffeemath
    Nov 11, 2021 at 19:37

1 Answer 1

1
$\begingroup$

This problem was studied by Diaconis and Graham: Spearman's Footrule as a Measure of Disarray.

What you call $d_{\text{swap}}$ they call $I$, and what you call $d_{\text{sum}}$ they call $D$. They show

$$I + T \leq D \leq 2 I$$

where $T$ is the number of transpositions needed to put the permutation in order, also called the reflection-length of a permutation. This language comes from the study of Coxeter Groups.

$\endgroup$
1
  • $\begingroup$ Hello, thanks for your answer! I should have mentioned that I ended up asking the question on Mathoverflow (see link) where I received the same answer. $\endgroup$
    – reservoir
    Oct 17, 2023 at 9:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .