Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\pi$ be an arbitrary permutation of the set $\lbrace 1,\ldots,n,n+1,\ldots,2n \rbrace$ for some $n \in \mathbb{N}$. We call a swap local if you swap two neighboring positions in $\pi$, i.e. if you change the positions $i$ and $i-1$ or $i$ and $i+1$ for some $i$.

A $c$-separation of the pairs $(1,n+1),\ldots,(n,2n)$ is a partition of $\pi$ in $L := \lbrace \pi(1), \ldots, \pi(p) \rbrace$ and $R := \lbrace \pi(p+1), \ldots, \pi(2n) \rbrace$ such that for at least $c$ pairs $(k,k+n)$ hold $(k,k+n) \in L \times R$ or $(k,k+n) \in R \times L$.

What is a good upper bound on the number of local swaps I have to perform on $\pi$ to get a $c$-separation of the pairs $(1,n+1), \ldots, (n,2n)$?

share|cite|improve this question
My guess is $\Theta(c^2)$, at least for small $c$. – Yuval Filmus Mar 3 '11 at 1:56
@Yuval Filmus this is also my guess. I think the worst case is the alternate permutation $1,n+1,\ldots,n,2n$. But my guess lack a proof :) – Marc Bury Mar 3 '11 at 2:03
up vote 0 down vote accepted

Fix $p=n$. For $m \in (n-c,n]$, $\pi(m)$ is either already separated (these form the set $S$), or not already separated (these form the set $N$). Let $X$ be the set of all "partners" of those $\pi(m)$ which are separated (i.e. $S$). Thus $X \subset \{\pi(n+1),\ldots,\pi(2n)\}$. We can use $O(c^2)$ right shifts so that none of $X$ lies in $\pi(n+1),\ldots,\pi(n+c)$. Now we can use $O(c^2)$ right shifts to move $N$ across the "break", without ruining the separation of $S$.

share|cite|improve this answer
Is there an example where $\Omega(c^2)$ shifts are necessary to get the separation? – Marc Bury Mar 5 '11 at 12:06
Your example should work. However you pick $p$, you need to move $c/2$ elements, and it shouldn't be hard to show that that requires $\Omega(c^2)$ shifts. – Yuval Filmus Mar 5 '11 at 16:16

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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