\documentclass[12pt]{article} \usepackage{e-jc} \specs{}{}{} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb, enumerate} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \newcommand{\cP}{\mathcal{P}} \newcommand{\N}{\mathbb{N}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\R}{\mathbb{R}} \newcommand{\X}{\mathbb{X}} \newcommand{\Y}{\mathbb{Y}} \newcommand{\U}{\mathbb{U}} \newcommand{\W}{\mathbb{W}} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Extremal permutations in routing cycles} \author{Junhua He\thanks{Research support in part by the fundamental research funds for Chinese universities under Grant ZYGX2012J120.}\\ \small School of Mathematical Sciences\\[-0.8ex] \small University of Electronic Science and Technology of China\\[-0.8ex] \small Chengdu, Sichuan, 611731, China.\\ \and Louis A. Valentin\\ \small Department of Mathematics\\[-0.8ex] \small College of William and Mary\\[-0.8ex] \small Williamsburg, VA 23185\\ \and Xiaoyan Yin\thanks{Research supported in part by National Science Foundation of China (61373174) and the Fundamental Research Funds for the Central Universities (K5051370007).}\\ \small \phantom{makewide}School of Mathematics and Statistics\phantom{makewide}\\[-0.8ex] \small Xidian University\\[-0.8ex] \small Xi'an, Shaanxi, 710071, China.\\ \and Gexin Yu\thanks{The research is supported in part by the NSA grant H98230-16-1-0316}\\ \small Department of Mathematics\\[-0.8ex] \small College of William and Mary\\[-0.8ex] \small Williamsburg, VA 23185\\ \small\tt gyu@wm.edu } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Jul 19, 2015}{Aug 30, 2016}{}\\ \small Mathematics Subject Classifications: 05A05, 05C35, 05E15} \begin{document} \maketitle \begin{abstract} Let $G$ be a graph whose vertices are labeled $1,\ldots,n$, and $\pi$ be a permutation on $[n]:=\{1,2,\cdots, n\}$. A pebble $p_i$ that is initially placed at the vertex $i$ has destination $\pi(i)$ for each $i\in [n]$. At each step, we choose a matching and swap the two pebbles on each of the edges. Let $rt(G, \pi)$, the routing number for $\pi$, be the minimum number of steps necessary for the pebbles to reach their destinations. Li, Lu, and Yang proved that $rt(C_n, \pi)\le n-1$ for every permutation $\pi$ on the $n$-cycle $C_n$ and conjectured that for $n\geq 5$, if $rt(C_n, \pi) = n-1$, then $\pi = 23\cdots n1$ or its inverse. By a computer search, they showed that the conjecture holds for $n<8$. We prove in this paper that the conjecture holds for all even $n\ge 6$. \bigskip\noindent \textbf{Keywords:} Routing number, permutation, sorting algorithm, Cayley graphs \end{abstract} \section{Introduction} Routing problems occur in many areas of computer science. Sorting a list involves routing each element to the proper location. Communication across a network involves routing messages through appropriate intermediaries. Message passing between multiprocessors requires the routing of signals to correct processors. In each case, one would like the routing to be done as quickly as possible. Let us consider the routing model introduced by Alon, Chung, and Graham \cite{ACG94} in 1994. Let $G = (V,E)$ be a graph whose vertices are labeled as $1, \ldots, n$. For a permutation $\pi$ on $[n]$, a pebble $p_i$, which has destination $\pi(i)$, is placed at $i$ for each $i\in [n]$. For example, let $\pi=342165=\begin{pmatrix}1&2&3&4&5&6\\3&4&2&1&6&5\end{pmatrix}$, then the destination of $(p_1, p_2, p_3, p_4, p_5, p_6)$ are $(3,4,2,1,6,5)$. We wish to move pebbles to their destinations. To do so, at each round we select a matching of $G$ and swap the pebbles at the endpoints of each edge, and repeat rounds until all pebbles are in place. Let $rt(G, \pi)$ denote the minimum number of rounds necessary to route $\pi$ on $G$. Then, the {\bf routing number} of $G$ is defined as: \[ rt(G) = \max_{\pi}\ \{ rt(G, \pi) \}. \] Note that when each matching in the routing process consists of one edge, the routing number corresponds to the diameter of Cayley graph generated by (cyclically) adjacent transpositions. The diameter problem of Cayley graphs has a rich research literature, and we refer the reader to the book~\cite{FLRTV09} for a comprehensive survey. %As the routing problem occurs in many contexts in computer science, some of the first bounds are consequences of computer science algorithms. %The odd-even transposition sort \cite{K98} and Benes network \cite{B65} show $rt(P_n) = n$ and $rt(Q_n) \le 2n- 1$, for $n$-vertex path $P_n$ and $n$-dimensional hypercube $Q_n$, respectively. Very few results are known for the exact values of the routing numbers of graphs. \begin{theorem}[Alon, Chung, and Graham~\cite{ACG94}] The following are true: \begin{enumerate} \item $rt(P_n)=n$, $rt(K_n) = 2$ and $rt(K_{n,n}) = 4$; \item $rt(G) \ge diam(G)$ and $rt(G) \ge \frac{2}{|C|} \min \{|A|,|B|\}$, where $diam(G)$ is the diameter of $G$ and $C$ is a set that cuts $G$ into parts $A$ and $B$; \item $rt(G) \le rt(H)$ and $rt(T_n) < 3n$, where $H$ is a spanning subgraph of $G$ and $T_n$ is a tree on $n$ vertices; \item $rt(G_1 \times G_2) \le 2rt(G_1)+rt(G_2)$, and $n \le rt(Q_n) \le 2n-1$. \end{enumerate} \end{theorem} Zhang~\cite{Zheng99} improved the above bound on trees, showing that $rt(T_n) \le \left \lfloor \frac{3n}{2} \right \rfloor + O(\log n)$. Li, Lu, and Yang~\cite{LLY10} showed that $n+1 \le rt(Q_n) \le 2n-2$, improving both the previous upper and lower bounds on hypercubes. Among other results, they showed that $rt(C_n)= n-1$, and made the following conjecture. \begin{conjecture}[Li, Lu, Yang~\cite{LLY10}] \label{conj} For $n \ge 5$, if $rt(C_n, \pi) = n-1$, then $\pi$ is the rotation $23\cdots n1$ or its inverse $n12\cdots (n-1)$. \end{conjecture} The conjecture does not hold for $n=4$; the permutation that transposes two non-adjacent vertices and fixes the other two serves as a counterexample. They verified the conjecture for $n<8$ through a computer search. The conjecture is kind of counter-intuitive: the permutations on the cycle requiring most time to route are the ones that each pebble is very close to (actually at distance one from) its destination. In this article, we give a proof of the conjecture when $n$ is even. \begin{theorem} \label{thework} For even $n \ge 6$, if $rt(C_n, \pi) = n-1$, then $\pi$ is the rotation $23\cdots n1$ or its inverse. \end{theorem} %this is a new paragraph Some new tools are introduced in the proof, beyond the ideas from \cite{ALSY11} by Albert, Li, Strang, and the last author. These tools, introduced in Section~\ref{tools}, enable us to describe precisely the swapping process of each pebble, and determine the pebbles that need $n-1$ steps to route, see Section~\ref{extreme} for detail. In Section~\ref{solution}, we show that the only permutations that need $n-1$ steps to route must be the two permutations in the theorem. \section{Important notion and tools}\label{tools} Let $G = C_n$ with even $n\ge 6$ and label the vertices of $C_n$ as $1,2,\dots,n$ in the clockwise order. Let the clockwise direction be the positive direction and counter clockwise be the negative direction. In the rest of the paper, when list pebbles or sets of pebbles in a row, we always think them to be in the clockwise order on the cycle. \subsection{The Odd-Even Routing Algorithm} %The result on the routing number of $P_n$ were shown using what is known as the {\bf odd-even routing algorithm}. An {\em odd-even sort} or {\em odd-even transposition sort} is a classic sorting algorithm (see \cite{K98}) used to sort a list of numbers on parallel processors. To describe this algorithm, we may place the $n$ numbers to be sorted on the vertices of the path $P_n=v_1v_2\ldots v_n$. An edge $e = v_iv_{i+1}$ is odd if and only if $i$ is odd. At each odd step (respectively, even step) of the routing process, we select a matching consisting of odd edges (respectively, even edges) whose two numbers have the wrong order and swap the numbers on the endpoints. We apply a similar algorithm on even cycles, whose edges can be partitioned into two perfect matchings. We shall call edges in one perfect matching to be even and the others to be odd. Thus, once the parity of one edge is specified, the parity of all the edges is determined. During the odd steps (respectively, even steps) we choose a matching consisting of odd edges (respectively, even edges) whose two pebbles are comparable (defined in subsequent subsections). If an edge $e$ is chosen to be an odd edge, we would call this algorithm the {\em odd-even routing algorithm with odd edge $e$}. %Note that this algorithm is not defined on cycles of odd length since the edges that would be labeled as odd edges do not form a matching. \subsection{Spins and Disbursements} %%% spin There are exactly two paths for pebble $p_i$ to reach its destination, by traveling either in the positive or negative direction. Let $d^+(i, j)$ denote the distance from the vertex $i$ to the vertex $j$ along the positive direction. Then if $ij$. For simplicity, for pebbles $p_i$ and $p_j$, we define $d^+(p_i,p_j)=d^+(i, j)$, and if $p_i$ and $p_j$ are on the endpoints of an edge, we sometimes call the edge $p_ip_j$. %% disbursement Consider a routing process of a permutation $\pi$ on $C_n$ with pebble set $P=\{p_1, \ldots, p_n\}$. For each pebble $p_i$, let $s(p_i)$, the {\em spin} of $p_i$, represent the displacement for $p_i$ to reach its destination from its current position. So, $s(p_i) \in \{ d^+(i, \pi(i)), d^+(i, \pi(i))-n \}$. Note that the spin of a pebble changes with its movement. A sequence $B =(s(p_1), s(p_2), \ldots, s(p_n))$ is called a {\em valid disbursement} of $\pi$ if the spins can be realized by a routing process on $\pi$. Not all combinations of spins give valid disbursements. The following lemma gives a necessary and sufficient condition for a set of spins to be a valid disbursement. \begin{lemma} Let $B=(s(p_1), s(p_2), \ldots, s(p_n))$ be an assignment of the spins to the pebbles. It is a valid disbursement if and only if $\sum_{i=1}^n s(p_i)= 0$. \end{lemma} \begin{proof} To see the necessity, we observe that when two pebbles are swapped, one moves forward one step and one moves backward one step, so the sum of spins remains invariant. Since $B$ is a valid disbursement, the final spins are all zeroes, so the sum is also zero. For sufficiency, we can move the pebbles one by one along their assigned directions. \end{proof} From this lemma, a valid disbursement of a non-identity permutation $\pi$ must contain both positive and negative spins. Let $s(p_i)>0$ and $s(p_j)<0$ in a valid disbursement $B$ of $\pi$. By {\em flipping the spins of $p_i$ and $p_j$}, we change the spins of $p_i$ and $p_j$ to $s(p_i)-n$ and $s(p_j)+n$, respectively. Clearly, after one flip, we obtain a new valid disbursement. A valid disbursement $(s(p_1), \ldots, s(p_n))$ is minimized if $\sum_{p\in P} |s(p)|$ is minimized. The following simple fact is very important. \begin{lemma} If a valid disbursement is minimized, then $s(p_i)-s(p_j)\le n$ for all $i,j\in [n]$. \end{lemma} \begin{proof} For otherwise, one can make the sum smaller by flipping the spins of $p_i$ and $p_j$. \end{proof} %It is not hard to see that the converse is also true, so one can apply the flips on a valid disbursement to get a minimized disbursement. \iffalse The following lemma give a characterization of minimized disbursement of a permutation. \begin{lemma}\label{mini-disbursement} Let $B=(b_1,\cdots, b_n)$ be a valid disbursement of a permutation $\pi$, the following conditions are equivalent:\\ (1) $B$ is a minimized disbursement of $\pi$; \\ (2) ${\rm max}(b_1,\cdots, b_n)-{\rm min}(b_1,\cdots, b_n)\le n$. \end{lemma} \fi %Given $C_n$ and a particular valid $B$, the sum of the absolute values of the spins in $B$ is the number of rounds to route $C_n$ using $B$. %We also have as a lower bound $\frac{ |B| }{ 2\lfloor \frac{n}{2} \rfloor }$, since the denominator represents the maximum total distance change during one step using a maximum matching. Because of these bounds, we want to minimize $|B|$. \subsection{An order relation} Once a valid disbursement $B=(s(p_1), s(p_2), \ldots, s(p_n))$ of $\pi$ is given, some restrictions are placed on the routing processes realizing $B$. For example, if $s(p_i)-s(p_j)>d^+(p_i,p_j)$, then $p_i$ and $p_j$ must swap at some round in the routing processes. In other words, each valid disbursement is associated with an order relation on the pebbles. \begin{definition} Let $B=(s(p_1), s(p_2), \ldots, s(p_n))$ be a valid disbursement. We call $p_i\succ p_j$ if $s(p_i)-s(p_j) > d^+(p_i, p_j) $ \end{definition} %Remark: even though the order is associated with a disbursement, but we will usually omit it in the routing process, as the spins changes and the order is always associated with the new disbursements. Note that the order relation is transitive. To see that, let $p_i\succ p_j$ and $p_j\succ p_k$. Then $s(p_i) - s(p_j)>d^+( p_i, p_j)$ and $s(p_j) - s(p_k)>d^+(p_j, p_k)$. It follows that $s(p_i)-s(p_k)>d^+(p_i, p_j)+d^+(p_j, p_k)\ge d^+(p_i, p_k)$, which implies $p_i\succ p_k$. As two pebbles have different destinations, $s(p_i)-s(p_j)\not=d^+(p_i, p_j)$, so if $p_i\succ p_j$ is not true, then $s(p_i)-s(p_j)n$, a contradiction. Likewise, if $x\succ z$ and $y\succ x$, then $s(x)-s(z)\ge d^+(x,z)$ and $s(y)-s(x)\ge d^+(y,x)$, and it follows that $s(y)-s(z)\ge d^+(x,z)+d^+(y,x)>n$, a contradiction. \end{proof} The following lemma says that we only need to swap comparable pebbles to route the permutation. \begin{lemma}\label{incomparable} Let $B$ be a minimized disbursement of $\pi$. If a pebble $p$ is incomparable with all other pebbles, then $s(p)=0$, i.e., the pebble $p$ is at its destination vertex. \end{lemma} \begin{proof} Suppose that $s(p)\neq 0$. By symmetry, let $s(p)>0$. Let $\pi=\Pi_i \pi_i$ be a cycle decomposition of $\pi$, where $\pi_i=(i_1,\cdots,i_{r_i})$. Then the pebble placed at $i_{k}$, which we call pebble $i_k$ to save symbols, has destination $i_{k+1}$ for all $k\le r_i$, with $i_{r_i+1}=i_1$. Let $P_i$ be the set of pebbles on $\pi_i$. We say that $\pi_i$ is the orbit of the pebbles in $P_i$. We may assume that $p=i_1$. We claim that for each $j$, $\sum_{q\in P_j}s(q)=an$ for some integer $a$. To see this, we note that $s(j_k)\in \{d^+(j_k, j_{k+1}), d^+(j_k, j_{k+1})-n\}$. Thus, if the spins are all positive, the sum equals $bn$ for some positive integer $b$. However, each switch of a spin from positive to negative would cause a change of $-n$ in the sum. So the sum of spins remains a multiple of $n$. %We also claim that for orbit $P_i$ on which where $p$ is, $\sum_{q\in P_i}s(q)=n$. For convenience, let $p_j$ be on $v_{i_j}$. We just need to show that all pebbles on $\pi_i$ has positive spins. For otherwise, if $s(p_k)<0$, then $s(p_k)=d^+(v_{i_k}, v_{i_{k+1}})-n$, so $s(p_1)-s(p_k)=n+d^+(v_{i_1}, v_{i_{2}})-d^+(v_{i_k}, v_{i_{k+1}})>d^+(p_1, p_k)$, and thus $p_1\succ p_k$, a contradiction. We further claim that all pebbles in $P_i$ have positive spins, which also implies that $\sum_{q\in P_i} s(q)=bn$ for some positive integer $b$. Note that $s(i_1)=s(p)>0$. Let $j$ be the smallest integer so that $s(i_j)<0$. Then $s(i_j)=d^+(i_j, i_{j+1})-n\le -d^+(i_1,i_j)$. So $s(i_1)>0\ge s(i_j)+d^+(i_1,i_j)$. It follows that $s(i_1)-s(i_j)>d^+(i_1,i_j)$, that is, $p=i_1\succ i_j$, a contradiction. %We also claim that no pebble in $P_i$ will pass $i_2$ in the negative direction in order to arrive its destination. Otherwise, assume that $i_k (20>s(i_k)+d^+(i_1, i_k)$. It follows that $p=i_1\succ i_k$, a contradiction. %Furthermore, we have $s(i_2)>0$. Otherwise, let $s(i_2)\le 0$. As the destination of pebble $i_2$ is $i_3$, we have $s(i_2)=d^+(i_2, i_3)-n<-d^+(i_1, i_2)$. Hence $s(i_1)>0>s(i_2)+d^+(i_1, i_2)$. It follows that $p=i_1\succ i_2$, a contradiction. %The fact that $s(i_1)>0$ implies that $i_1$ will travel in the positive direction, and the fact that $s(i_2)>0$ implies that $i_2$ will arrive its destination $i_3$ in the positive direction, since there exists no pebble will pass $i_2$ in the negative direction. Therefore, $\sum_{q\in P_1}s(q)=bn$ for some positive integer $b$. As the sum of all spins is zero, there exists some orbit $\pi_j$ with spin sum $cn$ for some integer $c<0$. In particular, there exists a pebble $q\in P_j$ such that $q$ passes $p=i_1$ in the negative direction to arrive its destination. So $s(q)+d^+(p, q)<0 n$. Their spins can be flipped to decrease the absolute sum of $B$. (b) Suppose $p_i\succ p_j$ and $p_j\succ p_k$. Then, by definition, we have $s(p_i) - s(p_j)>d^+( p_i, p_j)$ and $s(p_j) - s(p_k)>d^+(p_j, p_k)$. It follows that $s(p_i)-s(p_k)>d^+(p_i, p_j)+d^+(p_j, p_k)\ge d^+(p_i, p_k)$, so $p_i\succ p_k$. % Now, either $s(p_k)-s(p_i) = d^+( p_i, p_j) + d^+( p_j, p_k) = d^+( p_i, p_k)$ or $s(p_k)-s(p_i) =n + d^+( p_i, p_k)$. Suppose $s(p_k)-s(p_i) > n$. Then, $s(p_k) > 0$ and $ s(p_i) < 0$, since $ -n < s(p_a) < n$ for all $a$. Flipping the spins of $p_i$ and $p_j$ gives a smaller sum of absolute values of spins, a contradiction. Therefore, $s(p_k) - s(p_i) = d^+( p_i, p_k) \Leftrightarrow p_i \prec p_k$. Thus, the order is transitive. \end{proof} \fi %The above lemma implies that a permutation is the identify if there is no order relation among the pebbles. Note that the order of pebbles is always associated with the current disbursement, which may not be the same as the initial disbursement. The following lemma says that whether or not two pebbles swap is determined by the initial disbursement. So we will not keep tracking of the spins, but just see whether necessary swaps are performed. \begin{lemma} If $p_i$ and $p_j$ are incomparable, then in the sorting process, they will always be incomparable. If $p_i\succ p_j$, then $p_i$ and $p_j$ are incomparable after the swap of $p_i$ and $p_j$. \end{lemma} \begin{proof} If $p_i$ and $p_j$ are incomparable, then in the sorting process, $(s(p_i)-s(p_j))-d^+(p_i,p_j)$ does not change: if a pebble swaps with both $p_i$ and $p_j$, then it must be bigger than or smaller than both $p_i$ and $p_j$, thus the distance from $p_i$ to $p_j$ does not change and $s(p_i)-s(p_j)$ does not change; If a pebble swaps only with $p_i$, then $s(p_i)$ increases by one and $d^+(p_i,p_j)$ increases by one; If a pebble swaps only with $p_j$, then $s(p_j)$ increases by one and $d^+(p_i,p_j)$ decreases by one. Now let $p_i\succ p_j$. We only need to show that they become incomparable right after the swap of $p_i$ and $p_j$, by what we just proved. Since $p_i\succ p_j$, $n\ge s(p_i)-s(p_j)\ge d^+(p_i,p_j)+1\ge 2$. Let $s'(p_i)$ and $s'(p_j)$ respectively be the new spins of $p_i$ and $p_j$ right after the swap of $p_i$ and $p_j$. Note that $p_i$ and $p_j$ are adjacent to each other only if the pebbles on the segment from $p_i$ to $p_j$ along the positive direction have swapped with $p_i$ (for those smaller than $p_i$) or $p_j$ (for those bigger than $p_j$). Then $s'(p_i)-s'(p_j)=s(p_i)-s(p_j)-d^+(p_i,p_j)-2$. Therefore, $s'(p_j)-s'(p_i)<0$, and $p_j$ cannot be bigger than $p_i$. Also, $s'(p_i)-s'(p_j)\le n-2d^+(p_j,p_i).$ For pebbles not in $\{p_i,p_j\}$, the spins and distance do not change from $B$ to $B'$, so their order relation does not change as well. (2) For $k\notin\{i,j\}$, we know that $$s(p_k)-s'(p_i)-d^+(p_k, p_i)=s(p_k)-(s(p_i)-n)-(n-d^+(p_i,p_k))=s(p_k)-s(p_i)+d^+(p_i,p_k).$$ Therefore, $s(p_k)-s'(p_i)>d^+(p_k, p_i)$ if and only if $s(p_i)s(p_i)-s(p_j)=n$. It follows that $p_k\succ p_i$ under $B'$ if and only if $p_k$ and $p_i$ are incomparable under $B$. By flipping the spins of $p_i$ and $p_j$ in $B'$, we get $B$. So we have the other part as well. (3) Since $s'(p_j)-s'(p_i)=n$ under $B'$, and one gets $B$ after flipping the spins of $p_i$ and $p_j$ in $B'$, these two statements follow from (2). \end{proof} \subsection{The window of a pebble} Let $B$ be a minimized disbursement of $\pi$ with associated order $\succ$. For an arbitrary pebble $p_0$, let $$U=\{p\in P: p\succ p_0\}\;\;{\rm and}\;\;W=\{p\in P: p_0\succ p\}.$$ By Lemma~\ref{incomparable}, the routing process ends when no pebble has a bigger or smaller pebble. So we have the following equation, which is heavily used to determine the spins of the pebbles in our later proofs. \begin{equation}\label{spin} s(p_0)=|W|-|U|. \end{equation} By Lemma~\ref{induced-order}, there are no $u\in U, w\in W$ such that $u, w, p_0$ or $p_0, u, w$ on $C_n$. %For otherwise, $d^+(p_0, w)+d^+(u,p_0)>n$, thus we have $s(u)>s(p_0)+d^+(u,p_0)>s(w)+d^+(p_0,w)+d^+(u,p_0)>s(w)+n$, a contradiction. So if $U=\{u_1, u_2, \ldots, u_r\}$ and $W=\{w_1, w_2, \ldots, w_t\}$, then we may assume that the pebbles in $U\cup W$ and $p_0$ are ordered as $u_r, \ldots, u_1, p_0, w_1, \ldots, w_t$ on $C_n$. We denote the set of pebbles incomparable to $p_0$ between $p_0$ and $w_t$ (between $u_r$ and $p_0$ resp.) by $X$ ($Y$ resp.). A {\em segment} is a sequence of consecutive pebbles. An $U$-segment is a segment whose pebbles are all in $U$, and likewise, we have $W$-segments, $X$-segments and $Y$-segments. So we can group the pebbles between $u_r$ and $w_t$ along the positive direction as $$win(p_0)=(U_k, Y_k, U_{k-1}, \ldots, U_1, Y_1, p_0, X_1, W_1, \ldots, X_l, W_l),$$ where $X_1, Y_1$ may be empty, and $win(p_0)$ is called the {\em initial window} of $p_0$. So in the window $win(p_0)$ of the pebble $p_0$, from the leftmost (the $U$-segment) to $p_0$, the segments are alternatively $U$- and $Y$-segments, and from the rightmost (the $W$-segment) to $p_0$, the segments are alternatively $W$- and $X$-segments. We shall use this notation without further notice. We denote the set of all other pebbles as $Z$. So sometimes we write $\pi$ as $$\pi=(Z, U_k, Y_k, U_{k-1}, \ldots, U_1, Y_1, p_0, X_1, W_1, \ldots, X_l, W_l).$$ %It is clear that $|win(p_0)|=|U|+|Y|+|W|+|X|+1\le n$ and $p_0$ is in place if and only if $|win(p_0)|=1$. % If $|win(p)|=1$ for all $p\in P$, it implies that each pebble has reached its own destination and thus the routing process is finished. By transitivity, we have $u_i\succ w_j$ since $u_i\succ p_0\succ w_j$ for all $1\le i\le r$ and $1\le j\le t$, and in particular, $u_r\succ w_t$, hence $n\ge s(u_r)-s(w_t)>d^+(u_r, w_t)$. By Lemma~\ref{induced-order}, $\text{if $i\ge j$, then $u\succ y$ for all $u\in U_i,\;y\in Y_j$; If $k\ge l$, then $w\prec x$ for all $w\in W_k,\;x\in X_l$. }$ \bigskip \iffalse \begin{lemma}\label{propWin} Let $win(p_0)=(U_r Y_r U_{r-1}Y_{r-1}\cdots U_1 Y_1 p_0 X_1 W_1\cdots X_t W_t)$. Then \begin{enumerate} \item If $i\ge j$, then $u\succ y$ for all $u\in U_i,\;y\in Y_j$; \item If $k\ge l$, then $w\prec x$ for all $w\in W_k,\;x\in X_l$; % \item If $r>0$ and $t>0$, then $|win(p_0)|\le n-1$. \end{enumerate} \end{lemma} \begin{proof} Let $i>j$ and $u\in U_i, y\in Y_j$. Then $y$ is between $u$ and $p_0$ along the positive direction, and we have $d^+(u,p_0)=d^+(u, y)+d^+(y,p_0)$. The incomparability of $y$ and $p_0$ implies that $s(y)\le s(p_0)+d^+(y, p_0)$, and $u\succ p_0$ implies $s(u)>s(p_0)+d^+(u, p_0)$, hence we have $s(u)>s(p_0)+d^+(u,p_0)=s(p_0)+d^+(u,y)+d^+(y,p_0)\geq s(y)+d^+(u,y)$, and it follows that $u\succ y$. Similarly for $W$ and $X$. \end{proof} \fi %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Rotation Lemma %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\section{Consecutive moves and rotation permutations}\label{rotation} %\red{I would delete the following lemma, as it is not quite right. Instead I would add one paragraph in the proof of the lemma following it} %\begin{lemma}\label{consecutive} %Let $Q_1$ be a segment of pebbles. Let $Q_2$ be a set of pebbles such that $Q_1\succ Q_2$ (or $Q_2\succ Q_1$). Suppose at some moment during the routing process, pebbles in $Q_1$ are ordered clockwise as $p_1, p_2, \ldots, p_k$, then at most one pebble from $Q_2$ is between $p_i$ and $p_{i+1}$ for $1\le i\le k-1$. %\end{lemma} %\begin{proof} %Let step $s$ be the first step so that for some pebbles $p, p'\in Q_1$ and $q,q'\in Q_2$, they are ordered consecutively as $p, q, q', p'$. Since this is the first step, $pq$ and $q'p'$ were edges to be swapped in the previous step. But the edge $pq$ would have swapped $p$ and $q$, and give $q, p, q',p'$ in step $s$, a contradiction. %\end{proof} \subsection{Two important lemmas} A nice property of the odd-even routing algorithm is the following %%%%%%%%% the following was the old Lemma 8 (now Lemma 7) \begin{lemma}\label{consecutive-swaps} Let $p$ be a pebble and $Q$ be a segment of pebbles. If $p\succ Q$ or $Q\succ p$, then once $p$ starts to swap with a pebble in $Q$ in an odd-even routing algorithm, $p$ will not stop swapping until $p$ swaps with all pebbles in $Q$ (in the following $|Q|-1$ or more steps). % In particular, once $p_0$ begins to swap with a pebble in $U_i$ (or $W_j$), $p_0$ will swap with $U$-elements (or $W$-elements) in the next $|U_i|-1$ steps (or $|W_j|-1$ steps). \end{lemma} \begin{proof} By symmetry, we let $p\succ Q$. An {\em enlargement of $Q$} is a segment obtained from $Q$ by mixing some pebbles that are smaller than $p$. So $p\succ Q'$ if $Q'$ is an enlargement of $Q$. We first claim that if $x,y\succ Q$, then after swapping with some pebbles in $Q$, $x$ and $y$ can never be on an edge unless they have swapped with all pebbles in $Q$. Suppose that the first time such an edge occurs at step $s$. That is, after step $s-1$, we have $q, x, y, q'$, where $x,y\succ \{q,q'\}$. Now, at step $s-1$, $xq$ and $yq'$ are among the chosen edges. So, after step $s-1$, we should have $q, x, q',y$, a contradiction. Note that for a pebble $q$ between $p$ and $Q$ along the positive direction, by Lemma~\ref{induced-order}, either $p\succ q$ or $q\succ Q$; in the former case, $q$ either becomes a pebble in an enlargement of $Q$ or $p,q$ swap before $p$ meets a pebble in $Q$. So we may assume that all pebbles from $p$ to $Q$ along the positive direction are bigger than $Q$. Now by the claim, $p$ never meets a pebble incomparable with $p$ before it finishes swapping with $Q$. So $p$ moves continuously. \end{proof} %By symmetry, we let $p\succ Q$. If the pebbles in $Q$ that have yet to swap with $p$ remain to be a segment (possibly in a different order) in the routing process, then $p$ would swap with $Q$ consecutively, as $p$ is paired with a new pebble from $Q$ in each of the following steps. Also note that if some pebble smaller than a pebble in $Q$ is between pebbles in $Q$, this pebble is also smaller than $p$ by transitivity thus will not delay the movement of $p$. We should call it {\em an enlargement of $Q$} if a smaller pebble (than $p$) is mixed with $Q$. If $Q'$ is an enlargement of $Q$, then $p\succ Q'$ and $Q'$ is a segment. % Note that we shall similarly consider the enlargement of the yet-to-swap-with-$p$ pebbles in $Q$ if necessary. %Consider the initial window $win(p)$ of $p$ and let the segments between $p$ and $Q$ be $$p, X_1, W_1, \ldots, X_k, W_k=Q,$$ where pebbles in $W_i$ with $i\le k$ are all smaller than $p$, and pebbles in $X_i$ with $i\le k$ are incomparable with $p$ (thus by Lemma~\ref{induced-order}, are bigger than pebbles in $Q$). %We claim that at most one pebble from $X=\cup_{i=1}^k X_i$ is between any consecutive pair of pebbles in an enlargement of $Q$ (note that after a pebble $u\succ p$ swapped with $p$, $u$ is incomparable with $p$ thus considered to be in $X$). For otherwise, let step $s$ be the first step so that some pebbles $x, x'\in X$ and $q,q'$ in an enlargement of $Q$ are ordered consecutively as $q, x, x', q'$. Since this is the first step of enlargement, $qx$ and $x'q'$ were edges to be swapped in the previous step. But the edge $qx$ would have swapped $q$ and $x$, and give $x, q, x',q'$ in step $s$, a contradiction. %Assume that $p$ starts to swaps with a pebble in $Q$ in step $s$, but does not swap with a pebble before finishing swapping with $Q$. Let step $t$ be the first step that $p$ does not swap in the process (before finish swapping with $Q$). Then before the step $t-1$, the pebbles following $p$ are $z_1, z_2, z_3, z_4$ with $p\succ z_1$. By the above claim, at most one of $z_2$ and $z_3$ is from $X$, so at least one of them is smaller than $p$. At step $t-1$, $pz_1, z_2z_3$ are the edges to swap; if $z_2\in X$ then $z_3\not\in X$ thus $p\succ z_3$, therefore after the swap we have $z_1, p, z_3, z_2$ and $pz_3$ swap at step $t$; and if $z_2\not\in X$, then $p\succ z_2$, and after the swap, we have either $z_1, p, z_3, z_2$ or $z_1, p, z_2, z_3$; the former case occurs if $z_2\succ z_3$ thus $p\succ z_3$ so $p, z_3$ swap in step $t$, and in the latter case $p, z_2$ swap in step $t$. \begin{lemma}[Rotation Lemma] \label{rot} Let $q$ be an integer with $ -\frac{n}{2} < q \le \frac{n}{2}$, and $\pi$ be the permutation that satisfies $\pi(a) = a + q \pmod{n}$ for each $a\in [n]$. Then, $rt(C_n, \pi) = n - |q|$. \end{lemma} \begin{proof} By symmetry we only consider the case when $q>0$. For each pebble $p$, the spin of $p$ is either $q$ or $q-n$. Since the sum of spins is zero, there must be exactly $n-q$ pebbles with the positive spin and $q$ pebbles with the negative spin. So, $n-q \le rt(C_n, \pi)$. Now, we show that $rt(C_n, \pi) \le n-q$. Let the pebbles be $p_1, p_2, \ldots, p_n$ on $C_n$. We assign spins to the pebbles so that $s(p_{2i-1})=q-n$ for $1\le i\le q$ and each of the remaining $n-q$ pebbles has the spin $q$. We use an odd-even routing algorithm with odd edge $p_1p_2$. As $q\le n/2$, no two pebbles with spin $q-n$ are adjacent. In the routing process, $p_1$ will be paired with $p_2, p_4, \ldots, p_{2q}, p_{2q+1}, \ldots, p_n$ in the first $n-q$ steps, thus reach its destination, and similar things occur for all other pebbles with negative spins. When all pebbles with negative spins reach their destinations, there is no comparable pebbles, so each pebble will be in place. Thus, $\pi$ is routed in $n-q$ steps. \end{proof} %We will consider segments which can be partitioned into blocks. %\red{I really like to unify Lemmas~\ref{block-2}, ~\ref{block-2a} and ~\ref{block-3} here. I don't know a good way to do that yet. } \section{Extremal Windows}\label{extreme} Now we count the steps needed for an arbitrary pebble, say $p_0$, to swap with all comparable pebbles. Let the initial window of $p_0$ be $$win(p_0)=(U_k, Y_k, U_{k-1}, \ldots, U_1, Y_1, p_0, X_1, W_1, \ldots, X_l, W_l).$$ As we only consider how $p_0$ swaps with other pebbles, we ignore the swaps between pebbles inside each of the segments, and regard them to be incomprable for now. % For this purpose, we may regard $p_0$ and pebbles in $X, Y, Z$ ($Z$ is the set of the pebble outside of $win(p_0)$) as ones, pebbles in $U$ as twos, and pebbles in $W$ as zeros, and a pebble is bigger than another if and only the corresponding number is larger. The goal is to swap $p_0$ with all twos and zeros. %Now let us consider the routing process for an (arbitrary) pebble, say $p_0$. As defined, let $U_1, U_2, \ldots, U_k$ and $W_1, W_2, \ldots, W_l$ be the segments comparable with $p_0$. In the routing process, those segments may be mixed and $p_0$ may not swap with them in their initial order. However, by Lemma~\ref{consecutive-swaps}, if $p_0$ starts to swap with a pebble in one segment $Q$, then $p_0$ will swap with pebbles in the following $|Q|$ steps (not necessary with elements in $Q$ though). However, if $p_0$ starts to swap with $W_i$, and in the following $|W_i|$ steps, $p_0$ will swap with pebbles that are smaller than $p_0$, thus must be in $W$ as well; we would denote those pebbles $W_i'$. So we know $|W_i'|=|W_i|$ and they both contain pebbles smaller than $p_0$. Similarly we define $U_i'$ for $1\le i\le k$. Note that $U'$ and $W'$ are not necessarily segments any more. So $p_0$ will meet $U$-sequences in the order of $U_1', U_2', \ldots, U_k'$, and $W$-sequences in the order of $W_1', W_2', \ldots, W_l'$, but may meet those sequences in a mixed order. Let $Z_1, Z_2, \ldots, Z_{k+l}$ be the order the sequences meet $p_0$, so $Z_i\in \{U_1', \ldots, U_k', W_1', \ldots, W_l'\}$. By Lemma~\ref{consecutive-swaps}, when we apply the odd-even routing algorithm, $p_0$ will meet a segment $S\in \{U_1, \ldots, U_k, W_1, \ldots, W_l\}$ and swap with all the pebbles in $S$ in the following $|S|$ steps. Assume that $p_0$ meets the segments in the order $S_1, S_2, \ldots, S_{k+l}$, where $S_i\in \{U_1, \ldots, U_k, W_1, \ldots, W_l\}$. For $i=1, 2,\dots,k+l-1$, let $\omega_i$ be the waiting time between $S_{i-1}$ and $S_i$, that is, the number of steps that $p_0$ waits between swapping with the last pebble of $S_{i-1}$ and swapping with the first pebble of $S_i$. Let $\alpha$ be the largest index such that $\omega_\alpha\neq 0$. %First, we assume that $Z_\alpha$ is the $t$-th $W$-sequence. By symmetry, we assume that $S_{\alpha}=W_t$. Because of the parity, a swap of $p_0$ and $W$ (or $p_0$ and $U$) cannot be followed by a swap of $p_0$ and $U$ (or $p_0$ and $W$). Therefore, as $\omega_{\alpha+1}=\cdots=\omega_{k+l}=0$, $\cup_{i\ge \alpha}S_i=\cup_{i=t}^l W_i$ and $p_0$ will swap with them continuously until it reaches its destination. Let $w$ be the pebble in $W_t$ next to $X_t$. Since we ignore the swaps between pebbles in $W$, $w$ only moves in one direction (counter-clockwise). Then the steps for $p_0$ to be in place are the steps for $p_0$ and $w$ to meet plus $|\cup_{i=t}^l W_i|$. To meet $p_0$, $w$ has to swap with pebbles in $\cup_{j=1}^t X_j$ and $\cup_{i=1}^k U_i$. We also note that, $w$ is always paired with a comparable pebble starting from the first or the second step, depending on the parity of the first edge with which $w$ is incident. Thus the total number of steps for $p_0$ to be in place is: \begin{equation}\label{eq01} \sum_{j=1}^{t}|X_j|+\sum_{j=t}^{l}|W_j|+\sum_{i=1}^{k}|U_i|+\delta, \end{equation} where $\delta=0$ if $w\in W_t$ is paired with an $X$-pebble in the first step, and $\delta=1$ otherwise. By symmetry, if $S_{\alpha}=U_t$, then the number of steps for $p_0$ to be in place is \begin{equation}\label{eq02} \sum_{j=1}^{t}|Y_j|+\sum_{j=t}^{k}|U_j|+\sum_{i=1}^{l}|W_i|+\delta, \text{ where $\delta\in\{0,1\}$.} \end{equation} \iffalse \begin{lemma} Let $p_0$ be a pebble with initial window $$win(p_0)= win(p_0)=(U_k, Y_k, U_{k-1}, \ldots, U_1, Y_1, p_0, X_1, W_1, \ldots, X_l, W_l).$$ Then the number of steps for $p_0$ to be in place is $$\sum_{j=1}^{t}|X_j|+\sum_{j=t}^{l}|W_j|+\sum_{i=1}^{k}|U_i|+\delta,$$ where $\delta=0$ if $w\in W_t$ is paired with an $X$-pebble in the first step, otherwise $\delta=1$; or $$\sum_{j=1}^t |Y_j| + \sum_{j=t}^{k} |U_j| +\sum_{j=1}^{l} |W_j|+\delta,$$ where $\delta=0$ if $w\in U_t$ is paired with an $Y$-pebble in the first step, otherwise $\delta=1$. \end{lemma} \fi Therefore, every permutation that takes $n-1$ steps to route must contain a pebble $p_0$ such that (when $S_{\alpha}=W_t$) \begin{equation} \label{eq1} \sum_{j=1}^k |Y_j| + \sum_{j=t+1}^{l} |X_j| +\sum_{j=1}^{t-1} |W_j| + |Z|= \delta, \text{ where $\delta\in \{0,1\}$.} \end{equation} or (when $S_{\alpha}=U_t$) \begin{equation} \label{eq2} \sum_{j=1}^l |X_j| + \sum_{j=t+1}^{k} |Y_j| +\sum_{j=1}^{t-1} |U_j| + |Z| = \delta, \text{ where $\delta\in \{0,1\}$.} \end{equation} \bigskip Now we are ready to determine the extreme windows that need $n-1$ steps to route. \begin{lemma}\label{extremal-windows} Every permutation that takes $n-1$ steps to route must contain a pebble $p_0$ whose window is one of the following \begin{enumerate}[(i)] \item $|win(p_0)|=n$ and $win(p_0)=(p_0, X, W)$ (or $win(p_0)=(U, Y, p_0)$). \item $|win(p_0)|=n-1$ and $win(p_0)=(U, p_0, X, W)$ (or $win(p_0)=(U, Y, p_0, W)$). \item $|win(p_0)|=n$, and $win(p_0)=(p_0, X_1, W_1, X_2, W_2)$ and ${\rm min}(|W_1|, |X_2|)=1$ (or $win(p_0)=(U_2,Y_2,U_1,Y_1, p_0)$ and ${\rm min}(|Y_2|, |U_1|)=1$). \end{enumerate} In other words, if the window of a pebble is not one of the above ones, then in $n-2$ steps, the pebble will be in place. \end{lemma} \begin{proof} By symmetry, we may assume that \eqref{eq1} holds. As $\delta=0$ or $1$, all the terms in the left-hand side of \eqref{eq1} are zeros or ones. We first claim that when $|win(p_0)|=n$, $U_k$ or $W_l$ must be empty. For otherwise, let $u_p\in U_k$ and $w_q\in W_l$ be the furthest $U$-pebble and $W$-pebble to $p_0$, respectively. As $|win(p_0)|=n$, no pebble is bigger than $u_p$ and no pebble is smaller than $w_q$ by Lemma~\ref{induced-order}, so $s(u_p) \ge 1+|Y|+|W|$ and $s(w_q) \le -(1+|X|+|U|)$, and it follows that $s(u_p)-s(w_q)\ge n+1$, a contradiction. \medskip {\bf Case 1.} $\delta=0$ or $\delta=|Z|=1$. Then $\sum_{j=1}^k |Y_j|=\sum_{j=t+1}^l |X_j|=\sum_{j=1}^{t-1} |W_j|=0$. It follows that $Y=\emptyset$, $t=1=l$. So $win(p_0)=(U, p_0, X, W)$. By the above claim, when $|win(p_0)|=n$, $U$ or $W$ must be empty, so we have (i) or (ii) in the lemma, where $X$ (or $Y$) could be empty. %Note that $\sum_{j=1}^k |Y_j|=0$ implies that $Y=\emptyset$, thus there is at most one $U$-set; $\sum_{j=t+1}^l |X_j|=0$ means there are at most $t$ non-empty $X$-sets (the first $t$ sets); $\sum_{j=1}^{t-1} |W_j|=0$ means that $|W|=0$ (if $t\ge 2$) or there are at most one non-empty $W$-set (that is, $W_1$ when $t=1$). But if $t=2$, $|W|=0$ implies all $X$-sets are actually outside of window of $p_0$, so $|X|=0$ as well. Therefore, $win(p_0)=(U, p_0, X, W)$ so that if $W=\emptyset$ then $X=\emptyset$.\\ \medskip {\bf Case 2.} $\delta=1$ and $|Z|=0$. Then $|win(p_0)|=n$, and one of the following holds: \begin{itemize} \item $\sum_{j=1}^k |Y_j|=1$, and $\sum_{j=t+1}^l |X_j|=\sum_{j=1}^{t-1} |W_j|=0$. Then $|Y|=1, t=l=1$. So there are at most two $U$-sets, $U_1$ and $U_2$, and when there are two, $Y_1=\emptyset$ and $|Y_2|=1$. Because of the above claim, we have $win(p_0)=(U_2, y, U_1, p_0)$. \item $\sum_{j=t+1}^l |X_j|=1$ and $\sum_{j=1}^k |Y_j|=\sum_{j=1}^{t-1} |W_j|=0$. Then $Y=\emptyset$ and $t=|X_2|=1$. Because of the above claim, $win(p_0)=(p_0, X_1, W_1, x_2, W_2)$. \item $\sum_{j=1}^{t-1} |W_j|=1$ and $\sum_{j=1}^k |Y_j|=\sum_{j=t+1}^l |X_j|=0$. Then $Y=\emptyset$, $t=2$ and $|W_1|=1$, and $X_i=\emptyset$ for $i\ge 3$. Because of the above claim, $win(p_0)=(p_0, X_1, w_1, X_2, W_2)$. \end{itemize} So we have the desired extremal windows in the lemma. \end{proof} \section{Proof of Theorem~\ref{thework}}\label{solution} In this section, we show how to deal with the extremal situations in Lemma~\ref{extremal-windows}. For each of the extreme windows, we will decompose it into blocks of the following kinds. Let $q_1, q_2, \ldots, q_s$ be a segment of pebbles. It is called a {\em block with head $q_1$} if $q_1\succ q_i$ for $i\ge 2$ and the other pebbles are incomparable; it is called a {\em block with tail $q_s$} if $q_i\succ q_s$ for $i0$, then $X$ is an isolated block and $W$ can be partitioned into isolated blocks and blocks with heads so that the block next to $X$, say $W_0$, is isolated with $c$, and the order relation is $\{p_0\}\cup X\succ W$ and $z\succ W_0$. %\item if $U$ is empty and $s(z)=c<0$, then $W$ is isolated and $X$ can be partitioned into isolated blocks and blocks with tails so that the block next to $W$ is isolated with $|c|$ pebbles and bigger than $z$, and the only other order relation is $\{p_0\}\cup X\succ W$. %\item if $U$ is empty and $s(z)=0$, then either $X$ can be partitioned into isolated blocks and blocks with tails and $W$ is an isolated block or $W$ can be partitioned into isolated blocks and blocks with heads and $X$ is an isolated block, and the only other order relation is $\{p_0\}\cup X\succ W$. %\end{itemize} \end{lemma} \begin{proof} Let $U=u_1u_2\ldots u_p, X=x_1x_2\ldots x_a$ and $W=w_1w_2\ldots w_b$. Consider the spins of $u_1$ and $w_b$. As no pebble is bigger than $u_1$ and $u_1\succ \{p_0\}\cup W$, $s(u_1)\ge 1+|W|=1+b$. Similarly, no pebble is smaller than $w_b$ and $U\cup \{p_0\}\cup X\succ w_b$, so $s(w_b)\le -(1+|U|+|X|)=-(1+a+p)$. So $s(u_1)-s(w_b)\ge 1+b+1+a+p=n$, and the equality must hold. So $s(u_1)=1+b, s(w_b)=-(1+a+p)$ and the only order relation involving $u_1$ and $w_b$ are $u_1\succ \{p_0\}\cup W$ and $U\cup \{p_0\}\cup X\succ w_b$. Inductively we can consider $u_2$ and $w_{b-1}$ and all pebbles in $U$ and $W$ and conclude that $U\cup \{p_0\}\cup X\succ W$ is the only order relation involving $U$ and $W$. %Let $U=u_1u_2\ldots u_k, X=x_1x_2\ldots x_a$ and $W=w_1w_2\ldots w_b$ along the positive direction. \red{Applying lemma \ref{spin}, we have $s(u_1)=1+|W|=1+b, s(w_b)=-(1+|U|+|X|)=-(1+a+k)$, $u_1$ and $w_b$ are maximal and minimal pebbles respectively,} the only order relation involving $u_1$ and $w_b$ are $u_1\succ \{p_0\}\cup W$ and $U\cup \{p_0\}\cup X\succ w_b$. \blue{Inductively} we can consider $u_2$ and $w_{k-1}$ and all pebbles in $U$ and $W$ and conclude that $U\cup \{p_0\}\cup X\succ W$ is the only order relation involving $U$ and $W$. Now consider the spins of pebbles in $X$. As $s(w_b)=-(1+a+k)$ and $s(x)-s(w_b)\le n$ for each $x\in X$, we have $s(x)\le b+1$. Note that $z$ cannot be bigger than any pebble in $X$, for otherwise $z\succ W$ and contradict to what we just concluded. But $z$ may be smaller than some pebbles in $X$, thus $s(z)\le 0$. Consider $x_1$. By Lemma~\ref{induced-order}, no pebble is bigger than $x_1$. As $x_1\succ W$, $s(x_1)\ge |W|=b$. So $s(x_1)\in \{b, b+1\}$. Let $s(x_1)=b+1$. Then the order relations involving $x_1$ are $x_1\succ W\cup\{x_i\}$ for some $2\le i\le a$ or $x_1\succ W\cup\{z\}$; if $x_1\succ z$, then $x_j\succ z$ for $1\le j\le a$ by Lemma~\ref{induced-order} and we inductively conclude $s(x_j)=b+1$, thus $X$ is an isolated block and $X\succ z$; if $x_1\succ x_i$ for some $2\le i\le a$, then $x_j\succ x_i$ for $1\le j0$, then $X$ is an isolated block and $W$ can be partitioned into isolated blocks and blocks with heads, say $W_1, W_2, \ldots, W_r$, so that $W_1$ is isolated with $c$ pebbles and $z\succ W_1$, and the only other order relation is $\{p_0\}\cup X\succ W$. \item if $s(z)=c<0$, then $W$ is isolated and $X$ can be partitioned into isolated blocks and blocks with tails, say $X_1, \ldots, X_r$, so that $X_r$ is isolated with $|c|$ pebbles and $X_r\succ z$, and the only other order relation is $\{p_0\}\cup X\succ W$. \item if $s(z)=0$, then either $X$ can be partitioned into isolated blocks and blocks with tails and $W$ is an isolated block, or $W$ can be partitioned into isolated blocks and blocks with heads and $X$ is an isolated block, and the only other order relation is $\{p_0\}\cup X\succ W$. \end{enumerate} \end{lemma} The proof of this lemma is very similar to Lemma~\ref{block-2}, and for completeness, we include a proof below. \begin{proof} Let $\pi=zp_0x_1x_2\ldots x_aw_1w_2\ldots w_b$, where $x_i\in X$ and $w_i\in W$. Clearly, $s(p_0)=|W|=b$. By Lemma~\ref{induced-order}, $X\succ W$. As $z$ is incomparable with $p_0$, no pebble in $W$ is bigger than $z$. %Similarly, no pebble in $X$ is smaller than $z$ (but could be bigger than $z$), thus $z$ could only cause pebbles in $X$ move one step along the positive direction. %Let $\pi=zp_0x_1x_2\ldots x_aw_1w_2\ldots w_b$ along the positive directions, where $x_i\in X$ and $w_i\in W$. Clearly, \red{$s(p_0)=|W|=b$ by lemma \ref{spin}}. As $z$ is incomparable with $p_0$, no pebble in $W$ is bigger than $z$ (but could be smaller than $z$), thus $z$ could only cause pebbles in $W$ move one step along the negative direction. Similarly, no pebble in $X$ is smaller than $z$ (but could be bigger than $z$), thus $z$ could only cause pebbles in $X$ move one step along the positive direction. % By symmetry we will only consider the case $s(z)=c\ge 0$. Consider $w_b$. Since $\{p_0\}\cup X\succ w_b$, and no pebble is smaller than $w_b$ by Lemma~\ref{induced-order}, $s(w_b)\le -(|X|+1)=-(a+1)$. On the other hand, $s(p_0)-s(w_b)\le n$, for otherwise the flip of spins of $p_0$ and $w_b$ gives a smaller disbursement, so $s(w_b)\ge -(a+2)$. Therefore $s(w_b)\in \{-(a+1), -(a+2)\}$. Clearly, if $s(w_b)=-(a+1)$, then $\{p_0\}\cup X\succ w_b$ is the only order relation involving $w_b$, thus $w_b$ is in an isolated block. We shall move to consider $w_{b-1}$. Now let $s(w_b)=-(a+2)$. Then exactly one pebble in $\{z\}\cup (W-w_b)$ is bigger than $w_b$. If $z\succ w_b$, then by Lemma~\ref{induced-order}, $z\succ w_j$ for each $w_j\in W-w_b$; thus, inductively we conclude that the only order relation involving $W$ is $\{z, p_0\}\cup X\succ W$, and $W$ is an isolated block. %\red{For $w\in W$, $s(p_0)-s(w)\le n$ implies $s(w)\ge b-n=-(a+2)$. Note that $p_0\succ w_b$ implies $s(w_b)\le s(p_0)-d^+(p_0, w_b)-1=b-(n-2)-1=-(a+1)$.} Therefore $s(w_b)\in \{-(a+1), -(a+2)\}$, and $s(w_b)=-(a+2)$ if and only if $w_b$ is smaller than $z$ or some pebble in $W$ but not both \red{since $w_b$ is minimal by lemma \ref{spin}.} If $w_b$ is not smaller than $z$ and any other pebbles in $W$, then we call $w_b$ to be {\em isolated} and in this case $s(w_b)=-(a+1)$. If $w_i\succ w_b$ for some $i0$, $W_i$ is either an isolated block or a block with a head (say $w_{i'}$). %the block $W_i$, if not isolated, has head $w_{i'}$ and $W_0$ is an isolated block with $c$ pebbles which are all smaller than $z$. If $c=b$, then the spins of $\{z, p_0\}\cup X$ are all $b$ and the spins of $X$ are all $-(a+2)$, and $\pi$ is a rotation. By Lemma~\ref{rot}, if $\pi$ needs $n-1$ steps to route, $\pi$ must be one of the two extremal permutations. So we assume $cc\ge 1$). If $w_1$ is not smaller than $z$, then $s(z)=0$, and $w_1$ will be in place after at most $(a+1)+1+|W_i|-10$, then the block $W_0$ in $W_1$ next to $X_1$ is an isolated block with $c$ elements and are all smaller than $x$; and the only other order relation between segments are $\{p_0\}\cup X_1\succ W_1\cup W_2, x\succ W_2\cup W_0$. \item if $win(p_0)=(p_0, X_1, w, X_2, W_2)$, then $X_2$ can be partitioned into isolated blocks and blocks with tails. Furthermore, $c:=s(w)+(1+|X_1|)\le 0$, and if $c<0$, then the block $X_0$ in $X_2$ next to $W_2$ is an isolated block with $-c$ elements and are all bigger than $w$; and the order relation between segments are $\{p_0\}\cup X_1\succ \{w\}\cup W_2$ and $X_0\succ w$. \end{itemize} \end{lemma} \begin{proof} We only prove the case when $win(p_0)=(p_0, X_1, W_1, x, W_2)$, and the other case is very similar. Let $W_1=w_1w_2\ldots w_a$ and $W_2=w_{a+1}w_2\ldots w_b$. Consider the spins of $p_0$ and $w_b$. Since $s(p_0) = b$ and by Lemma~\ref{induced-order}, no pebble is smaller than $w_b$, thus $s(w_b)\le -(2+|X|)=-(n-b)$; furthermore, as $s(p_0)-s(w_b)\le n$, we have $s(w_b)\ge -(n-b)$, so $s(w_b) = - (n-b)$, and the order relation involving $w_b$ is $\{p_0\}\cup X\succ w_b$. Now we can repeat the argument for $w_{b-1}, w_{b-2}, \ldots, w_{a+1}$ successively and get $s(w_i) = -(n-b)$ for all $w_i \in W_2$. Similarly, by comparing the spins of pebbles in $X_1$ to that of $w_b$, we have $s(x_i) = b$ for all $x_i \in X_1$. So $X_1$ and $W_2$ are isolated blocks. Since $s(p_0)=s(x)$ for each $x\in X_1$, let $X'_1 = X_1 \cup \{p_0\}$. %Let $W_1=w_1w_2\ldots w_a$ and $W_2=w_{a+1}w_2\ldots w_b$. Consider the spins of $p_0$ and $w_b$. \red{It is clear that $s(p_0)=|W_1|+|W_2|=b$ by lemma \ref{spin}(1), and we have $s(w_b)=b-n$ by lemma \ref{spin}(2) since $p_0\succ w_b$ and $d^+(p_0, w_b)=n-1$, $p_0$ and $w_b$ are maximal pebble of $P$ respectively, and the only pebbles that $w_b$ swaps with are $p_0$ and all $x$'s. Since $w_{b-1}$ will not swap with $w_b$, we get $s(w_{b-1}) \le b-n$. Note that $s(p_0)-s(w_{b-1})\le n$, thus we have $s(w_{b-1}) = b-n$ and the only pebbles that $w_{b-1}$ swaps with are $p_0$ and all $x$'s.} By induction, we have $s(w_i) = b-n$ for all $w_i \in W_2$. Similarly, by comparing the spins of pebbles in $X_1$ to that of $w_b$, we have $s(x_i) = b$ for all $x_i \in X_1$ \red{by induction.} Since $s(p_0)$ is the same as the pebbles in $X_1$, let $X'_1 = X_1 \cup \{p_0\}$. We have shown that $X_1$ and $W_2$ are isolated blocks. %Now the cycle has been divided into four segments, $X'_1, V_1, X_2,$ and $V_2$, where no segment is empty, either $|X_2| = 1$ or $|V_1|=1$, $s(X'_1) = q$, and $s(V_2) = -(n-q)$. From this point we assume $|X_2| = 1$. Let $x_2$ represent this pebble. (The case when $|V_1| =1$ is symmetric by swapping the labels $X_1$ and $V_2$ and swapping the labels $V_1$ and $X_2$.) Now we consider the spins of pebbles in $W_1$. %\red{NOTE: All $w_q, w_b$ have been replaced by $w_a$ in the following two paragraphs. } We note that no pebble in $W_1$ is bigger than $x$, for otherwise $p_0$ would be bigger than $x$ as $p_0\succ W_1$. Consider $w_a$. The pebbles in $X_1'$ are bigger than $w_a$ and by Lemma~\ref{induced-order}, no pebble is smaller than $w_a$, so $s(w_a)\le -|X_1'|=b-n+1$. On the other hand, $s(p_0)-s(w_a)\le n$ and $s(p_0)=b$ implies $s(w_a)\ge b-n$. That is, $s(w_a)\in \{b-n, b-n+1\}$, and at most one pebble other than those in $X_1'$ is bigger than $w_a$. If $s(w_a) = b-n+1$, then $\{p_0\}\cup X_1\succ w_a$ is the only order relation involving $w_a$, and we turn to consider $w_{a-1}$. If $s(w_a)=b-n$, then $w_a$ is smaller than $x$ or some pebble $w_i\in W_1$; in the former case, all pebbles in $W_1$ are smaller than $x$ and inductively one can show that they are incomparable and thus $W_1$ is an isolated block; in the latter case, $w_i\succ w_j$ for $i+1\le j\le a$ and $w_i$ is the only such pebble other than those in $X_1'$, so $w_iw_{i+1}\ldots w_a$ is a block with head $w_i$. Inductively one can have a partition of $W_1$ into blocks, as desired. We observe that if $x\succ w_i\in W_1$ then $w_i$ is in an isolated block and $x\succ \{w_1, w_2, \ldots, w_i\}$ by Lemma~\ref{induced-order}. Let $c:=s(x)-|W_2|$. Then $W_0:=(w_1,\cdots, w_c)$ is an isolated block, $x\succ W_2\cup W_0$ is the only order relation involving $x$, as desired. \end{proof} \begin{lemma} If a permutation $\pi$ contains a pebble $p_0$ such that $win(p_0)=\pi=(p_0, X_1, W_1$, $x, W_2)$ or $win(p_0)=\pi=(p_0, X_1, w, X_2, W_2)$, then $\pi$ can be routed in $n-2$ steps. \end{lemma} \begin{proof} Again we only consider the case $win(p_0)=(p_0, X_1, W_1, x, W_2)$, as the other one is very similar. Let $win(p_0)=(p_0x_1x_2\ldots x_kw_1\ldots w_axw_{a+1}\ldots w_b)$ with $x_i\in X_1$ and $w_i\in W_1\cup W_2$. By Lemma~\ref{block-3}, $X_1, W_2$ are isolated blocks, and $W_1=\cup_{i=0}^r W_1^i$, where $x\succ W_1^0$, and $W_1^i$ for $i>0$ is an isolated block or a block with head $w_1^i$. We flip the spins of $p_0$ and $w_b$, and then use an odd-even routing algorithm with odd edge $x_kw_1$ to route the permutation. Now by Lemma~\ref{flip-spins} and Lemma~\ref{block-3}, the order relations under the new disbursement are $$X_1\cup \{w_b\}\succ W_1\cup (W_2-w_b)\cup \{p_0\},\quad x\succ (W_2-w_b)\cup W_1^0\cup\{p_0\}, \quad w_1^i\succ W_1^i-w_1^i \text{ for some $i$}.$$ We list the windows for the pebbles in $X_1\cup \{w_b, x, w_1^i: 1\le i\le r\}$: \begin{align*} win(x_i)&=(x_i, X_1-\{x_j: 1\le j\le i\}, W_1, x, W_2-w_b, p_0), \\ win(w_1^i)&=(w_b, p_0, X_1, \cup_{j=0}^{i-1}W_1^j, w_1^i, W_1^i-w_1^i),\\ win(x)&=(x, W_2-w_b, w_b, p_0, X_1, W_1^0),\\ win(w_b)&=(w_b, p_0, X_1, W_1, x, W_2-w_b). \end{align*} %where the leftmost is a $U$-segment (or the pebble itself) to the pebble, and the rightmost is a $W$-segment (or the pebble itself) to the pebble, and the rest is alternatively $U, Y$-segments (on the left of the pebble) and $X,W$-segment (on the right of the pebble). %We will use an odd-even routing algorithm with odd edge $x_kw_1$. By Lemma~\ref{consecutive-swaps}, $p_0$ and $w_b$ will swap in the first or second step depending on the parity of the edge $p_0w_b$, thus after the first two steps, we may think $w_b$ is part of $X_1$ and $p_0$ is part of the new $W_2$; Again by the lemma, $x_k$ meets $W_1$ in the first step and will swap with $|W_1|$ elements in the next $|W_1|$ steps, and by then it will meet $W_2-w_b+p_0$ and swap with all of them, so it takes $|W_1|+|W_2|=b