5
$\begingroup$

I think this problem should have a known solution, but I wasn't able to find any reference.

Consider a multiset of size $n \cdot m$: it has $n$ elements, and all element multiplicities equal to $m$.

What is the maximum number of transpositions (swaps) needed to make two permutations of the multiset equal, in the worst case?

When $m = 1$ the result is well known and is $n-1$, but what about $m \ge 2$?

$\endgroup$
2
  • 1
    $\begingroup$ Let $\sigma_1, \sigma_2$ be two permutations of the multiset $M$ under consideration and let $w(\sigma_1, \sigma_2)$ be the least number of transpositions required to turn $\sigma_1$ into $\sigma_2$. Set $w(m, n) = \max_{\sigma_1, \sigma_2} w(\sigma_1, \sigma_2)$. For $\sigma \in \text{Sym}(n)$, let $M(\sigma)$ be the permutation of $M$ defined by the sequence $(\sigma(1), \dots, \sigma(1), \sigma(2), \dots, \sigma(2), \dots, \sigma(n), \dots, \sigma(n))$. Then we have $w(m, n) \le 2m((n - H(n) + (n - 1))$ and it is tempting to believe that $w(m, n) \ge m(n - 1)$ (true when $m \le 3$). $\endgroup$
    – Luc Guyot
    Jan 2 at 21:08
  • 1
    $\begingroup$ ... To get the upper bound: first turn $\sigma_1$ into the "closest" $M(\sigma)$ (first summand) and then turn this $M(\sigma)$ into $M(id)$ (second summand, where the maximum reflection length, that is $n - 1$, comes into play). Since $w(\sigma_1, \sigma_2) = w(id, \sigma_2 \sigma_1^{-1})$, we actually have $w(m, n) \le m(n - H(n) + (n - 1))$ where $H(n) = 1 + \frac{1}{2} + \cdots + \frac{1}{n}$ (we have removed the factor $2$). $\endgroup$
    – Luc Guyot
    Jan 2 at 21:53

2 Answers 2

1
$\begingroup$

The minimum number of transposition in a product decomposition is $n-s$ where $s$ is the number of cycles in the permutation. Lets call it the transposition number.

The problem here is equivalent to finding the smallest number of transpositions to transform a permutation of the multiset to the canonical one, which we will define as $11...122...2...nn...n$.

Lets call a valid labeling a labeling of a permutation using labels $1_1, 1_2, ..., 1_m, 2_1, ..., 2_m,...n_1,...n_m$, so that a $k$ can only get a label $k_i, 1\leq i\leq n$

Our problem becomes equivalent to finding the minimum transposition number over all valid labelings of our permutation where the identity is labeled $\sigma_0 = 1_11_2...1_m2_12_2...2_m...n_1n_2...n_m$.

We first show that we can find a valid labeling with permutation number less than $m(n-1)$

We do it greedily: Let $\sigma = a_1a_2...a_{nm}$ be the multiset permutation. let $\sigma(a_i)$ be the first valid label not attributed (${a_i}_1$ if no label $a_i$ attributed, then ${a_i}_2$, etc.)

We compute the sequence $u_1 = a_1$, $u_n$ is the element of $\sigma$ at index $\sigma(u_{n-1})$ in $\sigma_0$ until we reach a cycle (that will happen when we meet a value for the second times.

For each element on the cycle only, we set the corresponding label. We iterate until all labels are attributed.

We repeat from an element with no label until every element has a label. At the end, we get a valid labeling. All the cycles find have length less than $n$, so there is more than $m$ cycle, hence transposition number is lower than $mn-m = m(n-1)$

Example: If $\sigma = a_1...a_6 = 323121$ We get the sequence $a_1, a_5, a_3, a_5...$ so we set the labels only for $a_3$ and $a_5$, so we get: $323_112_11$

We start again, from $a_1$ since it still does not have a label yet. We get the sequence $a_1, a_6, a_1, ...$. We set the labels for $a_1$ and $a_6$, so we get: $\sigma = a_1...a_6 = 3_223_112_11_1$

Continuing the process we then get $a_1...a_6 = 3_22_23_11_22_11_1$. We have $3$ cycles so the transposition number is $nm-3 \leq m(n-1)$

We then exhibit a permutation that attains this bound

We easily verify that any valid labeling of $\sigma = 22...2...nn...n11...1$ induces less than $m$ cycles, so the transposition number will always be $mn-m$.

Example: $2_12_22_31_21_11_3$ induces 2 cycles, and $2_12_22_31_11_21_3$ indices 3 cycles (the maximum)

$\endgroup$
4
  • $\begingroup$ Could you give an example for the last statement? $\endgroup$ Jan 15 at 10:45
  • $\begingroup$ @FabiusWiesner done, there was a slight mistake, we can have less than $m$ cycles (but not more) $\endgroup$
    – caduk
    Jan 15 at 13:52
  • $\begingroup$ Many thanks for your input. I think I get the second part: there is a surjective forgetful map from $\text{Sym}(mn)$ (the labeled permutations) onto the permutations of the OP's multiset (those are label-less permutations), that is, the natural map $\text{Sym}(mn) \rightarrow \text{Sym}(mn) / \text{Sym}(m)^n$. Then you exhibit a special element $\sigma$ such that $\sigma \theta$ has exactly $m$ cycles for every $\theta \in \text{Sym}(m)^n$. This means that the reflection length of $\sigma \theta$ is $m(n - 1)$ for every $\theta$. Hence $\sigma$, as a permutation of the multiset ... $\endgroup$
    – Luc Guyot
    Jan 15 at 21:36
  • $\begingroup$ ... cannot be the product of less than $m(n - 1)$ transpositions. $\endgroup$
    – Luc Guyot
    Jan 15 at 21:39
4
$\begingroup$

The question relates to the numbers $H(n, m)$ of the Anand–Dumir–Gupta conjectures solved by Richard Stanley, see e.g. [1] (this MO post set me on this track).

Indeed, we have:

Claim 1. Let $M = \{m \cdot a_1, \dots, m \cdot a_n\}$ be a multiset of size $mn$ consisting of $n$ elements $a_1, \dots, a_n$, each with multiplicity $m$. Let $X = (x_s)_{1 \le s \le mn}$ with $x_s \in \{a_1, \dots, a_n\}$ be a permutation of $M$ and let $\mu = (\mu_{i, j})_{1 \le i, j \le n} \in \mathbb{Z}_{\ge 0}^{n \times n}$ be the matrix defined by $$\mu_{i, j} = \#\left\{s \, \vert \, x_s = a_j,\, im + 1 \le s \le (i + 1)m\right\}.$$ Then the sum of every row and every column of $\mu$ is $m$.

Proof. A straightforward verification.

Note. The integer $H(n, m)$ of the Anand–Dumir–Gupta conjectures is the number of matrices in $\mathbb{Z}_{\ge 0}^{n \times n}$ with constant row and column sums equal to $m$, see [1]. The original distribution problem that motivated [2] is due to Kenji Mano; it was first investigated in [3].

We shall establish the following simple fact:

Claim 2. Let $M$ be a multiset as in Claim 1. Any two permutations of $M$ can be related by means of at most $m(n - 1)$ swaps.

Notation. Let $w(X, Y)$ be the minimum number of swaps required to turn $X$ into $Y$, for $X$ and $Y$ two permutations of $M$ and $M$ as in Claim 1. Let $w(m, n) = \max_{X, Y} w(X, Y)$. Then Claim 2 states that $$w(m, n) \le m(n - 1).$$

Our proof relies on the following straightforward lemma:

Lemma. Let $M$ be as in Claim 1 and let $X$ and $Y$ be two permutations of $M$. Then we have $$w(X \sigma, Y \sigma) = w(X, Y)$$ for every $\sigma \in \text{Sym}(mn)$.

Proof. The key fact is that conjugating a product of $k$ transpositions in $\text{Sym}(mn)$ results in a product of $k$ transpositions.

Proof of Claim 2. Let $X$ be a permutation of $M$. For each $i \in \{1, \dots, n - 1\}$, we need at most $m$ swaps to move the $m$ elements of $X$ equal to $a_i$ so that they occupy the positions from $(i - 1)m + 1$ to $im$. Thus it suffices to apply $m(n - 1)$ swaps to $X$ to turn it into the permutation $$(a_1 \cdots a_1 a_2 \cdots a_2 \cdots a_{n - 1} \cdots a_{n - 1} a_n \cdots a_n).$$ Since $\text{Sym}(mn)$ acts transitively on the permutations of $M$, the result now follows from the above lemma.

It seems now natural to ask:

Question. Is the upper bound of Claim 2 a tight bound? More specifically, does $w(m,n) \ge m(n - 1)$ hold?


In my initial answer, I thought that the following results could be useful. (As of now, it's unclear to me how they could help).

Lemma 1 (Birkhoff-von Neumann Theorem, see [1, Theorem 1.1]). Let $\mu \in \mathbb{Z}_{\ge 0}^{n \times n}$ be a matrix such that the sum of every of its rows and of every of its columns is $m$. Then $\mu$ is a sum of $m$ permutation matrices.

Our strategy is rather naive. It consists in showing that a permutation of $M$ decomposes as a union of $m$ intertwined permutations of $\{a_1, \dots, a_n\}$. This is explained in the next lemma.

Lemma 2. Let $M$ and $X$ be as in Claim 1. Then there are pairwise distinct indices $i_{k, l} \in \{1, \dots, mn\}$ with $k \in \{1, \dots, m\}$ and $l \in \{1, \dots, n \}$ such that

  • $i_{k, l} \in [(l - 1)m + 1, lm]$ for every $k$ and every $l$,
  • $\{x_{i_{k,l}} \, \vert \, 1 \le l \le n\} = \{a_1, \dots, a_n\}$ for every $k$, i.e., the map $\sigma_k$ defined by $$\sigma_k(a_l) = x_{i_{k, l}}$$ is a permutation of the set $\{a_1, \dots, a_n\}$ for every $k$.

Proof. Apply Claim 1 and Lemma 1: the matrix $\mu = \mu(X)$ is a sum of $m$ permutation matrices. The corresponding permutations are the desired permutations $\sigma_k$. Alternatively, one may resort to Hall's marriage theorem and exhibit the sequences $(i_{k, l})$ directly through induction.


$\endgroup$
3
  • $\begingroup$ The minimal number of transpositions is in a decomposition is $n-s$ where is the number of cycle. If we apply a circular shift of $m$ element to the permutation $11...122...2...nn...n$, we easily see that no matter how we partition the permutation in $m$ sets of $n$ distinct elements, the corresponding permutation will have $m$ disjoint cycles, hence requiring $mn-m$ transpositions $\endgroup$
    – caduk
    Jan 12 at 14:11
  • $\begingroup$ @caduk Many thanks for your interest and for sharing your thoughts. A proof that $w(m, n) \ge m(n - 1)$ still eludes me. If you have a simple argument in mind, you may create your own answer. I'll be very glad to read it. $\endgroup$
    – Luc Guyot
    Jan 14 at 11:32
  • $\begingroup$ I added an answer requiring only basic reasoning on permutations $\endgroup$
    – caduk
    Jan 15 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.