Timeline for Minimum number of transpositions to make two multiset permutations equal
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 16 at 7:11 | vote | accept | Fabius Wiesner | ||
| Jan 15 at 9:00 | answer | added | caduk | timeline score: 1 | |
| Jan 4 at 1:34 | answer | added | Luc Guyot | timeline score: 4 | |
| S Jan 2 at 22:34 | history | suggested | D.W. | CC BY-SA 4.0 |
Be clear about definition of multiset permutation.
|
| Jan 2 at 22:27 | review | Suggested edits | |||
| S Jan 2 at 22:34 | |||||
| Jan 2 at 22:07 | history | edited | Fabius Wiesner | CC BY-SA 4.0 |
Canceled the duplicated post at math.stackexchange
|
| Jan 2 at 21:53 | comment | added | Luc Guyot | ... 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$). | |
| Jan 2 at 21:08 | comment | added | Luc Guyot | 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$). | |
| Jan 2 at 17:53 | history | edited | Fabius Wiesner | CC BY-SA 4.0 |
added 92 characters in body
|
| Dec 19, 2023 at 17:54 | history | asked | Fabius Wiesner | CC BY-SA 4.0 |