For a set $T\subseteq\{1,\ldots,k\}$, write $b_T=\{b_i:i\in T\}$. Let $r(T)$ be the number of maximal intervals of integers contained in $T$, and let $s(T)$ be the number of those with at least two elements; both counts are zero for $T=\varnothing$. \begin{theorem}\label{thm:sparse} For every $T\subseteq\{1,\ldots,k\}$, \[ d_{\CP(B_k)}(\varnothing,b_T) \ge \left\lceil\frac{|T|+r(T)+s(T)}2\right\rceil. \] \end{theorem} The proof uses a potential $H(V,S)$ that depends on the current antichain $S$ and on the set $V$ of columns visited so far. \subsection{Visited columns}\label{ssec:visited} For an antichain $X$, let $\operatorname{supp}(X)$ be the set of indices of the columns that contain an element of $X$. For a walk $\varnothing=X_0,X_1,\dots,X_t$, the \emph{visited set} after $i$ moves is $V_i=\operatorname{supp}(X_0)\cup\dots\cup\operatorname{supp}(X_i)$. For a set $Z$ of column indices put $p(Z)=|Z|+r(Z)$; all sets of column indices are subsets of $\{1,\dots,k\}$. We write $[\,\cdot\,]$ for the Iverson bracket: it is $1$ if the statement inside holds and $0$ otherwise. Let $S\to S'$ be a move, and let $V$ be a set of column indices with $\operatorname{supp}(S)\subseteq V$. The set $F=S\sd S'$ is connected by Theorem~\ref{thm:adjacency}, so its columns form an interval $[L,R]$ by Lemma~\ref{lem:colconn}; in this section $L$ and $R$ always denote these ends. Put $V'=V\cup\operatorname{supp}(S')$. A column is \emph{new} if its index lies in $V'\setminus V$. Put $\varepsilon_L=[\,L\text{ is new and }L-1\notin V\,]$ and $\varepsilon_R=[\,R\text{ is new and }R+1\notin V\,]$. \begin{lemma}\label{lem:visited} Let $S\to S'$ be a move, and let $V$, $V'$, $[L,R]$, $\varepsilon_L$ and $\varepsilon_R$ be as above. \begin{enumerate}[label=\textup{(\alph*)}] \item Every new column lies in $[L,R]$, and no two new columns are neighbors. \item $p(V')-p(V)=\varepsilon_L+\varepsilon_R\le2$. \item If $Z\subseteq Z'$ are sets of column indices, then $p(Z)\le p(Z')$. \end{enumerate} \end{lemma} \begin{proof} For a set $Z$ of column indices and an index $j\notin Z$, let $n_Z(j)=|\{j-1,j+1\}\cap Z|$ be the number of neighbors of $j$ in $Z$. \emph{Step 1.} If $j\notin Z$, then $p(Z\cup\{j\})-p(Z)=2-n_Z(j)$. Indeed, $|Z|$ increases by one. If $n_Z(j)=0$, then $\{j\}$ is a new maximal interval of $Z\cup\{j\}$; if $n_Z(j)=1$, then $j$ extends one maximal interval of $Z$; if $n_Z(j)=2$, then $j$ joins two maximal intervals of $Z$ into one. So $r(Z)$ changes by $1-n_Z(j)$ in each of the three cases. \emph{Step 2: proof of \textup{(c)}.} Add the indices of $Z'\setminus Z$ to $Z$ one at a time. By Step~1, adding an index $j$ to the current set $Z_0$ changes $p$ by $2-n_{Z_0}(j)\ge0$. Hence $p(Z)\le p(Z')$. \emph{Step 3: first part of \textup{(a)}.} If $j$ is new, then $S$ has no element in column $j$, because $\operatorname{supp}(S)\subseteq V$, while $S'$ has one. That element lies in $F$, so $j\in[L,R]$. \emph{Step 4: second part of \textup{(a)}.} Suppose that two neighboring columns $j,j+1$ are both new. By Step~3 both lie in $[L,R]$. Hence, by Lemma~\ref{lem:colconn}, some $x\in F$ in one of them is comparable to some $y\in F$ in the other. Neither column contains an element of $S$, so $x,y\in S'$. This contradicts the fact that $S'$ is an antichain. \emph{Step 5: proof of \textup{(b)}.} Every column of $[L,R]$ contains an element of $F\subseteq S\cup S'$, so its index lies in $V$ or in $\operatorname{supp}(S')$, hence in $V'$. Therefore a column of $[L,R]$ that is not new lies in $V$. Now add the new columns to $V$ one at a time. By Step~4 no neighbor of a new column is new, so its neighbors in the current set are its neighbors in $V$. Therefore, by Step~1, adding a new column $j$ increases $p$ by $2-n_V(j)$. Let $j$ be new. If $LL$, then $R$ contributes $\varepsilon_R$. If $j=L=R$, then $j$ contributes $2-[L-1\in V]-[R+1\in V]=\varepsilon_L+\varepsilon_R$. Finally, $\varepsilon_L=0$ if $L$ is not new, and $\varepsilon_R=0$ if $R$ is not new. Summing the contributions gives $p(V')-p(V)=\varepsilon_L+\varepsilon_R$, and $\varepsilon_L,\varepsilon_R\le1$. \end{proof} \subsection{A potential for long runs in the middle row} We use the word representation from Section~\ref{sec:chain}: the word of an antichain $S$ is $\omega_1\omega_2\cdots\omega_k$, where $\omega_j\in\{a,b,c,-\}$ is the letter of the element of $S$ in column $j$, and $\omega_j=-$ if column $j$ contains no element of $S$. We also put $\omega_0=\omega_{k+1}=-$. As in Subsection~\ref{ssec:words}, the letters $a$ and $c$ are the \emph{outer letters}. Throughout, $V$ is a set of column indices with $\operatorname{supp}(S)\subseteq V$. \smallskip\noindent\emph{Components.} A \emph{component} of a set $Z$ of column indices is a maximal interval $[s,e]$ contained in $Z$ (a different notion from the components of a set of elements in Section~\ref{sec:prelim}). Thus $Z$ has exactly $r(Z)$ components. \smallskip\noindent\emph{Long $b$-runs.} A \emph{long $b$-run} of $S$ is an interval $[s,e]$ with $ss_1$, so $s\ge e_1+2$. All columns of $[s_1,v+1]$ lie outside $[L,R]$, so $\omega=\omega'$ there. Moreover $[s_1,v]\subseteq[R+1,v]\subseteq D_{\mathrm{right}}$ by Claim~2(b), and $D_{\mathrm{right}}\subseteq C'$ by Claim~2(c), since $D_{\mathrm{right}}$ meets $C'$. \emph{Step 5: the run $\beta'$ in $S$.} The letters of $\omega$ on $\beta'$ are $b$. The neighboring indices $s-1$ and $e+1$ lie in $[s_1,v+1]$, so by Step~4, $\omega_{s-1}=\omega'_{s-1}\ne b$ and $\omega_{e+1}=\omega'_{e+1}\ne b$. Hence $\beta'$ is a long $b$-run of $S$. It lies in $[s_1,v]\subseteq D_{\mathrm{right}}$. \emph{Step 6: credited runs in \textup{(b)}.} The index $e_1$ is the end of the long $b$-run $\psi$ of $S'$. It is also the end of a long $b$-run of $S$: by Step~4, $\omega_j=b$ for $s_1\le j\le e_1$ and $\omega_{e_1+1}=\omega'_{e_1+1}\ne b$, so the maximal interval on which $\omega$ equals $b$ and which contains $[s_1,e_1]$ ends at $e_1$ and has at least two columns. Apply Claim~3 with $D=D_{\mathrm{right}}$, $D'=C'$ and $t=e_1$, in case \textup{(B)}. We have $t\le s-2$. Hypothesis \textup{(i)} holds, because $[e_1,s]\subseteq[s_1,v]$ lies in $D_{\mathrm{right}}\cap C'$ and $\omega=\omega'$ there, by Step~4. So $\beta'$ is credited in $(V,S)$ exactly if it is credited in $(V',S')$. \emph{Step 7: proof of \textup{(c)}.} The runs assigned in \textup{(a)} start at $s\le L-2$, and those assigned in \textup{(b)} start at $s\ge R+2$; so no run is assigned in both parts. In \textup{(a)}, different left runs have different starts, and the assigned runs have the same starts. In \textup{(b)}, each run is assigned to itself. \end{proof} \medskip\noindent\textbf{Claim 6} (A new column at the left end of its component)\textbf{.} \textit{Let $L=R$, $\varepsilon_L=1$ and $\varepsilon_R=0$. Then $q(V',S')-q(V,S)\le1$.} \begin{proof}[Proof of Claim~6] \emph{Step 1.} Put $j=L=R$. By Claim~2(e), $j\notin V$ and $u=j$. Since $j$ is new and $\varepsilon_R=0$, we have $j+1\in V$. As $j\in C'$ and $j+1\in V\subseteq V'$, the component $C'$ contains $j+1$; so $v\ge j+1$, and $D=[j+1,v]$ is contained in $V$ by Claim~2(b). It is a component of $V$, because $j\notin V$ and $v+1\notin V$. It is the only component of $V$ contained in $C'=[j,v]$, because $V\cap C'=D$. By Claim~2(c), the other components of $V$ are the components of $V'$ other than $C'$, with the same letters; by~\eqref{eq:local}, each of them contributes equally to $q(V,S)$ and $q(V',S')$. Hence \[ q(V',S')-q(V,S)=q_{C'}(V',S')-q_D(V,S). \] \emph{Step 2.} We have $\omega_j=-$ because $j\notin V$, and $\omega'_j\ne-$ because $j\in V'\setminus V$ forces $j\in\operatorname{supp}(S')$. Also $\omega'_i=\omega_i$ for $i\ne j$. Moreover $\omega'_{j-1}=-$, because $j-1\notin V'$ (Claim~2(e) gives $u=j$). \emph{Step 3: $\omega'_j\in\{a,c\}$.} No long $b$-run of $S'$ contains $j$. A long $b$-run of $S'$ contained in $D$ is a long $b$-run of $S$, and conversely: the letters on $D$ agree, and at the index $j$ neither word has the letter $b$. So the marks of $(V',S')$ in $C'$ are the outer mark $\{j\}$, followed by the marks of $(V,S)$ in $D$. Every run mark in $D$ other than the leftmost mark of $D$ has the same left neighbor in both cases. If the leftmost mark of $D$ is a run mark, it is credited in $(V,S)$, since it has no left neighbor, and it is blocked in $(V',S')$, since its left neighbor is $\{j\}$. Hence $q_{C'}(V',S')\le q_D(V,S)$. \emph{Step 4: $\omega'_j=b$ and $\omega_{j+1}\ne b$.} Then $\omega'_{j-1}=-$ (Step~2) and $\omega'_{j+1}=\omega_{j+1}\ne b$, so the letter $b$ in column $j$ is not part of a long $b$-run of $S'$, and it is not an outer letter. Neither word has the letter $b$ in column $j+1$, so every long $b$-run of $S$ or of $S'$ in $C'$ lies in $[j+2,v]$; there, and at the neighboring indices $j+1$ and $v+1$, the two words agree. So the marks of $(V',S')$ in $C'$ are exactly the marks of $(V,S)$ in $D$. Hence $q_{C'}(V',S')=q_D(V,S)$. \emph{Step 5: $\omega'_j=b$ and $\omega_{j+1}=b$.} Let $[j+1,e]$ be the maximal interval containing $j+1$ on which $\omega$ equals $b$; it starts at $j+1$, because $\omega_j=-$. Since $\omega'_{j-1}=-$ and $\omega'=\omega$ on $D$, the interval $[j,e]$ is a long $b$-run of $S'$. It is the leftmost mark in $C'$, because $j=\min C'$; so it is credited. If $e\ge j+2$, then $[j+1,e]$ is a long $b$-run of $S$; it is the leftmost mark in $D$ because $j+1=\min D$, hence it is credited. All other marks of $(V,S)$ in $D$ and of $(V',S')$ in $C'$ lie in $[e+1,v]$, where the two words agree, and they are the same. So the marks in $C'$ are those in $D$, with $[j+1,e]$ replaced by $[j,e]$. Hence every other run mark has a left neighbor of the same kind in both cases, and $q_{C'}(V',S')=q_D(V,S)$. If $e=j+1$, then $\{j+1\}$ is a maximal interval on which $\omega$ equals $b$; it has one column, so it is not a mark. Since $\omega'_{j+2}=\omega_{j+2}\ne b$ (as $e=j+1$), all other marks of $(V,S)$ in $D$ and of $(V',S')$ in $C'$ lie in $[j+2,v]$, where the two words agree, and they are the same. So the marks in $C'$ are the run mark $[j,j+1]$, followed by the marks of $(V,S)$ in $D$, which all lie in $[j+2,v]$. The leftmost mark of $D$, if it is a run mark, is credited in both cases: in $(V,S)$ it has no left neighbor, and in $(V',S')$ its left neighbor is the run mark $[j,j+1]$. Every other run mark in $D$ has the same left neighbor in both cases. Hence $q_{C'}(V',S')=q_D(V,S)+1$. Steps~3--5 cover all letters $\omega'_j\in\{a,b,c\}$, and in each case $q_{C'}(V',S')-q_D(V,S)\le1$. \end{proof} \begin{proof}[Proof of Lemma~\ref{lem:history}] \emph{Step 1.} By Claim~2(c), the components of $V'$ other than $C'$ are exactly the components of $V$ disjoint from $C'$, and $\omega'=\omega$ on each of them; by~\eqref{eq:local}, each of them contributes the same number to $q(V',S')$ and to $q(V,S)$. Every other component of $V$ is contained in $C'$, by Claim~2(c). Hence \[ q(V',S')-q(V,S)=q_{C'}(V',S')-\sum_{D}q_D(V,S), \] where $D$ runs over the components of $V$ contained in $C'$. \emph{Step 2.} Let $N'$ be the set of credited long $b$-runs of $S'$ in $C'$, and let $N'_{\mathrm{left}}$, $N'_{\mathrm{central}}$ and $N'_{\mathrm{right}}$ be its left, central and right runs. By Claim~5, the runs in $N'_{\mathrm{left}}$, and the runs in $N'_{\mathrm{right}}$ other than $\psi$, are assigned different credited long $b$-runs of $S$, all lying in components of $V$ contained in $C'$. Hence the sum in Step~1 is at least $|N'_{\mathrm{left}}|+|N'_{\mathrm{right}}\setminus\{\psi\}|$, and \[ q(V',S')-q(V,S)\le|N'_{\mathrm{central}}|+[\,\psi\in N'_{\mathrm{right}}\,]. \] \emph{Step 3.} We show that $q(V',S')-q(V,S)\le2-\varepsilon_L-\varepsilon_R$. If $L=R$, $\varepsilon_L=1$ and $\varepsilon_R=0$, Claim~6 gives this bound. Otherwise we bound the two terms of Step~2. First, $|N'_{\mathrm{central}}|\le1-\varepsilon_L$. By Claim~4(a), $|N'_{\mathrm{central}}|\le1$. If $\varepsilon_L=1$, then either $Lv$; so there is no right run in $C'$. \emph{Step 4.} By Claim~2(d) and Step~3, \[ H(V',S')-H(V,S)=(\varepsilon_L+\varepsilon_R)+\bigl(q(V',S')-q(V,S)\bigr)\le2. \qedhere \] \end{proof} \begin{proof}[Proof of Theorem~\ref{thm:sparse}] Let $\varnothing=X_0,X_1,\dots,X_t=b_T$ be a walk of length $t=d_{\CP(B_k)}(\varnothing,b_T)$, with visited sets $V_i$ (Subsection~\ref{ssec:visited}). Then $\operatorname{supp}(X_{i-1})\subseteq V_{i-1}$ and $V_i=V_{i-1}\cup\operatorname{supp}(X_i)$, so Lemma~\ref{lem:history} gives $H(V_i,X_i)-H(V_{i-1},X_{i-1})\le2$. Initially $H(\varnothing,\varnothing)=0$. The word of $b_T$ has no outer letter, so $(V_t,b_T)$ has no outer mark, and every long $b$-run of $b_T$ is credited, whatever the visited set $V_t$ is. These long $b$-runs are the $s(T)$ maximal intervals in $T$ with at least two elements. Therefore \[ 2t\ge H(V_t,b_T)=p(V_t)+s(T)\ge |T|+r(T)+s(T), \] using Lemma~\ref{lem:visited}(c) and $T\subseteq V_t$. \end{proof} \begin{corollary}\label{cor:chainlower} For every $k\ge1$, \[ \diam\CP(B_k)\ge \lfloor2k/3\rfloor+1. \] \end{corollary} \begin{proof} Let $m\ge1$ and $\ell\in\{2,3,4\}$, put $k=3m+\ell-3$, and let \[ T=[1,\ell]\cup\bigcup_{i=1}^{m-1}[\ell+3i-1,\ell+3i]\subseteq\{1,\dots,k\}. \] Its maximal intervals are $[1,\ell]$ and $m-1$ intervals of length two, separated by single missing indices. So $|T|=2m+\ell-2$ and $r(T)=s(T)=m$, and Theorem~\ref{thm:sparse} gives $d_{\CP(B_k)}(\varnothing,b_T)\ge\lceil(4m+\ell-2)/2\rceil$. This is $2m$, $2m+1$ and $2m+1$ for $\ell=2,3,4$, that is, $\lfloor2k/3\rfloor+1$ for $k=3m-1$, $3m$ and $3m+1$. Every $k\ge2$ has one of these forms. For $k=1$, take $T=\{1\}$. \end{proof}