7
$\begingroup$

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)$?

$\endgroup$
2
  • $\begingroup$ My guess is $\Theta(c^2)$, at least for small $c$. $\endgroup$ Mar 3, 2011 at 1:56
  • $\begingroup$ @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 :) $\endgroup$
    – Marc Bury
    Mar 3, 2011 at 2:03

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Is there an example where $\Omega(c^2)$ shifts are necessary to get the separation? $\endgroup$
    – Marc Bury
    Mar 5, 2011 at 12:06
  • $\begingroup$ 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. $\endgroup$ Mar 5, 2011 at 16:16

You must log in to answer this question.

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