Take the 2-minute tour ×
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.

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|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 Gillé Mar 3 '11 at 2:03

1 Answer 1

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|improve this answer
    
Is there an example where $\Omega(c^2)$ shifts are necessary to get the separation? –  Marc Gillé 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

 
discard

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.