\newcommand{\bw}[1]{\mbox{\texttt{#1}}} \begin{theorem}\label{thm:chain} For every $k\ge1$, $\ \diam\CP(B_k)\le\lfloor2k/3\rfloor+1$. \end{theorem} Together with Corollary~\ref{cor:chainlower}, Theorem~\ref{thm:chain} gives part~(ii) of Theorem~\ref{thm:main}. This section contains the proof of Theorem~\ref{thm:chain}. Throughout, $d(X,Y)$ is the distance of two antichains $X,Y$ in the graph of $\CP(B_k)$, and \[ f(0)=0,\qquad f(m)=\lfloor2m/3\rfloor+1\quad(m\ge1). \] \emph{Outline of the proof.} Lemma~\ref{lem:split} reduces the theorem to pairs of disjoint antichains whose union is an antichain $U$. Walks for such pairs are built from short walks on a few columns, which are performed one after the other or merged into common moves (Lemma~\ref{lem:merge}). (Splits, walks, runs and empty columns are defined in Subsection~\ref{ssec:words}.) Subsections~\ref{ssec:comb}--\ref{ssec:fullword} treat a set $U$ without empty columns; every split of such a set with $L\ge2$ columns has a walk of length at most $\lceil L/2\rceil+1$ (Proposition~\ref{prop:fullword}). An induction across empty columns (Subsection~\ref{ssec:chainproof}) leaves one family of patterns (Proposition~\ref{prop:cores}), in which runs of lengths $3$, then $2$ or $5$, \dots, and finally $3$ are separated by single empty columns. For these, local walks are joined across each empty column, and each join merges two moves into one (Subsections~\ref{ssec:join} and~\ref{ssec:local}). \subsection{Words, splits 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} $\omega_1\omega_2\cdots\omega_k$ over the alphabet $\{a,b,c,-\}$, where $\omega_i$ is the letter of the element of $X$ in the $i$-th column, and $\omega_i=-$ if there is none; then the column is \emph{empty}. By~\eqref{eq:cross}, a word over $\{a,b,c,-\}$ is the word of an antichain exactly if it has no two neighboring letters $\omega_i\omega_{i+1}$ equal to $ab$, $ac$, $ca$ or $cb$; a letter $b$ or $-$ 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$; so the word of a run is $b^ix^j$ with $x\in\{a,c\}$ and $i,j\ge0$. The elements $a_i$ and $c_i$ are \emph{outer} elements, and $b_i$ is a \emph{middle} element. For $x\in\{a,c\}$ we write $x_i$ for the element of the row $x$ in column $i$, and $\bar x$ for the other outer letter. 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. So 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. We therefore describe local constructions on the columns $1,\dots,L$ or $0,\dots,L$ of a band, and use them on any interval of columns of $B_k$. For integers $s\le e$, the \emph{band on the columns $s,\dots,e$} is the poset of the elements $a_i,b_i,c_i$ $(s\le i\le e)$ with the comparable pairs of Lemma~\ref{lem:pairs}; it is a translated copy of $B_{e-s+1}$. \begin{lemma}\label{lem:colconn} A nonempty set $F\subseteq B_k$ is connected exactly if the columns that meet $F$ 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} A \emph{walk} of length $n=|W|$ from $X_0$ to $X_n$ is a sequence $W=(X_0,\dots,X_n)$ of antichains in which every \emph{difference} $X_{t-1}\sd X_t$ is connected; by Theorem~\ref{thm:adjacency} consecutive antichains are then adjacent. The antichains $X_0,\dots,X_n$ are the \emph{states} of $W$, and $X_0$ and $X_n$ are its \emph{initial} and \emph{final sets}. The \emph{move} $t$ exchanges this difference. We often write walks as sequences of words. The \emph{reversal} $(X_n,\dots,X_0)$ of a walk is a walk. 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, so it maps walks to walks; on words it exchanges the letters $a$ and $c$. A sequence of sets \emph{runs through} a walk $W$ if it becomes $W$ after consecutive repetitions are merged. 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 $-$ 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 $(-,c_e,a_e,-)$. \begin{lemma}[Splits]\label{lem:split} Let $X,Y$ be antichains of a finite poset $P$. There are disjoint antichains $A\subseteq X$ and $B\subseteq Y$ such that $A\cup B$ is an antichain and $d_{\CP(P)}(X,Y)\le d_{\CP(P)}(A,B)$. \end{lemma} \begin{proof} Write $d=d_{\CP(P)}$. For a set $S$ of elements let $N(S)$ be its open neighborhood in the comparability graph, that is, the set of elements that are comparable to some element of $S$ (comparable elements are distinct). For antichains $R,S$ put $\pi_R(S)=S\cup(R\setminus N(S))$; this is an antichain. We first show that if $S,S'$ are adjacent antichains, then $\pi_R(S)$ and $\pi_R(S')$ are equal or adjacent. Let $F=S\sd S'$, which is connected by Theorem~\ref{thm:adjacency}, and $F'=\pi_R(S)\sd\pi_R(S')$. Let $x\in F'\setminus F$. Elements of $S\cap S'$ lie in both images, so $x\notin S\cup S'$. Then $x\in R$, and $x$ lies in exactly one of $N(S)$, $N(S')$, say in $N(S)$. So $x$ is comparable to some $z\in S$, and $z\notin S'$. Hence every element of $F'\setminus F$ is comparable to an element of $F$. Let $x\in F$, say $x\in S\setminus S'$, so that $x\in\pi_R(S)$. If $|F|\ge2$, the connected set $F$ contains an element $y$ comparable to $x$. Since $S$ is an antichain, $y\in S'$; so $x\in N(S')$ and $x\notin\pi_R(S')$. Thus $F\subseteq F'$, and $F'$ is connected. If $F=\{x\}$ and $x\notin R$, then again $x\notin\pi_R(S')$, and $F'$ is connected. If $F=\{x\}$ and $x\in R$, then $x\notin N(S')$, because $S'\cup\{x\}=S$ is an antichain; so $x\in\pi_R(S')$. Moreover no element of the antichain $R$ is comparable to $x$, so $F'\subseteq F=\{x\}$; as $x$ lies in both images, $F'$ is empty, that is, $\pi_R(S)=\pi_R(S')$. With Theorem~\ref{thm:adjacency} this proves the claim, and consequently $d(\pi_R(S),\pi_R(S'))\le d(S,S')$ for all antichains $S,S'$. Now let $K=X\cap Y$, $X_1=X\setminus K$, $Y_1=Y\setminus K$, $R=X_1\cap N(Y_1)$, $A=X_1\setminus R$ and $B=Y_1$. Since $X$ and $Y$ are antichains, $\pi_K(X_1)=X$ and $\pi_K(Y_1)=Y$; hence $d(X,Y)\le d(X_1,Y_1)$. Since $R\subseteq X_1$ and $R\subseteq N(Y_1)$, we have $\pi_R(A)=X_1$ and $\pi_R(B)=B=Y_1$; hence $d(X_1,Y_1)\le d(A,B)$. Finally $A\subseteq X$ and $B\subseteq Y$ are disjoint, and no element of $A$ is comparable to an element of $B$; so $A\cup B$ is an antichain. \end{proof} A pair $(A,B)$ of disjoint sets whose union $U$ is an antichain is a \emph{split} of $U$. The elements of $A$ are \emph{initial} and those of $B$ are \emph{final}. A \emph{walk for} the split $(A,B)$ is a walk from $A$ to $B$, and the split \emph{has a walk} of length $n$ if there is such a walk of length $n$. By Lemma~\ref{lem:split}, $\diam\CP(B_k)$ is the largest distance $d(A,B)$ over all splits of antichains of $B_k$. 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 $t$ let $W_t=(X^t_0,\dots,X^t_{n_t})$ be a walk whose states are subsets of $D_t$. Group all moves of these walks into \emph{steps} $S_1,\dots,S_N$, so that each step is a nonempty set of moves, at most one of each walk, every move lies in exactly one step, and, for each walk, a later move lies in a later step. 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 N)$. Suppose 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_N)$ is a walk from $\bigcup_tX^t_0$ to $\bigcup_tX^t_{n_t}$ of length $N=\sum_tn_t-\sum_\alpha(|S_\alpha|-1)$. For each $t$, the sets $Z_\alpha\cap D_t$ run through $W_t$; in particular, if all elements of a column that occur in states of the walks lie in $D_t$, the walk $(Z_\alpha)$ has the same outer trace at this column as $W_t$. \end{lemma} \begin{proof} Since the sets $D_t$ 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. \end{proof} We call $(Z_\alpha)$ a \emph{merged walk}, and describe its steps in words: a move is performed \emph{alone} or \emph{together with} another move. 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_t$ 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 the 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 the move $\mu$. Lemma~\ref{lem:merge} applies. (ii) follows from (i) by reversal. \end{proof} \begin{lemma}[Reflection]\label{lem:reflect} Let $L\ge1$, and let $\Pi_L$ consist of the elements $a_t,c_t$ $(0\le t\le L)$ and $b_t$ $(1\le t\le L)$ of the band on the columns $0,\dots,L$. The involution $\rho$ of $\Pi_L$ given by \[ \rho(b_t)=b_{L+1-t},\qquad \rho(a_t)=a_{L-t},\qquad \rho(c_t)=c_{L-t} \] preserves comparability and incomparability. Hence it maps walks with states in $\Pi_L$ to walks with states in $\Pi_L$. \end{lemma} \begin{proof} By~\ref{it:P1}, the elements comparable to $b_t$ are $a_{t-1},a_t,c_{t-1},c_t$; they lie in $\Pi_L$, and $\rho$ maps them to $a_{L+1-t},a_{L-t},c_{L+1-t},c_{L-t}$, which are the elements comparable to $b_{L+1-t}$. By~\ref{it:P2}, $a_s$ and $c_t$ are comparable exactly if $|(L-s)-(L-t)|\le1$. The map $\rho$ preserves rows. \end{proof} The map $\rho$ sends the outer elements of column $t$ to column $L-t$, in particular those of column $L$ to column $0$, and the middle element of column $t$ to column $L+1-t$. \subsection{Walks along one outer row}\label{ssec:comb} \begin{lemma}[Rows of helpers]\label{lem:comb} Let $s\le e$ be columns, $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$ is present exactly from the move that exchanges its component in the first phase to the move that exchanges its component in the second phase. If $c_e\in C$, then the outer trace at $e$ is $(a_e,c_e,-)$ if $a_e\in A$, and $(-,c_e,a_e)$ if $a_e\in B$. \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$ exactly 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 exactly if $u=t+1$ with $t,t+2\in T$; we call such an element $a_u$ a \emph{glue} element. There are $m-1$ 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 exactly if $a_{t+1}\in A$. Therefore $A\cup C$ has $m-l_A$ components, where $l_A$ is the number of glue elements in $A$, and $C\cup B$ has $m-l_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-l_A-l_B=m+1$, because every glue element lies in exactly one of $A$, $B$. If $c_e\in C$, then $c_{e-1}\notin C$, so $a_e$ lies in the component of $c_e$ in its phase. Hence $a_e\in A$ is removed in the move that adds $c_e$, and $a_e\in B$ is added in the move that removes $c_e$. \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$ with states in the columns $s,\dots,e$; no state contains a middle element, and $a_s$ is the only element of column $s$ that occurs in a state. 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$. Apply $\sigma$ for the second statement. \end{proof} \subsection{Tame walks}\label{ssec:tame} \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 $(-,h,-)$ 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 the move $\mu$ and \emph{departs} with the move $\nu$. \end{definition} The reversal of a tame walk is tame. The image of a tame walk under $\sigma$ is tame, and $h$ changes its 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 entry~1 are on column $1$, those of entry~2 on the columns $0,1$, and those of entries~3 and~4 on the columns $1,2$. In this table and in Table~\ref{tab:local}, the first word is the initial set and the last word the final set. For each move, the table lists one comparable pair of elements of the difference for every two neighboring columns of the difference; `---' marks a difference inside one column; in the words, $-$ is the letter of an empty column. By Lemma~\ref{lem:colconn}, every difference is connected.}\label{tab:bases} \begin{tabular}{rllll} \toprule no. & walk & move 1 & move 2 & move 3\\ \midrule 1 & \bw{b}\ $\to$\ \bw{c}\ $\to$\ \bw{-{}} & --- & --- & \\ 2 & \bw{-{}b}\ $\to$\ \bw{aa}\ $\to$\ \bw{c-{}}\ $\to$\ \bw{-{}-{}} & $a_0b_{i+2}a_{i+2}$; $a_{i+1}a_{i+2}$; $b_{i+1}\mu'$ the move at which $a_i$ arrives. \emph{Step 2: two merges.} 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. 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}