\begin{theorem}\label{thm:chain} For every $k\ge1$, $\ \diam\CP(B_k)\le\lfloor3(k+1)/4\rfloor$. \end{theorem} Throughout this section, $d(X,Y)$ is the distance between two antichains $X,Y$ in the graph of $\CP(B_k)$. By Lemma~\ref{lem:split} it suffices to bound $d(A,B)$ for every split $(A,B)$ of every antichain of $B_k$. Subsections~\ref{ssec:words}--\ref{ssec:junction} construct walks by combining walks on a small number of columns, either one after the other or merged into common moves. Subsection~\ref{ssec:fullword} combines them: if $k\ge2$ and every column of $B_k$ contains an element of an antichain $U$, then for every split $(A,B)$ of $U$ there is a walk from $A$ to $B$ of length at most $\lceil k/2\rceil+1$ (Proposition~\ref{prop:fullword}). An induction on $k$, which cuts $B_k$ at a column that contains no element of $U$, completes the proof (Subsection~\ref{ssec:chainproof}). \subsection{Words and merged walks}\label{ssec:words} An antichain contains at most one element of each column. We describe an antichain $X$ by the \emph{word} $x_1x_2\cdots x_k$ over the alphabet $\{a,b,c,\emp\}$, where $x_i$ is the letter of the element of $X$ in the $i$-th column (the letter of $a_i$, $b_i$, $c_i$ is $a$, $b$, $c$), and $x_i=\emp$ if there is none; we then call the $i$-th column \emph{empty} in $X$. By~\eqref{eq:cross}, a word describes an antichain if and only if it has no two neighboring letters $x_ix_{i+1}$ equal to $ab$, $ac$, $ca$ or $cb$; a letter $b$ or $\emp$ may be followed by any letter. A \emph{run} of a word is a maximal set of consecutive nonempty columns. Inside a run a letter $a$ can only be followed by $a$, and $c$ only by $c$; hence the word of a run is $b^ix^j$ with $x\in\{a,c\}$ and $i,j\ge0$. In tables and displayed walks, words are set in typewriter type. The elements $a_1,\dots,a_k$ form the \emph{row} $a$, and similarly for the rows $b$ and $c$. The elements $a_i$ and $c_i$ are \emph{outer} elements, and $b_i$ is a \emph{middle} element. By Lemma~\ref{lem:pairs}, two distinct elements are comparable exactly in the following cases: \begin{enumerate}[label=\textup{(P\arabic*)}] \item\label{it:P1} $b_j$ and one of $a_{j-1},a_j,c_{j-1},c_j$; \item\label{it:P2} $a_s$ and $c_t$ with $|s-t|\le1$. \end{enumerate} In particular, two elements of one row are incomparable, and two elements of one column are comparable. Comparability depends only on the rows of the two elements and on the difference of their column indices. Hence a translation of the column indices maps antichains to antichains, connected sets to connected sets, and walks to walks, provided that the translated elements exist. In Subsection~\ref{ssec:chainproof} we use this to regard walks in a smaller band $B_p$ as walks on any $p$ consecutive columns of $B_k$. \begin{lemma}\label{lem:colconn} A nonempty set $F\subseteq B_k$ is connected if and only if its columns form an interval and, for any two neighboring columns of this interval, some element of $F$ in one of them is comparable to some element of $F$ in the other. \end{lemma} \begin{proof} The elements of one column form a chain, and elements of columns that are not neighbors are incomparable. \end{proof} We often write walks as sequences of words. Let $\sigma$ exchange $a_i$ and $c_i$ for every $i$ and fix every $b_i$. By \ref{it:P1} and \ref{it:P2}, $\sigma$ preserves comparability (by Lemma~\ref{lem:pairs} it even reverses the order), so it maps walks to walks; on words it exchanges the letters $a$ and $c$. The \emph{outer trace} of a walk $W=(X_0,\dots,X_n)$ at a column $e$ is the sequence of the outer elements of $X_0,\dots,X_n$ in column $e$, written $\emp$ when there is none, after consecutive repetitions are merged. For example, if column $e$ holds $b_e$, then $c_e$, then $a_e$, then nothing, the outer trace at $e$ is $(\emp,c_e,a_e,\emp)$. A \emph{walk for} a split $(A,B)$ is a walk from $A$ to $B$. For a set $S$, the split \emph{induced} by $(A,B)$ on $S$ is $(A\cap S,B\cap S)$. The elements of $A$ are \emph{initial} and those of $B$ are \emph{final}. The reversal of a walk from $A$ to $B$ is a walk for the split $(B,A)$, in which initial and final elements are exchanged. \begin{lemma}[Merging walks]\label{lem:merge} Let $D_1,\dots,D_r$ be pairwise disjoint sets of elements of $B_k$, and for each $q$ let $W_q=(X^q_0,\dots,X^q_{n_q})$ be a walk whose states are subsets of $D_q$. Suppose that the moves of all these walks are partitioned into nonempty \emph{steps} $S_1,\dots,S_M$ such that each step contains at most one move of each walk and, for each $q$, the moves of $W_q$ lie in steps of increasing index. Let $Z_\alpha$ be the union of the states that the walks have reached after the steps $S_1,\dots,S_\alpha$ $(0\le\alpha\le M)$. Assume moreover that \begin{enumerate} \item every $Z_\alpha$ is an antichain, and \item for every step, the graph on its moves, in which two moves are joined when some element of the difference of one is comparable to some element of the difference of the other, is connected. \end{enumerate} Then $(Z_0,\dots,Z_M)$ is a walk from $\bigcup_qX^q_0$ to $\bigcup_qX^q_{n_q}$ of length $M=\sum_qn_q-\sum_\alpha(|S_\alpha|-1)$. If all elements of a column that occur in states of the walks lie in $D_q$, then $(Z_\alpha)$ has the same outer trace at this column as $W_q$. \end{lemma} \begin{proof} Since the sets $D_q$ are disjoint, $Z_{\alpha-1}\sd Z_\alpha$ is the disjoint union of the differences of the moves in $S_\alpha$. These are connected, and by~(ii) their union is connected. Each $Z_\alpha\cap D_q$ is the state that $W_q$ has reached after the steps $S_1,\dots,S_\alpha$, which gives the statement on outer traces. \end{proof} We call $(Z_\alpha)$ a \emph{merged walk}. A move $K$ is performed \emph{alone} if its step is $\{K\}$, and \emph{together with} a move $K'$ if both lie in one step; $K$ is performed \emph{just before} $K'$, and $K'$ \emph{just after} $K$, if the step of $K'$ immediately follows the step of $K$. If the walks are performed one after the other, all steps have one move and condition~(ii) holds trivially; condition~(i) then holds, for instance, when elements of different sets $D_q$ lie in columns at distance at least two. \begin{lemma}[Adding an element]\label{lem:ride} Let $W=(X_0,\dots,X_n)$ be a walk, and let $y$ be an element that lies in no state of $W$ and is comparable to an element of some state of $W$. \begin{enumerate} \item If $X_0$ has no element comparable to $y$, let $\mu$ be the least index such that $X_\mu$ has one. Then $(X_0\cup\{y\},\dots,X_{\mu-1}\cup\{y\},X_\mu,\dots,X_n)$ is a walk of length $n$. \item If $X_n$ has no element comparable to $y$, let $\nu$ be the largest index such that $X_{\nu-1}$ has one. Then $(X_0,\dots,X_{\nu-1},X_\nu\cup\{y\},\dots,X_n\cup\{y\})$ is a walk of length $n$. \end{enumerate} \end{lemma} \begin{proof} (i) Merge $W$ with the walk $(\{y\},\varnothing)$, performing its move together with move $\mu$ of $W$. The sets $X_t\cup\{y\}$ with $t<\mu$ are antichains by the choice of $\mu$. The state $X_\mu$ contains an element comparable to $y$, which is not in $X_{\mu-1}$; it lies in the difference of move $\mu$. Lemma~\ref{lem:merge} applies. (ii) follows from (i) by reversal. \end{proof} \subsection{Splits of one outer row}\label{ssec:comb} The next lemma joins the two parts $A$ and $B$ of a split of a row of outer elements $a_s,\dots,a_e$ through helpers: elements $c_t$ of every second column, which are pairwise incomparable. The walk first exchanges $A$ for the set of helpers, one component at a time, and then exchanges the helpers for $B$. \begin{lemma}\label{lem:comb} Let $s\le e$ be columns, $[s,e]=\{s,s+1,\dots,e\}$, $j=e-s+1$ and $U=\{a_s,\dots,a_e\}$. Let $T$ be either the set $\{s+1,s+3,\dots\}\cap[s,e]$ of \emph{even helper positions} (the second, fourth, \dots\ columns of the interval), provided that $j\ge2$, or the set $\{s,s+2,\dots\}\cap[s,e]$ of \emph{odd helper positions} (the first, third, \dots\ columns). Put $C=\{c_t:t\in T\}$, whose elements are the \emph{helpers}, and $m=|C|$. For every split $(A,B)$ of $U$ there is a walk from $A$ to $B$ of length $m+1$, with states in $U\cup C$, of the following form. Its first phase exchanges the components of $A\cup C$ one at a time, in any order, and ends at $C$; its second phase exchanges the components of $C\cup B$ one at a time, in any order. Thus every $c_t\in C$ lies exactly in the states after the move that exchanges its component in the first phase and before the move that exchanges its component in the second phase. \end{lemma} For even helper positions $m=\lfloor j/2\rfloor$, and the length is $\lfloor j/2\rfloor+1$; for odd ones $m=\lceil j/2\rceil$, and the length is $\lceil j/2\rceil+1$. \begin{proof} The helpers $c_t\in C$ are pairwise incomparable, and by~\ref{it:P2} the element $a_u$ is comparable to $c_t$ if and only if $|u-t|\le1$. Consecutive elements of $T$ differ by two, the least one is $s$ or $s+1$, and the largest is $e$ or $e-1$. Hence every element $a_u$ of $U$ is comparable to one or two helpers, and to two if and only if $u=t+1$ with $t,t+2\in T$. There are $m-1$ such \emph{glue} elements. So every component of $A\cup C$ contains a helper, and two consecutive helpers $c_t$, $c_{t+2}$ lie in the same component if and only if $a_{t+1}\in A$. Therefore $A\cup C$ has $m-\gamma_A$ components, where $\gamma_A$ is the number of glue elements in $A$, and $C\cup B$ has $m-\gamma_B$ components. By Proposition~\ref{prop:components}, applied to the disjoint antichains $A$ and $C$ and to $C$ and $B$, exchanging these components one at a time, in any order, gives walks from $A$ to $C$ and from $C$ to $B$. Their total length is $2m-\gamma_A-\gamma_B=m+1$, because every glue element lies in exactly one of $A$, $B$. \end{proof} \begin{corollary}\label{cor:comb} Let $j=e-s+1\ge1$. Every split of $\{a_s,\dots,a_e\}$ has a walk of length $\lfloor j/2\rfloor+1$ whose states contain no middle element and lie in the columns $s,\dots,e$, and in which $a_s$ is the only element of column $s$ that occurs. The same holds for $\{c_s,\dots,c_e\}$, with $c_s$. \end{corollary} \begin{proof} For $j=1$, exchange $a_s$ alone; for $j\ge2$, use Lemma~\ref{lem:comb} with even helper positions, none of which is $s$. In both cases the states lie in $U\cup C$, which contains no middle element. Apply $\sigma$ for the second statement. \end{proof} \subsection{Tame walks}\label{ssec:tame} From now on all walks are walks in $B_k$, so every column index that occurs is at most $k$. \begin{definition}\label{def:tame} Let $i\ge1$. A walk $W=(X_0,\dots,X_n)$ is \emph{tame at column $i$} if all its states consist of elements of the columns $\le i$, and its outer trace at column $i$ is $(\emp,h,\emp)$ for an outer element $h$ of column $i$. Then $h$ lies exactly in the states $X_\mu,\dots,X_{\nu-1}$ for some $1\le\mu<\nu\le n$; it \emph{arrives} with move $\mu$ and \emph{departs} with move $\nu$. \end{definition} Tame walks are designed for Lemma~\ref{lem:tameext}: a walk that is tame at column $i$ extends to the middle elements of the next two columns at the cost of a single move. The reversal of a tame walk is tame. The image of a tame walk under $\sigma$ is tame, and $\sigma(h)$ is the outer element of column $i$ in the other row. If the initial and final sets of $W$ consist of middle elements, $\sigma(W)$ has the same initial and final sets; then the row of $h$ can be prescribed. \begin{table}[ht] \centering\footnotesize \caption{Tame bases. The words of line~1 are on column $1$, and those of lines~2 and~3 on the columns $1,2$. In each line, the first word is the initial set and the last word the final set. Every move of line~1 and every first move has its difference in one column. For moves~2 and~3 of lines~2 and~3, the difference meets both columns, and the table lists a comparable pair of its elements, one in each column. By Lemma~\ref{lem:colconn}, every difference is connected.}\label{tab:bases} \begin{tabular}{rlll} \toprule no. & walk & move 2 & move 3\\ \midrule 1 & \bw{b}\ $\to$\ \bw{c}\ $\to$\ \bw{-{}} & & \\ 2 & \bw{-{}-{}}\ $\to$\ \bw{a-{}}\ $\to$\ \bw{cc}\ $\to$\ \bw{bb} & $a_1\mu'$ the move at which $a_i$ is added. \emph{Part 2: merging $W'$ with a walk on the columns $>i$.} Let $S=\{a_{i+1},\dots,a_L\}$, and let $Q$ be the walk of Lemma~\ref{lem:comb} for the split $(A''\cap S,B''\cap S)$ of $S$, with odd helper positions $i+1,i+3,\dots$; its length is $\lceil j/2\rceil+1$. Its only helper comparable to $a_{i+1}$ is $c_{i+1}$. Let $K_1$ be the move of its first phase that exchanges the component of $c_{i+1}$, which contains $a_{i+1}$, and let $K_2$ be the move of its second phase that exchanges the component of $c_{i+1}$. Order the phases so that $K_1$ is the last move of the first phase and $K_2$ the first move of the second. We merge $W'$ and $Q$: perform the first phase before $K_1$; then the moves of $W'$, with $K_1$ together with $\mu'$ and $K_2$ together with $\nu'$; then the rest of the second phase. The states of $W'$ lie in the columns $\le i$, and those of $Q$ in the columns $\ge i+1$, where column $i+1$ holds only $a_{i+1}$ or $c_{i+1}$. Since $b_i$ is incomparable to column $i+1$, the only comparable pairs between the two walks are $a_{i+1}