Límite superior del número de intercambios locales

Question

Deje $\pi$ ser arbitraria permutación del conjunto $\lbrace 1,\ldots,n,n+1,\ldots,2n \rbrace$ algunos $n \in \mathbb{N}$. Llamamos a un intercambio local si intercambio de dos vecinos de posiciones en $\pi$, es decir, si cambia las posiciones de $i$ $i-1$ o $i$ $i+1$ algunos $i$.

Un $c$-separación de los pares de $(1,n+1),\ldots,(n,2n)$ es una partición de a $\pi$ $L := \lbrace \pi(1), \ldots, \pi(p) \rbrace$ $R := \lbrace \pi(p+1), \ldots, \pi(2n) \rbrace$ tales que por lo menos $c$ pares de $(k,k+n)$ mantener $(k,k+n) \in L \times R$ o $(k,k+n) \in R \times L$.

¿Qué es un buen límite superior en el número de los swaps que tengo que realizar en $\pi$ a obtener un $c$-separación de los pares de $(1,n+1), \ldots, (n,2n)$?

Answer 1

Fijar $p=n$. $m \in (n-c,n]$, $\pi(m)$ Ya cualquiera se separa (estos forman el conjunto de $S$), o no ya separados (estos forman el conjunto de $N$). Sea $X$ el conjunto de los «socios» de los $\pi(m)$ separadas (es decir, $S$). Así $X \subset \{\pi(n+1),\ldots,\pi(2n)\}$. Podemos utilizar $O(c^2)$ derecha cambios para que nada de $X$ se encuentra en $\pi(n+1),\ldots,\pi(n+c)$. Ahora podemos utilizar $O(c^2)$ derecha cambia de puesto para mover $N$ a través de la "rotura", sin arruinar la separación de $S$.