If one attaches shifted copies of a skew tableau to the right of itself and rectifies, at a certain point the copies no longer experience vertical slides, a phenomenon called tableau stabilization. While tableau stabilization was originally developed to construct the sufficiently large rectangular tableaux fixed by given powers of promotion, the purpose of this paper is to improve the original bound on tableau stabilization to the number of rows of the skew tableau. In order to prove this bound, we encode increasing subsequences as lattice paths and show that various operations on these lattice paths weakly increase the maximum combined length of the increasing subsequences.

§ INTRODUCTION

Tableau stabilization was introduced in [1] in order to construct sufficiently large rectangular tableaux fixed by given powers of promotion. Rhoades first counted the number of rectangular tableaux fixed by the powers of promotion by exhibiting a remarkable cyclic sieving phenomenon for the action of promotion on rectangular tableaux [3]. But his representation-theoretic technique said nothing about what the actual fixed points were. In [1], Ahlbach exhibited these fixed points for sufficiently rectangular tableaux by applying the rectification operator to skew tableaux formed by attaching shifted copies of a skew tableaux to itself. This naturally gives rise to the notion of tableaux stabilization.

For any standard skew tableau $ T $ with weakly decreasing row sizes from top to bottom, let $ T^{(k)} $ denote the result of attaching $ (k - 1) $ shifted copies of $ T $ to the right of $ T $ so that the result is a standard skew tableau. Let $ n $ denote the size of $ T $ and $ k $ be a positive integer. Let $ \Rect $ denote Schützenberger's rectification operator. We say $ T $ stabilizes at $ k $ if each entry of $[(k - 1)n + 1, kn]$ in $\Rect(S^{(k)})$ lies in the same row as it does in $S^{(k)}$. Let $ \stab(S) $ denote the minimum value at which $ S $ stabilizes.

Having weakly decreasing row sizes from top to bottom is required for $ T^{(k)} $ to be a standard skew tableau for all $ k \ge 1 $. If this is not the case, $ T^{(k)} $ need not be standard. Consider <Ref>, where $ T^{(2)} $

\[
\Yvcentermath1 T = \begin{ytableau} \none & 2 \\
1 & 3
\end{ytableau}
\imp T^{(2)} = \begin{ytableau} \none & 2 & *(orange) 5 \\
1 & 3 & *(orange) 4 & *(orange) 6
\end{ytableau} \, ,
\]

The number of boxes in each row has to be weakly decreasing from top to bottom, or else $ T^{(k)} $ need not be standard.

is not a skew tableau both because of its shape and the third column not being increasing.

\begin{align*}
S & = \byt \none & \none & 1 & 3 \\ \none & \none & 5 & 6 \\ 2 & 4 \eyt \, , \\
S^{(3)} & = \byt \none & \none & 1 & 3 &  *(orange) 7 &  *(orange) 9 & *(cyan) 13 & *(cyan) 15 \\ \none & \none & 5 & 6 &  *(orange) 11 &  *(orange) 12 & *(cyan) 17 & *(cyan) 18 \\ 2 & 4 &  *(orange) 8 &  *(orange) 10 & *(cyan) 14 & *(cyan) 16 \eyt \, , \\
\Rect(S^{(3)}) & =  \byt 1 & 3 & 5 & 6 &  *(orange) 7 &  *(orange) 9 & *(cyan) 13 & *(cyan) 15 \\ 2 & 4 &  *(orange) 11 &  *(orange) 12 & *(cyan) 17 & *(cyan) 18 \\  *(orange) 8 &  *(orange) 10 & *(cyan) 14 & *(cyan) 16 \eyt \, .
\end{align*}

Example of a skew tableau $S$, the tableau $S^{(3)}$ constructed from $S$, and its rectification.

In Figure <ref>, $ 2 $ does not lie in the same row in $ S^{(3)} $ and $ \Rect(S^{(3)}) $, but $ 7, 8, \dots, 12 $ do. Hence, $ \stab(S) = 2 $. As $ 13, 14, \dots, 18 $ also stay in the same row in $ S^{(3)} $ and $ \Rect(S^{(3)}) $, $ S $ stabilizes at 3 as well. In Figure <ref>, 9 does not lie in the same row in $ T^{(3)} $ and $ \Rect(T^{(3)}) $, but $ 15, 16, \dots, 21 $ do, so $ \stab(T) = 3 $.

\begin{align*}
T & = \byt \none & \none & \none & 4 & 5 & 6 \\ \none & \none & 3 & 7 \\ 1 & 2 \eyt \, , \\
T^{(3)} & = \byt \none & \none & \none & 4 & 5 & 6 & *(orange) 11 & *(orange) 12 & *(orange) 13 & *(cyan) 18 & *(cyan) 19 & *(cyan) 20 \\ \none & \none & 3 & 7 & *(orange) 10 & *(orange) 14 & *(cyan) 17 & *(cyan) 21 \\ 1 & 2 & *(orange) 8 & *(orange)  9 & *(cyan) 15 & *(cyan) 16 \eyt \, , \\
\Rect(T^{(3)}) & = \byt 1 & 2 & 3 & 4 & 5 & 6 & *(orange) 11 & *(orange) 12 & *(orange) 13 & *(cyan) 18 & *(cyan) 19 & *(cyan) 20 \\ 7 & *(orange) 9 & *(orange) 10 & *(orange) 14 & *(cyan) 17 & *(cyan) 21 \\ *(orange) 8 & *(cyan) 15 & *(cyan) 16 \eyt \, .
\end{align*}

Example of a skew tableau $T$, the tableau $T^{(3)}$ constructed from $T$, and its rectification.

Ahlbach proved that once a tableaux stabilizes, it continues to stabilize, <cit.>. In the special case where the rows of $ T $ have the same size, he derived a formula for the shape of $ \Rect(T^{(k)}) $ for $ k \ge r - 1 $, <cit.>, and used it to show that any tableaux with $ r $ rows of the same size stabilizes at $ r $, <cit.>. He conjectured that the same bound still holds when the rows have weakly decreasing sizes but was only able to prove a bound of $ \max(1,2r - 2) $. The main purpose of this paper is to prove this conjecture.

For any standard skew tableaux $ T $ with $ r $ rows and weakly decreasing row sizes from top to bottom,

\[
\stab(T) \le r.
\]

The proof of the same-size-rows case of <Ref> in [1] relied on a formula for the shape of the stabilized tableaux. Unfortunately, an analogous formula for the general case would have to involve new terms not present in the previous shape formula, and we have not found such a formula.

Yet, we generalize the lattice path argument in the proof of Lemma 4.2 in [1] to prove <Ref>. Our argument relies on Greene's Theorem characterizing the shape of the insertion tableaux of words in terms of their increasing subsequences and a careful analysis of the increasing subsequences of reading words of $ T^{(k)} $ for standard skew tableaux $  T $.

In section 2, we show that the family of increasing sequences can be encoded by a family of lattice paths. In section 3, we go over various operations on a family of lattice paths that weakly increase the maximum combined length of corresponding increasing sequences. In section 4, we prove the main result using the tools developed in the previous sections.

§ LONGEST INCREASING SUBSEQUENCES

In this section we will go over Greene's theorem and set up the language of the matrix and lattice paths we will use. Before we introduce the essential tools, we will briefly explain why we need them.

Rectifying $T^{(k)}$ cannot be done one piece at a time. If one rectifies $T^{(k-1)}$ and then tries to attach another copy of $T$ and apply Jeu-da-taquin, the result need not be unique, unlike rectifying all at once. Figure <ref> demonstrates this. Hence we instead look at longest increasing sequences and Greene's theorem to analyze the shape of the rectification of $T^{(k)}$.

\begin{align*}
& \byt \none & \none & \none & 4 & 5 & 6 & *(orange) 11 & *(orange) 12 & *(orange) 13 \\ \none & \none & 3 & 7 & *(orange) 10 & *(orange) 14  \\ 1 & 2 & *(orange) 8 & *(orange)  9  \eyt  \to   \byt 1 & 2 & 3 & 4 & 5 & 6 & *(orange) 11 & *(orange) 12 & *(orange) 13 \\ 7 & \none & \none & \none & *(orange) 10 & *(orange) 14 \\ \none &  \none & *(orange) 8 & *(orange) 9 \, \eyt   \\
& \to \quad \byt 1 & 2 & 3 & 4 & 5 & 6 & *(orange) 11 & *(orange) 12 & *(orange) 13 \\ 7 & *(orange) 8 & *(orange) 9 & *(orange) 10 & *(orange) 14 \, \eyt \quad \tx{ or } \quad \byt 1 & 2 & 3 & 4 & 5 & 6 & *(orange) 11 & *(orange) 12 & *(orange) 13 \\ 7 & *(orange) 9 & *(orange) 10 & *(orange) 14 \\ *(orange) 8 \, \eyt
\end{align*}

If we only slide the white piece first, the orange piece could slide into two different positions depending on the order of the slides.

§.§ Greene's theorem

(Reading Word)
The reading word of a tableau is the word obtained by concatenating the rows from bottom to top. For a non-skew tableau $ T $, let $ \sh(T) $ denote its shape.

\[
T = \byt  \none & \none & 1 & 4 & 6 & 8 \\ \none & 3 & 5 & 9  \\ 2 & 7 \eyt
\imp
\Rect(T) = \byt 1 & 3 & 4 & 6 & 8 \\ 2 & 5 & 9 \\ 7 \eyt
\]

The reading word of $ T $ is $273591468$. The tableau to the right is its rectification, and $ \sh(\Rect(T)) = (5,3,1). $

(Greene's Theorem, [2])
Let $\pi$ be the reading word of a (skew) standard young tableau $T$ and let $\ell_k(\pi)$ denote the maximum combined length of $k$ disjoint increasing subsequences of $\pi$. Then,

\[
\ell_k(T) = \sh(\Rect(T))_1 + \cdots + \sh(\Rect(T))_k.
\]

Consider the tableau in Figure <ref>. A longest increasing sequence of its reading word $w = 273591468$ is exhibited by $23468$ or $23568$, which fits the fact that the first row has 5 boxes. Two disjoint increasing sequences with the longest combined length are $2359$ and $1468$, which again fits the fact that the combined number of boxes in the first and second row of $ \Rect(T) $  is 8. Note that neither $23468$ nor $23568$ can be reused to obtain two disjoint increasing subsequences of $w $ with total size 8. Finally, $ 27, 359, 1468 $ make 3 disjoint increasing subsequences comprising all of $ w $, so $ \Rect(T) $ has 3 rows.

§.§ Lattice paths

Suppose $T$ is a skew standard tableau with weakly decreasing row sizes from top to bottom. Let $ n $ denote the size of $ T $, and $r$ the number of rows of $ T $. For each positive integer $j$, let $T + (j - 1)n $ be obtained from $T$ by shifting the entries up by $(j - 1)n $. We define $T^{(q)}$ to be obtained by concatenating $ T, T + n,\ldots,T + (q - 1)n $ together from left to right.

For each positive integer $q$, we create an $r$-by-$q$ matrix $M = M(q,T)$ from $T$: each entry $M_{i,j}$ is a word set as the $(r-j+1)$-th row of $T$, with all entries shifted up by $(n-1)i$.

We will label coordinates Cartesian-style rather than matrix-style since that is more natural for lattice paths. Let $M_{i,j}$, the $(i,j)$-entry of the matrix $M$, denote the entry at the $i$-th column from the left and $j$-th row from the bottom.

With $ T $ as in <Ref>, we have

\[
M(3,T) = \begin{matrix} \color{black}{1468} & \color{orange}{1468} & \color{cyan}{1468} \\ \color{black}{359} & \color{orange}{359} & \color{cyan}{359} \\ \color{black}{27} & \color{orange}{27} & \color{cyan}{27} \end{matrix}
\]

The orange and cyan colors indicate that the entries are shifted up by $9$ and $18$ respectively. So $\color{orange}{3}$ is actually $3+9 = 12$ whereas $\color{cyan}{3}$ is actually $3+18 = 21$. We have $M_{1,1} = 27$ and $M_{3,2} = \color{cyan}{359}$.

For any sequences $ A, B $, let $ A \subseq B $ denote that $ A $ is a subsequence of $ B $. For a sequence $ A $ and a set $I$ we use $A \mid_I$ to denote the restriction of $A$ to $I$. For example, if $ A = 7164532 $, then

\[
A \mid_{ \{ 1, 2, 3, 4 \} } = 1432 \subseq S.
\]

The words in column $ j $ of $M$ use the letters $I_j \coloneqq \{(j-1)n+1,\ldots,jn\}$. Hence any entry used in column $ j $ of $M$ is bigger than any entry used in the previous columns.

A lattice path within $M$ is a sequence of entries of $M$ that move adjacently right or up at each step. Given a lattice path $S$, we use $S|_{i,*}$ to denote the subpath of $S$ by restricting ourselves to column $i$ of $M$. Similarly we use $S|_{*,j}$ to denote the subpath of $S$ by restricting ourselves to row $ j $ of $M$.

For possibly overlapping words $ A_1, \dots, A_k $, let

\begin{align*}
\ell(A_1, \dots, A_k) = & \tx{ the maximum combined length of disjoint} \\
& \tx{ increasing subsequences of } A_1, \dots, A_k \tx{ respectively}.
\end{align*}

We say that a collection of disjoint increasing sequences $S_1 \subseq A_1,\ldots,S_k \subseq A_k$ exhibits $\ell(A_1,\ldots,A_k)$ if $|S_1|+\cdots+|S_k|=\ell(A_1,\ldots,A_k)$.

For example, $ \ell(152643,13497) = 6 $ is exhibited by the pairs $(26, 1347) $ or $( 56, 1349 )$. Any letter, like  $ 1 $ in particular, cannot be used by both subsequences since the subsequences have to be disjoint.

Here we show why we are investigating lattice paths within matrix $M$.

Any increasing subsequence of the reading word of $T^{(k)}$ is a subsequence of a lattice path within $M$.

Each increasing subsequence of the reading word of $T^{(k)}$ cannot go downward in $ M $ because that is going backward in reading order of $ T^{(k)} $. It also cannot go left in $ M $ because any entry used in column $ j $ of $M$ is bigger than any entry used in column $ (j - 1) $ of $ M $, <Ref>. Therefore any increasing subsequence of the reading word of $T^{(k)}$ goes only right and up in $ M $ and is thus a subsequence of a lattice path.

\[
T = \byt  1 & 2 & 5 & 8 \\3 & 6 & 9  \\ 4& 7 \eyt
\]

With $ T $ as in <Ref>, we have

\[
\Rect(T^{(3)}) = \byt 1 & 3 & 4 & 6 & 8 & *(orange) 10 & *(orange) 13  & *(orange) 15 & *(orange) 17 & *(cyan) 19 & *(cyan) 22 & *(cyan) 24 & *(cyan) 26 \\ 2 & 5 & 9 & *(orange) 12 & *(orange) 14 & *(orange) 18 & *(cyan) 21 & *(cyan) 23 & *(cyan) 27 \\ 7 & *(orange) 11 & *(orange) 16 & *(cyan) 20 & *(cyan) 25 \eyt
\]

with shape $ \lam = (13, 9, 5) $ and

\[
M(3,T) = \begin{matrix} \color{black}{1468} & \color{orange}{1468} & \color{cyan}{1468} \\ \color{black}{359} & \color{orange}{359} & \color{cyan}{359} \\ \color{black}{27} & \color{orange}{27} & \color{cyan}{27} \end{matrix} \, .
\]

A longest increasing subsequence of $ M(3,T) $ is $ 23568\color{orange}{1468} \color{cyan}{1468} $, which has size 13 and is a subsequence of the lattice path in <Ref>.

\[
\begin{tikzpicture}
\draw (0,0) -- (0,2) -- (2,2);
\draw [fill = black] (0,0) circle (0.050);
\draw [fill = black] (0,1) circle (0.050);
\draw [fill = black] (0,2) circle (0.050);
\draw [fill = black] (1,0) circle (0.050);
\draw [fill = black] (1,1) circle (0.050);
\draw [fill = black] (1,2) circle (0.050);
\draw [fill = black] (2,0) circle (0.050);
\draw [fill = black] (2,1) circle (0.050);
\draw [fill = black] (2,2) circle (0.050);
\end{tikzpicture}
\]

The lattice path 27359146814681468  containing $ 23568\color{orange}{1468} \color{cyan}{1468} $.

Note this agrees with Greene's Theorem since $ \sh(\Rect(T))_1 = 13 $. Moreover, two disjoint increasing subsequences of $ M(3,T) $ with the longest combined length are $ 1468\color{orange}{1468} \color{cyan}{1468} $ and $ 2359\color{orange}{359} \color{cyan}{359} $, have total size 22 and are subsequences of the lattice paths in <Ref>.

\[
\begin{tikzpicture}
\draw (0,2) -- (2,2);
\draw (0,0) -- (0,1) -- (2,1);
\draw [fill = black] (0,0) circle (0.050);
\draw [fill = black] (0,1) circle (0.050);
\draw [fill = black] (0,2) circle (0.050);
\draw [fill = black] (1,0) circle (0.050);
\draw [fill = black] (1,1) circle (0.050);
\draw [fill = black] (1,2) circle (0.050);
\draw [fill = black] (2,0) circle (0.050);
\draw [fill = black] (2,1) circle (0.050);
\draw [fill = black] (2,2) circle (0.050);
\end{tikzpicture}
\]

The lattice paths containing $ 1468\color{orange}{1468} \color{cyan}{1468} $ and $ 2359\color{orange}{359} \color{cyan}{359} $.

Again, this agrees with Greene's Theorem since $ \lam_1 + \lam_2 = 13 + 9 = 22 $. Finally, three disjoint increasing subsequences of $ M(3,T) $ with the longest combined length are $ 1468\color{orange}{1468} \color{cyan}{1468}, \color{black}{359}\color{orange}{359} \color{cyan}{359}, $ and $ 27\color{orange}{27} \color{cyan}{27} $, which have total size 27 and are subsequences of the lattice paths in <Ref>.

\[
\begin{tikzpicture}
\draw (0,2) -- (2,2);
\draw (0,1) -- (2,1);
\draw (0,0) -- (2,0);
\draw [fill = black] (0,0) circle (0.050);
\draw [fill = black] (0,1) circle (0.050);
\draw [fill = black] (0,2) circle (0.050);
\draw [fill = black] (1,0) circle (0.050);
\draw [fill = black] (1,1) circle (0.050);
\draw [fill = black] (1,2) circle (0.050);
\draw [fill = black] (2,0) circle (0.050);
\draw [fill = black] (2,1) circle (0.050);
\draw [fill = black] (2,2) circle (0.050);
\end{tikzpicture}
\]

The lattice paths containing $ 1468\color{orange}{1468} \color{cyan}{1468}, \color{black}{359}\color{orange}{359} \color{cyan}{359}, $ and $ 27\color{orange}{27} \color{cyan}{27} $.

Again, this agrees with Greene's Theorem since $ \lam_1 + \lam_2 + \lam_3 = 13 + 9 + 5 = 27 $.

We will often identify lattice paths with the concatenated sequence of entries in $ M $ they represent, which we already have in <Ref> and <Ref>. What we are really interested in is the increasing subsequences they contain. By <Ref>, we can view any $ k $ disjoint increasing subsequences of the reading word of $ T^{(q)} $ as contained within a family of $ k $ lattice paths. And for a family $ P_1, \dots, P_k $ of lattice paths, we let $ \ell(P_1, \dots, P_k) $ denote the maximum combined length of disjoint increasing subsequences of $ P_1, \dots, P_k $, respectively, as in <Ref>.

§.§ Splitting words
In this subsection,
we show that we can attack each column of a family of lattice paths separately. We also prove a property of shuffling two increasing sequences that will be used as a key tool in the following section.

(Column Splitting) For any lattice paths $P_1,\dots,P_k$, we have

\[
\ell(P_1,\ldots,P_k) = \sum_{j = 1}^q \ell(P_1 \mid_{j,*},\ldots,P_k \mid_{j,*}).
%   \ell(S_1,\ldots,S_m) = \sum_{j = 1}^k \ell(S_1 \mid_{I_j},\ldots,S_m \mid_{I_j}).
\]

Since any element of column $ j $ is larger than any element of column ${j-1}$ for all $ j $, the increasing subsequences of each path can be picked independently column by column.

Hence when we are analyzing a family of lattice paths and its length $\ell(S_1,\ldots,S_m)$, we are allowed to study each column separately.

A splitting point of a word $ w = w_1 \dots w_n $ is an index $ k $ where

\[
w_i < w_j \quad \text{ for all } i \leq k < j.
\]

Suppose $ w $ is a word that is a shuffle of two increasing sequences, where one of these subsequences includes both the initial and final letters. Then $ w $ has a splitting point.

Without loss of generality, we may standardize $w = w_1 \dots w_n $ so it uses $ [n] $. By assumption, $ w $ is a shuffle of two increasing subsequences, $ A $ and $ B $, where $ A $ includes $ w_1 $ and $ w_n $. We wish to show that $w$ has a splitting point.

If $w_n=n$, then $n-1$ is a splitting point. Thus we may assume that $w_n < n$, which implies $ \max(A) = w_n < n $, so $ n \in B$.

For an index $i$, we say $ i $ is $A$-winning if $\max(w_1, w_2, \dots, w_i) \in A$ and $B$-winning otherwise. We have that $1$ is $A$-winning because $ w_1 \in A $, and $n$ is $B$-winning since $n \in B$.

Thus, there exists a  smallest positive integer $ k $ such that $k$ is B-winning. Since $k \geq 2$, $k-1$ must be A-winning. It follows that $w_k \in B$ and $ w_k = \max(w_1, \dots, w_k) $.

We claim that $k-1$ is a splitting point of $w$. We need to show that for all $i \leq k-1 < j $, we have $ w_i < w_j$. Let $i$ and $j$ be positive integers such that $i \leq k-1 < j$. If $ w_j \in A $, we have $ m = \max(w_1, w_2, \dots, w_{k-1}) \in A $ since $ k - 1 $ is $ A $-winning. Then from the fact that $A$ is increasing we deduce that $ w_i \le m < w_j $. If $ w_j \in B $, we have $w_i < \max(w_1, \dots, w_k) = w_k \leq w_j$ as $ w_k \in B $ and $ B $ is increasing. So $k-1$ is a splitting point, as desired.

For example, the word $ w = 231547968 $, which is a shuffle of $ 23568 $ and $ 1479 $, has a splitting point at $ 5 $ since $ 2, 3, 1, 5, 4 < 7, 9, 6, 8 $.

§ LATTICE PATH TOOLS

In this section we will introduce various tools we will need for the proof of our main result and prove them. Given a family of paths, we will show several operations that modify those paths while weakly increasing the maximum combined length of the longest sequences they contain.

The first tool, top-down switching, will allow us to modify the paths so that they do not cross (intersections can happen, but they will be non-transversal), and thus can be ordered in a top-down fashion. The second tool, left-shifting, will allow us to shift some vertical segments of a path to the left as long as no new intersections appear.  The last two tools, rectangular and reverse rectangular flip, will allow us to split paths with shared horizontal segments, while maintaining a top-down order.

[scale = 0.6]
(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[blue,thick](1a) – (2a);
[blue,thick](2a) – (3a);
[blue,thick](3a) – (3b);
[blue,thick](3b) – (4b);
[blue,thick](4b) – (4c);
[blue,thick](4c) – (5c);
[blue,thick](5c) – (6c);
[blue,thick](6c) – (7c);
[blue,thick](7c) – (7d);
[blue,thick](7d) – (7e);
[blue,thick](7e) – (7f);
[blue,thick](7f) – (7g);
[blue,thick](8g) – (7g);
[blue,thick](8g) – (9g);
[blue,thick](9g) – (9h);
[blue,thick](9i) – (9j);
[blue,thick](9h) – (9i);
[blue,thick](9j) – (10j);

[red,thick](1a) – (2a);
[red,thick](2a) – (3a);
[red,thick](3a) – (3b);
[red,thick](3b) – (4b);
[red,thick](4b) – (5b);
[red,thick](5b) – (5c);
[red,thick](5c) – (6c);
[red,thick](6c) – (6d);
[red,thick](6d) – (6e);
[red,thick](6e) – (6f);
[red,thick](6f) – (6g);
[red,thick](6g) – (7g);
[red,thick](7g) – (7h);
[red,thick](7h) – (7i);
[red,thick](8i) – (7i);
[red,thick](8i) – (8j);
[red,thick](8j) – (9j);
[red,thick](10j) – (9j);

[green,thick](1a) – (1b);
[green,thick](1b) – (1c);
[green,thick](1c) – (2c);
[green,thick](2c) – (2d);
[green,thick](2d) – (3d);
[green,thick](3d) – (3e);
[green,thick](3e) – (4e);
[green,thick](4e) – (5e);
[green,thick](5e) – (5f);
[green,thick](5f) – (5g);
[green,thick](5g) – (5h);
[green,thick](5h) – (6h);
[green,thick](6h) – (6i);
[green,thick](6i) – (6j);
[green,thick](6j) – (7j);
[green,thick](7j) – (8j);
[green,thick](8j) – (9j);
[green,thick](9j) – (10j);

§.§ Top-Down Switching

Consider two lattice paths $ P $(blue) and $ Q $(red) within the matrix $ M $ that cross in a way that they switch from $ Q $ being on top to $ P $ being on top, as in the left figure of Figure <ref>.

[Crossing paths.]

[scale = 1.2]
(-1) at (0,0) ;
(0) at (0,1) ;
(1) at (1, 1) ;
(1') at (1,2) ;
(2) at (1,3) ;
(3) at ( 2,3 ) ;
(4) at ( 1.05,0 ) ;
(5) at ( 1.05,1 ) ;
(6) at ( 1.05,2 ) ;
(7) at ( 1.05,3 ) ;
(8) at ( 1.05,4 ) ;
(9) at (2,4);

at (-0.3,0) $ P $;
at (-0.3,1) $ Q $;

at (2.3,3) $ Q $;
at (2.3,4) $ P $;

[red,thick](0) – (1) node   ;
[red,thick](2) – (3) node   ;
[red,thick](1) – (1') node   ;
[red,thick](1') – (2) node   ;
[blue,thick](-1) – (4) node ;
[blue,thick](4) – (5) node  ;
[blue,thick](5) – (6) node  ;
[blue,thick](6) – (7) node  ;
[blue,thick](7) – (8) node  ;
[blue,thick](8) – (9) node ;

[After switching.]

[scale = 1.2]

(-1) at (0,0) ;
(0) at (0,1) ;
(1) at (1, 1) ;
(1') at (1,2) ;
(2) at (1,3) ;
(3) at ( 2,3 ) ;
(4) at ( 1.05,0 ) ;
(5) at ( 1.05,1 ) ;
(6) at ( 1.05,2 ) ;
(7) at ( 1.05,3 ) ;
(8) at ( 1,3 ) ;
(9) at ( 1,4 ) ;
(10) at ( 2,4 ) ;

at (-0.3,0) $ P' $;
at (-0.3,1) $ Q' $;

at (2.3,3) $ P' $;
at (2.3,4) $ Q' $;

[red,thick](0) – (1) node   ;
[blue,thick](7) – (3) node   ;
[red,thick](1) – (1') node   ;
[red,thick](1') – (2) node   ;
[red,thick](9) – (10) node   ;

[blue,thick](-1) – (4) node  ;
[blue,thick](4) – (5) node  ;
[blue,thick](5) – (6) node  ;
[blue,thick](6) – (7) node  ;
[red,thick](8) – (9) node  ;

The top-down switching process.

Consider the result of switching the labels on the paths after $ P $ and $ Q $ diverge, giving new paths $ P' $ (blue) and $ Q' $ (red) as shown in the right figure of Figure <ref>. After using top-down switching, we have a clear upper and lower path. Our goal in this subsection is to show that this operation weakly increases the maximum combined length of increasing subsequences they contain.

For any words $ A, B, C, D_1, \dots, D_m $,

\[
\ell(ABC,B,D_1, \dots, D_m) \leq \ell(AB,BC,D_1, \dots, D_m).
\]

Let $S_{ABC},S_{B},\ldots$ be a list of sequences that exhibits $l(ABC,B,D_1,\ldots,D_m)$. We will modify $S_{ABC}$ and $S_{B}$ while preserving their union, into disjoint increasing subsequences of $AB$ and $BC$ respectively, making the remaining disjoint increasing subsequences irrelevant. To do this, consider $S = S_{ABC} \sqcup S_B $ listed in the same order they appear in $ ABC $ so that $ S \subseq ABC $.

If $S_{ABC}$ has no elements from $A$ or no elements from $C$, we can assign $ S_{ABC} $ as a subsequence of $ AB $ or $ BC $, and then $ S_B $ as a subsequence of the other. Otherwise, $ S _{ABC} $ has an element form $ A $ and an element from $C $, so $ S_{ABC} $ contains the first and last elements of $ S $. As $ S $ is a shuffle of $ S_{ABC} $ and $ S_B $, $ S $ has a splitting point by Lemma <ref>. If $ S_{ABC} $ contains the maximum element of $ B $ in $ S $, then we can put the splitting point right after $ B $. Else, by Lemma <ref>, there exists a splitting point where the sequence first switches from $ S_{ABC} $-winning to $ S_{B} $-winning, which is right before some element of $ B $.

Next, we can partition $S_{ABC}$ as

\[
S_{ABC} = S_{ABC}^{1} S_{ABC}^2
\]

where $ S_{ABC}^{1} $ is the subsequence of $ S_{ABC} $ before the splitting point, and $ S_{ABC}^{2} $ is the subsequence after the splitting point. Similarly, split $ S_B $ into

\[
S_B = S_B^1 S_B^2
\]

by splitting at the splitting point. Now create the sequences

\begin{align*}
S_{AB} = S_{ABC}^{1} S_B^2 \subseq AB, \\
S_{BC} = S_{B}^{1} S_{ABC}^2 \subseq BC.
\end{align*}

These are subsequences of $ AB, BC $ respectively because our splitting point was either at the end of $ B $ or just before some element of $ B $. Furthermore, $ S_{AB}$ and $S_{BC}$ are increasing because every element left of the the splitting point is less than every element right of the splitting point.

Hence we have successfully modified $S_{ABC}$ and $S_{B}$ into $S_{AB} \subseq AB $ and $S_{BC} \subseq BC$ while maintaining the union, which proves <Ref>.

Let $ A = 13 , B = 52947, C = 68 $. Then, $ \ell(ABC,B) = 8 $ is exhibited by

\[
S_{ABC} = 13568, \qquad S_B = 247.
\]

Viewing their union as a subsequence of $ ABC $ gives $ S = 13524768 $. Then, since $ S $ has a splitting point at 5, just after the 4, we split them into

\begin{align*}
S_{ABC}^1 & = 135, \qquad S_{ABC}^{2} = 68, \\
S_B^1 & = 24, \qquad S_B^2 = 7
\end{align*}

and then recombine them into

\begin{align*}
S_{AB} = S_{ABC}^1 S_B^2 = 1357 \subseq AB, \\
S_{BC} = S_B^1 S_{ABC}^2 = 2468 \subseq BC.
\end{align*}

This shows $ \ell(AB,BC) \ge 8 = \ell(ABC,B) $.

(Top-Down Switching)
Suppose $ P, Q $ are lattice paths, and there exists a column $ j $ where $ P $ begins weakly lower in column $ j $ than $ Q $ but $ P $ ends weakly higher in column $ j $ than $ Q $. Then, performing the top-down swap as in <Ref>,

\[
\ell(P_1, \dots, P_k, P,Q) \le \ell(P_1, \dots, P_k, P',Q').
\]

for any lattice paths $ P_1, \dots,P_k $.

By the Column Splitting lemma (Lemma <ref>), we only need to compare the lengths in the column $ j $ where $ P $ and $ Q $ intersect since in every other column, we are measuring the maximum combined lengths of disjoint increasing subsequences of exactly the same subsequences. Using the labels in

* $ A $ is the sequence in column $ j $ strictly below the intersection,

* $ B $ is the sequence in column $ j $ contained in the intersection of $ P $ and $ Q $,

* $ C $ is the sequence in column $ j $ strictly above the intersection,

* $ D_1, \dots, D_m $ are the sequences in the non-intersecting columns that are common to both families of paths,

[scale = 1.2]
(-1) at (0,0) ;
(0) at (0,1) ;
(1) at (1, 1) ;
(1') at (1,2) ;
(2) at (1,3) ;
(3) at ( 2,3 ) ;
(4) at ( 1.05,0 ) ;
(5) at ( 1.05,1 ) ;
(6) at ( 1.05,2 ) ;
(7) at ( 1.05,3 ) ;
(8) at ( 1.05,4 ) ;
(9) at (2,4);

at (-0.3,0) $ P $;
at (-0.3,1) $ Q $;

at (0.8,0.5) $ A $;
at (0.8,2) $ B $;
at (0.8,3.5) $ C $;

at (2.3,3) $ Q $;
at (2.3,4) $ P $;

[red,thick](0) – (1) node   ;
[red,thick](2) – (3) node   ;
[red,thick](1) – (1') node   ;
[red,thick](1') – (2) node   ;
[blue,thick](-1) – (4) node ;
[blue,thick](4) – (5) node  ;
[blue,thick](5) – (6) node  ;
[blue,thick](6) – (7) node  ;
[blue,thick](7) – (8) node  ;
[blue,thick](8) – (9) node ;

[scale = 1.2]

(-1) at (0,0) ;
(0) at (0,1) ;
(1) at (1, 1) ;
(1') at (1,2) ;
(2) at (1,3) ;
(3) at ( 2,3 ) ;
(4) at ( 1.05,0 ) ;
(5) at ( 1.05,1 ) ;
(6) at ( 1.05,2 ) ;
(7) at ( 1.05,3 ) ;
(8) at ( 1,3 ) ;
(9) at ( 1,4 ) ;
(10) at ( 2,4 ) ;

at (-0.3,0) $ P' $;
at (-0.3,1) $ Q' $;

at (0.8,0.5) $ A $;
at (0.8,2) $ B $;
at (0.8,3.5) $ C $;

at (2.3,3) $ P' $;
at (2.3,4) $ Q' $;

[red,thick](0) – (1) node   ;
[blue,thick](7) – (3) node   ;
[red,thick](1) – (1') node   ;
[red,thick](1') – (2) node   ;
[red,thick](9) – (10) node   ;

[blue,thick](-1) – (4) node  ;
[blue,thick](4) – (5) node  ;
[blue,thick](5) – (6) node  ;
[blue,thick](6) – (7) node  ;
[red,thick](8) – (9) node  ;

Labels on the top-down switching paths

we have

\begin{align*}
\ell(P_1, \dots, P_k, P,Q) & = \ell(ABC,B,D_1, \dots, D_m)
\end{align*}

before the top-down switch and

\begin{align*}
\ell(P_1, \dots, P_k, P',Q') = \ell(AB,BC,D_1, \dots, D_m)
\end{align*}

after the top-down switch. The fact that the remaining portions of $ P $ and $ Q $ after column $ j $ switch in $ P' $ and $ Q' $ is irrelevant by Column Splitting. Thus,

\begin{align*}
\ell(P_1, \dots, P_k, P,Q) & = \ell(ABC,B,D_1, \dots, D_m) \\
& \leq \ell(AB,BC,D_1, \dots, D_m) \qquad \tx{ by \Cref{lem:LIS1} }  \\
& = \ell(P_1, \dots, P_k, P',Q').
\end{align*}

An example of top-down switching is given in Figure <ref>. Each application of top-down switching eliminates a transverse crossing from our set of paths. Thus, after applying top-down switching as many times as possible in any order, there are no longer any transverse crossings in the resulting family of paths. Then we can order the family of paths from top to bottom. Hence, top-down switching lets us adjust the paths so they come in a top-down order $ P_1, \dots, P_k $ where $ P_i $ lies weakly above $ P_{i + 1} $ for all $ i $.

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1a) – (1b);
[green,thick](1c) – (1b);
[green,thick](1c) – (4c);
[green,thick](4c) – (4d);
[green,thick](4d) – (6d);
[green,thick](6d) – (6f);
[green,thick](6f) – (9f);
[green,thick](9f) – (9g);
[green,thick](9g) – (10g);
[green,thick](10g) – (10j);

[red,thick](1a) – (4a);
[red,thick](4a) – (4d);
[red,thick](5d) – (4d);
[red,thick](5d) – (5g);
[red,thick](5g) – (9g);
[red,thick](9g) – (9j);
[red,thick](9j) – (10j);

[blue,thick](1b) – (2b);
[blue,thick](2b) – (3b);
[blue,thick](3b) – (3e);
[blue,thick](3e) – (7e);
[blue,thick](7e) – (7f);
[blue,thick](7f) – (8f);
[blue,thick](8f) – (8i);
[blue,thick](8i) – (8j);
[blue,thick](8j) – (10j);

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1a) – (1b);
[green,thick](1c) – (1b);
[green,thick](1c) – (3c);
[green,thick](3c) – (3e);
[green,thick](3e) – (5e);
[green,thick](5e) – (5g);
[green,thick](5g) – (8g);
[green,thick](8g) – (8j);
[green,thick](8j) – (10j);

[red,thick](1a) – (4a);
[red,thick](4a) – (4d);
[red,thick](6d) – (4d);
[red,thick](6d) – (6e);
[red,thick](6e) – (7e);
[red,thick](7e) – (7f);
[red,thick](7f) – (9f);
[red,thick](9f) – (9g);
[red,thick](9g) – (10g);
[red,thick](10j) – (10g);

[blue,thick](1a) – (1b);
[blue,thick](1b) – (2b);
[blue,thick](2b) – (3b);
[blue,thick](3b) – (3c);
[blue,thick](3c) – (4c);
[blue,thick](4d) – (5d);
[blue,thick](4d) – (4c);
[blue,thick](5d) – (5e);
[blue,thick](5e) – (6e);
[blue,thick](6f) – (6e);
[blue,thick](6f) – (8f);
[blue,thick](8f) – (8f);
[blue,thick](8f) – (8g);
[blue,thick](8g) – (9g);
[blue,thick](9g) – (9j);
[blue,thick](9j) – (10j);

After applying Top-Down Switching, we can label the newly ordered paths $P_1,P_2,P_3$ from top to bottom, in a way that a path $P_i$ always stays weakly above $P_{i+1}$.

§.§ Left-shifting

A left-shift of a lattice path is an operation where part of the column of a path, following a horizontal segment of length at least two, is shifted one column to the left and creates no new intersections, as in Figure <ref>.

[scale = 1.2]
(-1) at (-1,0) ;
(0) at (0,0) ;
(1) at (1, 0) ;
(2) at (1,3) ;

(-1') at (3,0) ;
(0') at (4,0) ;
(1') at (4, 1.5) ;
(2') at (5, 1.5) ;
(3') at (5, 3) ;

[red,thick](-1) – (0) node   ;
[red,thick](0) – (1) node   ;
[red,thick](1) – (2) node   ;

[red,thick](-1') – (0') node ;
[red,thick](0') – (1') node ;
[red,thick](1') – (2') node  ;
[red,thick](2') – (3') node  ;

[->] (1.5,1) – (2.5,1);

[fill = black] (0,0) circle (0.050);
[fill = black] (1,0) circle (0.050);
[fill = black] (4,0) circle (0.050);
[fill = black] (1,1.5) circle (0.050);
[fill = black] (4,1.5) circle (0.050);
[fill = black] (5,1.5) circle (0.050);

Left-shifting applied to a lattice path

We are introducing left-shifting because it again weakly increases the maximum combined length of increasing subsequences contained in the lattice paths.

Suppose $ P_1, \dots, P_k, P $ are a family of lattice paths where a left-shift can be applied to $ P $ in a way so that no new intersection is introduced. Letting $ Q $ denote this left-shift of $ P $, we have

\[
\ell(P_1, \dots, P_k, P) \le \ell(P_1, \dots, P_k, Q).
\]

Suppose $ \ell(P_1, \dots, P_k, P) $ is exhibited by $ S_1, \dots, S_k, S $. Now, we restrict our attention only to the column of $ P $ that was just shifted, say $ A $ is sequence of the bottom point in the shifted column, $ B $ is the sequence strictly between the boundary points of the shifted piece, $ C $ is the sequence at the top point of the shift, and $ D $ is the sequence strictly above the shift. Also, let $ A', B', C' $ denote $ A, B , C $ decremented by $ n $ component-wise, respectively. Because the row sizes of $ T $ weakly decrease from top to bottom, $ A, C $ are increasing sequences with $ \ell(C) \ge \ell(A) $. See <Ref>.

[scale = 1.2]
(-1) at (-1,0) ;
(0) at (0,0) ;
(1) at (1, 0) ;
(2) at (1,3) ;

(-1') at (3,0) ;
(0') at (4,0) ;
(1') at (4, 1.5) ;
(2') at (5, 1.5) ;
(3') at (5, 3) ;

[red,thick](-1) – (0) node   ;
[red,thick](0) – (1) node   ;
[red,thick](1) – (2) node   ;

[red,thick](-1') – (0') node ;
[red,thick](0') – (1') node ;
[red,thick](1') – (2') node  ;
[red,thick](2') – (3') node  ;

[->] (1.5,1) – (2.5,1);

at (1.25, 2.25) D;
at (5.25, 2.25) D;
at (1.25, 1.5) C;
at (5.25, 1.5) C;
at (3.75, 1.5) C';
at (1.25, 0.75) B;
at (4.25, 0.75) B';
at (1.25, 0) A;
at (4.25, 0) A';
at (0, -0.25) A';
at (-1.3, 0) P;
at (2.7, 0) Q;

[fill = black] (0,0) circle (0.050);
[fill = black] (1,0) circle (0.050);
[fill = black] (4,0) circle (0.050);
[fill = black] (1,1.5) circle (0.050);
[fill = black] (4,1.5) circle (0.050);
[fill = black] (5,1.5) circle (0.050);

Labeled sections on the lattice path

Let $ S \mid_{AB} = a_1 \dots a_r b_1 \dots b_s $ and $ S \mid_C = c_1 \dots c_t $. Without loss of generality, we may assume $ S $ contains $ A' $. If not, just add the rest of the elements of $ A' $, which preserves $ S $ being increasing as $ A' $ is alone its own column within $ P $. Then, to get an increasing sequence in $ Q $ of weakly longer length, first remove $ A' $. Next, shift the letters of $ S \mid_{AB} $ to letters of $ A'B' $ by subtracting $n$. For notational convenience, we let $ x' = x - n $. Then, between $ S \mid_{AB} - n $ and $ S \mid_{CD} $, insert $ x' (x' + 1) ... \max(C') \min(C) (\min(C) + 1)... (x - 1) $ where $ x $ is the minimum element of $ C $ greater than $ b_s $. Note that by construction $ b_s < x \le c_1 $ because $ b_s < c_1 $. If no such $ x $ exists, which is when $ b_s > \max(C) $, insert $ C $ instead. Either way, we are inserting an increasing sequence of size $ \ell(C) $. Thus,

\[
S = \dots A' \; a_1 \dots a_r b_1 ... b_s c_1 c_2 ... c_t y \dots
\]

\begin{align*}
R = \begin{cases} \dots a_1' \dots a_r' b_1' \dots b_s' x' ... \max(C') \min(C)... (x - 1) c_1 \dots c_t y \dots & \tx{ if } b_s < \max(C) \\
\dots a_1' \dots a_r' b_1' \dots b_s' C y \dots & \tx{ if } b_s > \max(C).
\end{cases}
\end{align*}

If $ b_s < \max(C) $, this sequence is increasing since $ b_s < x \le c_1 $. If $ b_s > \max(C) $, the sequence is still increasing since $ \max(C) < b_s < y $. Thus, we have found an increasing $ R \subseq Q $ with length

\[
\ell(R) = \ell(S) - \ell(A) + \ell(C) \ge \ell(S) \qquad \tx{ because } \ell(C) \ge \ell(A).
\]

Because the space we shifted $ P $ into was empty earlier, $ R $ is still disjoint from $ S_1, \dots, S_k $. Therefore,

\[
\ell(P_1, \dots, P_k, P) \le \ell(P_1, \dots, P_k, Q).
\]

An example of left-shifting is given in Figure <ref>. We are using left-shifting to modify the bottom path drawn in red. When we left-shift, we are not allowed to introduce a new intersection: hence the furthest we can shift a particular path to the left is bounded by other paths.

[scale = 0.5]
(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[black,thick] (1a) – (1b);
[black,thick] (1b) – (2b);
[black,thick] (2b) – (2d);
[black,thick] (2d) – (3d);
[black,thick] (3d) – (3e);
[black,thick] (3e) – (4e);
[black,thick] (4e) – (4f);
[black,thick] (4f) – (6f);

[red,thick] (1a) – (4a);
[red,thick] (4a) – (4c);
[red,thick] (4c) – (6c);
[red,thick] (6c) – (6f);

[red,dotted,thick] (3a) – (3c);
[red,dotted,thick] (3c) – (4c);

[scale = 0.5]
(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[black,thick] (1a) – (1b);
[black,thick] (1b) – (2b);
[black,thick] (2b) – (2d);
[black,thick] (2d) – (3d);
[black,thick] (3d) – (3e);
[black,thick] (3e) – (4e);
[black,thick] (4e) – (4f);
[black,thick] (4f) – (6f);

[red,thick] (1a) – (3a);
[red,thick] (3a) – (3c);
[red,thick] (3c) – (6c);
[red,thick] (6c) – (6f);

[red,dotted,thick] (4c) – (4d);
[red,dotted,thick] (4d) – (6d);

[scale = 0.5]
(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[black,thick] (1a) – (1b);
[black,thick] (1b) – (2b);
[black,thick] (2b) – (2d);
[black,thick] (2d) – (3d);
[black,thick] (3d) – (3e);
[black,thick] (3e) – (4e);
[black,thick] (4e) – (4f);
[black,thick] (4f) – (6f);

[red,thick] (1a) – (3a);
[red,thick] (3a) – (3c);
[red,thick] (3c) – (4c);
[red,thick] (4c) – (4d);
[red,thick] (4d) – (6d);
[red,thick] (6d) – (6f);

[red,dotted,thick] (5d) – (5e);
[red,dotted,thick] (5e) – (6e);

[scale = 0.5]
(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[black,thick] (1a) – (1b);
[black,thick] (1b) – (2b);
[black,thick] (2b) – (2d);
[black,thick] (2d) – (3d);
[black,thick] (3d) – (3e);
[black,thick] (3e) – (4e);
[black,thick] (4e) – (4f);
[black,thick] (4f) – (6f);

[red,thick] (1a) – (3a);
[red,thick] (3a) – (3c);
[red,thick] (3c) – (4c);
[red,thick] (4c) – (4d);
[red,thick] (4d) – (5d);
[red,thick] (6e) – (6f);

[red,thick] (5d) – (5e);
[red,thick] (5e) – (6e);

Three consecutive applications of left-shifting on the red path. The figure on the far right is the furthest left we can shift the red path.

[scale = 0.6]
(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[blue,thick](1a) – (2a);
[blue,thick](2a) – (3a);
[blue,thick](3a) – (3b);
[blue,thick](3b) – (4b);
[blue,thick](4b) – (5b);
[blue,thick](5b) – (5c);
[blue,thick](5c) – (6c);
[blue,thick](6c) – (7c);
[blue,thick](7c) – (7d);
[blue,thick](7d) – (7e);
[blue,thick](7e) – (7f);
[blue,thick](7f) – (7g);
[blue,thick](7g) – (8g);
[blue,thick](8g) – (9g);
[blue,thick](9g) – (10g);
[blue,thick](10g) – (10h);
[blue,thick](10h) – (10i);
[blue,thick](10i) – (10j);

[red,thick](1a) – (1b);
[red,thick](1b) – (2b);
[red,thick](2b) – (3b);
[red,thick](3b) – (4b);
[red,thick](4b) – (4c);
[red,thick](4c) – (5c);
[red,thick](5c) – (6c);
[red,thick](6c) – (6d);
[red,thick](6d) – (6e);
[red,thick](6e) – (6f);
[red,thick](6f) – (6g);
[red,thick](6g) – (7g);
[red,thick](7g) – (7h);
[red,thick](7h) – (7i);
[red,thick](8i) – (7i);
[red,thick](8i) – (9i);
[red,thick](9i) – (10i);
[red,thick](10j) – (10i);

[green,thick](1a) – (1b);
[green,thick](1b) – (1c);
[green,thick](1c) – (1d);
[green,thick](1d) – (2d);
[green,thick](2d) – (2e);
[green,thick](2e) – (2f);
[green,thick](2f) – (3f);
[green,thick](3f) – (3g);
[green,thick](3g) – (3h);
[green,thick](3h) – (4h);
[green,thick](4h) – (4i);
[green,thick](4i) – (5i);
[green,thick](5i) – (5j);
[green,thick](5j) – (6j);
[green,thick](6j) – (7j);
[green,thick](7j) – (8j);
[green,thick](8j) – (9j);
[green,thick](9j) – (10j);

[black,dashed](1a) – (1d);
[black,dashed](1d) – (2d);
[black,dashed](2d) – (2e);
[black,dashed](2e) – (3e);
[black,dashed](3e) – (3f);
[black,dashed](3f) – (4f);
[black,dashed](4f) – (4g);
[black,dashed](4g) – (5g);
[black,dashed](5g) – (5h);
[black,dashed](5h) – (6h);
[black,dashed](6h) – (6i);
[black,dashed](6i) – (7i);
[black,dashed](7i) – (7j);
[black,dashed](7j) – (10j);

§.§ Rectangular flip and reverse rectangular flip.

For any words $ B, C, D_1, \dots, D_m $ and an increasing sequence $A$,

\[
\ell(ABC,AB,D_1, \dots, D_m) \leq \ell(AB,BC,D_1, \dots, D_m).
\]

Let $S_{ABC},S_{AB},\ldots$ be a list of sequences that exhibits $\ell(ABC,AB,D_1, \dots, D_m)$. We will modify $ S_{ABC},S_{AB} $ into subsequences $  S_{ABC}' ,  S_{AB}' $ of $ ABC, B $ or $ AB, BC $, respectively, while maintaining their union, making the rest of subsequences irrelevant.

First, we partition $ S_{ABC} $ and $ S_{AB} $ into

\begin{align*}
S_{ABC} & = S_{ABC}^1 S_{ABC}^2, \\
S_{AB} & = S_{AB}^1 S_{AB}^2,
\end{align*}

\[
S_{ABC}^1 \subseq A, \quad S_{ABC}^2 \subseq BC, \quad S_{AB}^1 \subseq A, \quad S_{AB}^2 \subseq B.
\]

Let $S = S_{ABC}^1 \sqcup S_{AB}^1 $ listed in the same increasing order they appear in $ A $ so that $ S \subseq A $. Now, if $ \max(S_{ABC}^1) < \max(S_{AB}^1) $ or $ S_{ABC}^1 $ is empty, let

\begin{align*}
S_{ABC}' &= S_{ABC}^2 \; \subseq BC, \\
S_{AB}' & = S \; S_{AB}^2 \; \subseq AB,
\end{align*}

and, if $ \max(S_{AB}^1) < \max(S_{ABC}^1) $ or $ S_{AB}^1 $ is empty, let

\begin{align*}
S_{ABC}' &= S \; S_{ABC}^2 \; \subseq ABC, \\
S_{AB}' & = S_{AB}^2 \; \subseq B,
\end{align*}

which are all increasing subsequences. Therefore,

\begin{align*}
\ell(ABC,AB,D_1, \dots, D_m) & \le \max( \ell(AB,BC,D_1, \dots, D_m), \ell(ABC,B,D_1, \dots, D_m)) \\
& = \ell(AB,BC,D_1, \dots, D_m),
\end{align*}

by <Ref>.

We also have an analogous lemma where the proof is similar:

For any words $ A, B, D_1, \dots, D_m $ and an increasing sequence $C$,

\[
\ell(ABC,BC,D_1, \dots, D_m) \leq \ell(AB,BC,D_1, \dots, D_m).
\]

The key idea in the proof of Lemma <ref> was that we could move the elements of $A$ around, using the fact that $A$ is an increasing sequence, so that they are all contained in just one sequence instead of being located in both $S_{ABC}$ and $S_{AB}$. The proof of <Ref> works the same way as <Ref> except we split according to the subsequences's restriction to $ C $ instead of $ A $ and then move every element of $ C $ to $S_{ABC}$ if $ \min(S_{ABC} \mid_C) < \min(S_{BC} \mid_C) $ or $ S_{BC} \mid_{C} $ is empty and to $S_{BC}$ otherwise.

[Rectangular flip]
Suppose that the pair of paths $P,Q$ share the horizontal segment from $ (a,i) $ to $ (b, i) $. Suppose $ P $ continues to $(b,i+1)$ in the matrix and lies weakly above $ Q $. Then we may modify $ P $ to $ P' $ so that instead it goes from $(a,i)$ to $(a,i+1)$ to $(b,i+1)$, and then

\[
\ell(P_1, \dots, P_k, P, Q) \le  \ell(P_1, \dots, P_k, P', Q).
\]

for any lattice paths $ P_1, \dots, P_k $.

Let $ (R, S, \ldots) $ be disjoint increasing subsequences of $ P, Q, \ldots $ which exhibit the maximum possible length. Restricting to column $ b $ in both paths, let $ A = M_{b,i} $, $ B $ denote the portion of the column $ b $ where $ P $ and $ Q $ overlap, and $ C $ denote the portion of column $ b $ that only $ P $ contains. Note that $ B, C $ may be empty. Then, because $ A $ is increasing, we have

\[
\ell(ABC, AB, \dots) \le \ell(BC, AB, \dots)
\]

by <Ref> with $ ABC \subseq P $ and $ AB \subseq Q $. This means that we can assume without loss of generality that $ R \subseq P $ contains no elements from $ A = M_{b,i} $. Furthermore, since $ M_{a + 1,i} \ldots M_{b - 1,i} $ is increasing, we may move any element in $ R \mid _{M_{a+1,i},\ldots,M_{b - 1,i}} $ to sequence $ S $, without breaking that $ S $ is increasing. Together, we may assume without loss of generality that $ R $ uses none of the elements in $ M_{a + 1,i} \ldots M_{b,i} $. Hence, if we modify $ P $ to get $ P' $ by moving $ (a,i) - (b,i) - (b, i + 1) $ to $ (a,i) - (a,i + 1) - (b, i + 1) $ as in <Ref>, then $ P' $ still contains $ R $ as in <Ref>. Thus,

\[
\ell(P_1, \dots, P_k, P, Q) \le  \ell(P_1, \dots, P_k, P', Q).
\]

(1) at (-2,0) ;
(2) at (1,0) ;
(3) at (1,2) ;
(4) at (2,2) ;
(5) at (2,3) ;
(6) at (3,3) ;
(7) at (-2,-0.05) ;
(8) at (1.05,-0.05) ;
(9) at (1.05,0.95) ;
(10) at (2.05,0.95);
(11) at (2.05,2.95);
(12) at (3,2.95);
[blue,thick](1) – (2);
[blue,thick](3) – (2);
[blue,thick](3) – (4);
[blue,thick](5) – (4);
[blue,thick](5) – (6);

at (-2.5,0) $(a, i)$;
at (1.5,0) $(b, i)$;
at (0.3,1.2) $(b, i + 1)$;

[fill = black] (1) circle (0.050);
[fill = black] (2) circle (0.050);
[fill = black] (1,1) circle (0.050);

[red,thick](8) – (9) ;
[red,thick](9) – (10) ;
[red,thick](7) – (8) ;
[red,thick](10) – (11) ;
[red,thick](12) – (11) ;
(1') at (5,0) ;
(2') at (5,1) ;
(25) at (8,1) ;
(3') at (8,2) ;
(4') at (9,2) ;
(5') at (9,3) ;
(6') at (10,3) ;
(7') at (5,-0.05) ;
(8') at (8.05,-0.05) ;
(9') at (8.05,0.95) ;
(10') at (9.05,0.95);
(11') at (9.05,2.95);
(12') at (10,2.95);
[blue,thick](1') – (2');
[blue,thick](25) – (2');
[blue,thick](25) – (3');
[blue,thick](3') – (4');
[blue,thick](5') – (4');
[blue,thick](5') – (6');

at (4.5,0) $(a, i)$;
at (8.5,0) $(b, i)$;
at (4.5,1.2) $(a, i + 1)$;
at (7.3,1.2) $(b, i + 1)$;

[fill = black] (1') circle (0.050);
[fill = black] (2') circle (0.050);
[fill = black] (8,0) circle (0.050);
[fill = black] (8,1) circle (0.050);

[red,thick](8') – (9') ;
[red,thick](9') – (10') ;
[red,thick](7') – (8') ;
[red,thick](10') – (11') ;
[red,thick](12') – (11') ;

A rectangular flip. Blue path: $ P \to P'$, Red path: $ Q $

An example of rectangular flip is given in Figure <ref>. Note that the red and blue paths in the left figure have a common horizontal segment at the start. After using the rectangular flip there, the blue path now is one height higher than its original position at the segment. An example of rectangular flip used in a family of paths is illustrated in Figure <ref>. Notice that in the left figure of Figure <ref>, the blue and red path share a horizontal segment at the beginning. After the usage of rectangular flip there, the red and blue paths do not share a horizontal segment there. Also after this operation, the green path passes $(1,3)$, the blue passes $(1,2)$ and the red passes $(1,1)$ which we will show in the next section is a property of at least one length-maximizing family of paths.

[scale = 0.6]
(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1a) – (1b);
[green,thick](1c) – (1b);
[green,thick](1c) – (4c);
[green,thick](4c) – (4d);
[green,thick](4d) – (6d);
[green,thick](6d) – (6f);
[green,thick](6f) – (9f);
[green,thick](9f) – (9g);
[green,thick](9g) – (10g);
[green,thick](10g) – (10j);

[red,thick](1a) – (4a);
[red,thick](4a) – (4d);
[red,thick](5d) – (4d);
[red,thick](5d) – (5g);
[red,thick](5g) – (9g);
[red,thick](9g) – (9j);
[red,thick](9j) – (10j);

[blue,thick](1a) – (2a);
[blue,thick](2a) – (2b);
[blue,thick](2b) – (3b);
[blue,thick](3b) – (3e);
[blue,thick](3e) – (7e);
[blue,thick](7e) – (7f);
[blue,thick](7f) – (8f);
[blue,thick](8f) – (8i);
[blue,thick](8i) – (8j);
[blue,thick](8j) – (10j);

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1a) – (1b);
[green,thick](1c) – (1b);
[green,thick](1c) – (4c);
[green,thick](4c) – (4d);
[green,thick](4d) – (6d);
[green,thick](6d) – (6f);
[green,thick](6f) – (9f);
[green,thick](9f) – (9g);
[green,thick](9g) – (10g);
[green,thick](10g) – (10j);

[red,thick](1a) – (4a);
[red,thick](4a) – (4d);
[red,thick](5d) – (4d);
[red,thick](5d) – (5g);
[red,thick](5g) – (9g);
[red,thick](9g) – (9j);
[red,thick](9j) – (10j);

[blue,thick](1b) – (2b);
[blue,thick](2b) – (3b);
[blue,thick](3b) – (3e);
[blue,thick](3e) – (7e);
[blue,thick](7e) – (7f);
[blue,thick](7f) – (8f);
[blue,thick](8f) – (8i);
[blue,thick](8i) – (8j);
[blue,thick](8j) – (10j);

An example of applying rectangular flip.

[Reverse rectangular flip]
Suppose that the pair of paths $P,Q$ share the horizontal segment from $ (a,i) $ to $ (b,i) $. Suppose $ P $ comes in via $(i-1,a)$ in the matrix and lies weakly below $ Q $. Then we may modify $ P $ to get $ P' $ that instead it goes from $(i-1,a)$ to $(i-1,b)$ to $(i,b)$, and then

\[
\ell(P_1, \dots, P_k, P, Q) \le \ell(P_1, \dots, P_k, P', Q).
\]

for any lattice paths $ P_1, \dots, P_k $.

Let $ (R, S, \ldots) $ be disjoint increasing subsequences of $ P, Q, \ldots $ which exhibit the maximum possible length. Restricting to column $a$ in both paths, let $ C = M_{i,a} $, $ B $ denote the portion of the column $a$ where $ P $ and $ Q $ overlap, and $ A $ denote the portion of column $a$ that only $P$ contains. Note that $ A,B $ may be empty. Then, because $C$ is increasing, we have

\[
\ell(ABC, BC, \dots) \le \ell(AB, BC, \dots)
\]

by <Ref> with $ ABC \subseq P $ and $ BC \subseq Q $. Then, just as in the proof of <Ref>, we can assume without loss of generality that $ P' $ still contains $ R $. Hence,

\[
\ell(P_1, \dots, P_k, P, Q) \le \ell(P_1, \dots, P_k, P', Q).
\]

(1) at (0,10) ;
(2) at (-3,10) ;
(3) at (-3,8) ;
(4) at (-4,8) ;
(5) at (-4,7) ;
(6) at (-5,7) ;
(7) at (0,10.05) ;
(8) at (-3.05,10.05) ;
(9) at (-3.05,9.05) ;
(10) at (-4.05,9.05);
(11) at (-4.05,7.05);
(12) at (-5,7.05);
[blue,thick](1) – (2);
[blue,thick](3) – (2);
[blue,thick](3) – (4);
[blue,thick](5) – (4);
[blue,thick](5) – (6);

at (-3.3,10.3) $(a,i)$;
at (-2.2,8.8) $(a,i -1)$;
at (0.3,10.3) $(b,i)$;

[fill = black] (1) circle (0.050);
[fill = black] (2) circle (0.050);
[fill = black] (-3,9) circle (0.050);

[red,thick](8) – (9) ;
[red,thick](9) – (10) ;
[red,thick](7) – (8) ;
[red,thick](10) – (11) ;
[red,thick](12) – (11) ;
(1') at (5,10) ;
(2') at (5,9) ;
(25) at (2,9) ;
(3') at (2,8) ;
(4') at (1,8) ;
(5') at (1,7) ;
(6') at (0,7) ;
(7') at (5,10.05) ;
(8') at (1.95,10.05) ;
(9') at (1.95,9.05) ;
(10') at (0.95,9.05);
(11') at (0.95,7.05);
(12') at (0,7.05);
[blue,thick](1') – (2');
[blue,thick](25) – (2');
[blue,thick](25) – (3');
[blue,thick](3') – (4');
[blue,thick](5') – (4');
[blue,thick](5') – (6');

at (1.7,10.3) $(a,i)$;
at (2.8,8.8) $(a, i - 1)$;
at (5.3,10.3) $(b,i)$;
at (5.3,8.8) $(b,i - 1)$;

[fill = black] (1') circle (0.050);
[fill = black] (2') circle (0.050);
[fill = black] (2,9) circle (0.050);
[fill = black] (2,10) circle (0.050);

[red,thick](8') – (9') ;
[red,thick](9') – (10') ;
[red,thick](7') – (8') ;
[red,thick](10') – (11') ;
[red,thick](12') – (11') ;

A reverse rectangular flip. Blue path: $ P \to P'$, Red path: $ Q $

An example of reverse rectangular flip is given in Figure <ref>. Initially, the red and blue paths in the left figure have a common horizontal segment at the end. After using the reverse rectangular flip there, the blue path now is one height lower than its original position at the segment. An example of rectangular flip used in a family of paths is illustrated in Figure <ref>. Notice that in the left figure of Figure <ref>, the green and blue path share a horizontal segment in the top row. After the usage of reverse rectangular flip there, the green and blue path does not share a horizontal segment there. Also after this operation, the green path has a horizontal segment $(9,10)-(10,10)$, the blue has a horizontal segment $(9,9)-(10,9)$ and the red has $(9,8)-(10,8)$ which we will show in the next section is a property of at least one length-maximizing family of paths.

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1c) – (1e);
[green,thick](1e) – (2e);
[green,thick](2e) – (2g);
[green,thick](2g) – (3g);
[green,thick](3g) – (3j);
[green,thick](3j) – (10j);

[red,thick](1a) – (2a);
[red,thick](2a) – (2b);
[red,thick](2b) – (3b);
[red,thick](3b) – (3c);
[red,thick](3c) – (4c);
[red,thick](4c) – (4d);
[red,thick](5d) – (4d);
[red,thick](5d) – (5e);
[red,thick](5e) – (6e);
[red,thick](6e) – (6f);
[red,thick](6f) – (7f);
[red,thick](7f) – (7g);
[red,thick](7g) – (8g);
[red,thick](8h) – (8g);
[red,thick](10h) – (8h);
[red,thick](10h) – (10j);

[blue,thick](1b) – (1c);
[blue,thick](1c) – (2c);
[blue,thick](2c) – (2d);
[blue,thick](2d) – (3d);
[blue,thick](3d) – (3e);
[blue,thick](3e) – (4e);
[blue,thick](4e) – (4f);
[blue,thick](5f) – (4f);
[blue,thick](5f) – (5g);
[blue,thick](5g) – (6g);
[blue,thick](6g) – (6i);
[blue,thick](6i) – (9i);
[blue,thick](9i) – (9j);
[blue,thick](9j) – (10j);

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1c) – (1e);
[green,thick](1e) – (2e);
[green,thick](2e) – (2g);
[green,thick](2g) – (3g);
[green,thick](3g) – (3j);
[green,thick](3j) – (10j);

[red,thick](1a) – (2a);
[red,thick](2a) – (2b);
[red,thick](2b) – (3b);
[red,thick](3b) – (3c);
[red,thick](3c) – (4c);
[red,thick](4c) – (4d);
[red,thick](5d) – (4d);
[red,thick](5d) – (5e);
[red,thick](5e) – (6e);
[red,thick](6e) – (6f);
[red,thick](6f) – (7f);
[red,thick](7f) – (7g);
[red,thick](7g) – (8g);
[red,thick](8h) – (8g);
[red,thick](10h) – (8h);
[red,thick](10h) – (10j);

[blue,thick](1b) – (1c);
[blue,thick](1c) – (2c);
[blue,thick](2c) – (2d);
[blue,thick](2d) – (3d);
[blue,thick](3d) – (3e);
[blue,thick](3e) – (4e);
[blue,thick](4e) – (4f);
[blue,thick](5f) – (4f);
[blue,thick](5f) – (5g);
[blue,thick](5g) – (6g);
[blue,thick](6g) – (6i);
[blue,thick](6i) – (9i);
[blue,thick](9i) – (10i);
[blue,thick](10i) – (10j);

An example of applying reverse rectangular flip.

§ THE MAIN RESULT

We have developed several tools regarding how the lattice paths encoding the longest sequences behave and how families of paths can be adjusted while weakly increasing the combined length they represent. Using these tools, we will be prove main result, <Ref> in this section.

There exists a family of $ k $ lattice paths $P_1,\ldots,P_k$ maximizing $ \ell(P_1, \dots, P_k) $ where for each $i$, the path $P_i$ starts at the point $(1,k+1-i)$ in the matrix.

Let $P_1,\ldots,P_k$ be a family of lattice paths maximizing $ \ell(P_1, \dots, P_k) $. Add an auxiliary column 0 all of whose entries are empty. Initially assume all paths start at (0,1) and go horizontally toward (1,1) without loss of generality. If not, extend them so they do. Order the paths based on their highest point in the first column, and label them $P_1,\ldots,P_k$ from top to bottom. We will perform rectangular flips to separate the starts of the paths.

For $ j = 0, 1, \dots, (k - 1) $, say the paths $ P_1, \dots, P_k $ are in position $ j $ if paths $ P_1, \dots, P_{k - j} $ go from $ (0,1) $ to $ (0,j + 1) $ to $ (1, j + 1) $, and for each $ i \ge k - j $, $ P_i $ goess from $ (0,1) $ to $ (0, k - i  + 1) $ to $ (1, k - i + 1) $. Initially, the paths start in position 0.

If the paths are in position $ j $, we will fix $ P_{k - j} $ and rectangular flip each of $ P_1, \dots, P_{k - j - 1} $ out of the horizontal segment from $(0, j + 1)$ to $ (1, j + 1) $, which is already used by $ P_{k - j}$. After these rectangular flips, $ P_1, \dots, P_{k - j - 1} $ travel from $(0,0)$ to $ (0,k - j + 2) $ to $ (1,k - j + 2) $. Now our paths are in position $ j + 1 $.

Thus, we can inductively use rectangular flips to put the paths in position $ k - 1 $, where $ P_i $ travels from $ (0,1) $ to $ (0, k - i + 1) $ to $ (1, k - i + 1) $ for all $ i \ge 1 $. But column 0 is an auxiliary column that doesn't contain any letters to use, so we can remove it. When we remove column 0, the path $P_i$ starts at $(1,k - i + 1)$ for all $ i \ge 1 $, as desired.

Hence we may assume that each path $P_i$ starts at the point $(1,k - i + 1)$. Beware that this does not imply that each $P_i$ has the horizontal segment $(1,k - i + 1)-(2,k - i + 1)$, as can be seen from Figure <ref>.

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;
[blue,thick](1a) – (2a);
[blue,thick](2a) – (3a);
[blue,thick](3a) – (3b);
[blue,thick](3b) – (4b);
[blue,thick](4b) – (4c);
[blue,thick](4c) – (5c);
[blue,thick](5c) – (5d);
[blue,thick](5d) – (5e);
[blue,thick](5e) – (6e);
[blue,thick](6e) – (6f);
[blue,thick](6f) – (7f);
[blue,thick](7f) – (7g);
[blue,thick](7g) – (8g);
[blue,thick](8g) – (8h);
[blue,thick](8h) – (9h);
[blue,thick](9h) – (10h);
[blue,thick](10h) – (10i);
[blue,thick](10i) – (10j);

[red,thick](1a) – (1b);
[red,thick](1b) – (2b);
[red,thick](2b) – (2c);
[red,thick](2c) – (3c);
[red,thick](3c) – (3d);
[red,thick](3d) – (3e);
[red,thick](3e) – (4e);
[red,thick](4e) – (4f);
[red,thick](4f) – (5f);
[red,thick](5f) – (5g);
[red,thick](5g) – (6g);
[red,thick](6g) – (6h);
[red,thick](6h) – (7h);
[red,thick](7h) – (7i);
[red,thick](8i) – (7i);
[red,thick](8i) – (9i);
[red,thick](9i) – (10i);
[red,thick](10j) – (10i);

[green,thick](1a) – (1b);
[green,thick](1b) – (1c);
[green,thick](1c) – (1d);
[green,thick](1d) – (2d);
[green,thick](2d) – (2e);
[green,thick](2e) – (2f);
[green,thick](2f) – (3f);
[green,thick](3f) – (3g);
[green,thick](3g) – (4g);
[green,thick](4g) – (4h);
[green,thick](5h) – (4h);
[green,thick](5h) – (5i);
[green,thick](5i) – (6i);
[green,thick](6i) – (6j);
[green,thick](6j) – (7j);
[green,thick](7j) – (8j);
[green,thick](8j) – (9j);
[green,thick](9j) – (10j);

We will reference a new family of paths - $ L_1, \dots, L_k $ that will serve as lower boundaries for our maximizing family. Fix positive integers $ q \ge r $, and $ k \ge 1 $. For each $ i = 1, \dots, k $, the bounding path $ L_i $ is given by:

* Walk horizontally from $ (1, k-i + 1) $ to $ (i, k-i+1) $, then

* Alternate between $ (0,1) $ and $ (1,0) $ steps, starting with $ (0,1) $, until reaching $ (r-k+i-1, r-i+1) $, then

* Walk horizontally to $ (q,r-i+1) $.

[scale=1, transform shape]

[label=left:$1$] (1a) at (0,0) ;
(1b) at (4,0) ;
[label=below:$k$] (1b') at (4,-0.15) ;
(1c) at (4,0.5) ;
(1d) at (4.5,0.5) ;
(1e) at (4.5,1) ;
(1f) at (5,1) ;
(1g) at (6,2) ;
(1h) at (6,2.5) ;
(1i) at (8,2.5) ;
(1j) at (8,2.5) ;

[label=left:$2$] (2a) at (0,0.5) ;
(2b) at (3.5,0.5) ;
(2c) at (3.5,1) ;
(2d) at (4,1) ;
(2e) at (4,1.5) ;
(2f) at (4.5,1.5) ;
(2g) at (5.5, 2.5) ;
(2h) at (5.5, 3) ;
(2i) at (6, 3) ;
(2j) at (8, 3) ;

[label=left:$3$] (3a) at (0,1) ;
(3b) at (3,1) ;
(3c) at (3,1.5) ;
(3d) at (3.5,1.5) ;
(3e) at (3.5,2) ;
(3f) at (4,2) ;
(3g) at (5, 3) ;
(3h) at (5, 3.5) ;
(3i) at (6, 3.5) ;
(3j) at (8,3.5) ;

[label=left:$(k - 1)$] (4a) at (0,3.5) ;
(4b) at (0.5,3.5) ;
(4c) at (0.5, 4) ;
(4d) at (1, 4) ;
(4e) at (1,4.5) ;
(4f) at (1.5, 4.5) ;
(4g) at (2.5, 5.5) ;
(4h) at (2.5, 6) ;
(4i) at (6, 6) ;
(4j) at (8, 6) ;

[label=left:$k$] (5a) at (0,4) ;
(5b) at (0,4) ;
(5c) at (0,4.5) ;
(5d) at (0.5, 4.5) ;
(5e) at (0.5,5) ;
(5f) at (1, 5) ;
(5g) at (2, 6) ;
[label=above:$r - k$] (5h) at (2, 6.5) ;
[label=above:$r - 1$] (5i) at (6, 6.5) ;
[label=above:$q$] (5j) at (8, 6.5) ;

[label=right: $ r $] (6) at (8,6.5) ;
[label=below: $1$] (7) at (0,-0.15) ;
[label=right: $ (r - k + 1)$] (8) at (8,2.5) ;
[label=right: $ (r - k + 2)$] (9) at (8,3) ;
[label=right: $ (r - k + 3)$] (11) at (8,3.5) ;
[label=right: $ (r - 1) $] (10) at (8,6) ;

(1a) – (1b);
(1b) – (1c);
(1c) – (1d);
(1d) – (1e);
(1e) – (1f);
[style = dashed] (1f) – (1g);
(1g) – (1h);
(1h) – (1i);
(1i) – (1j);

(2a) – (2b);
(2b) – (2c);
(2c) – (2d);
(2d) – (2e);
(2e) – (2f);
[style = dashed] (2f) – (2g);
(2g) – (2h);
(2h) – (2i);
(2i) – (2j);

(3a) – (3b);
(3b) – (3c);
(3c) – (3d);
(3d) – (3e);
(3e) – (3f);
[style = dashed] (3f) – (3g);
(3g) – (3h);
(3h) – (3i);
(3i) – (3j);

(4a) – (4b);
(4b) – (4c);
(4c) – (4d);
(4d) – (4e);
(4e) – (4f);
[style = dashed] (4f) – (4g);
(4g) – (4h);
(4h) – (4i);
(4i) – (4j);

(5a) – (5b);
(5b) – (5c);
(5c) – (5d);
(5d) – (5e);
(5e) – (5f);
[style = dashed] (5f) – (5g);
(5g) – (5h);
(5h) – (5i);
(5i) – (5j);

[fill = black] (1a) circle (0.050);
[fill = black] (1b) circle (0.050);
[fill = black] (1c) circle (0.050);
[fill = black] (1d) circle (0.050);
[fill = black] (1e) circle (0.050);
[fill = black] (1f) circle (0.050);
[fill = black] (1g) circle (0.050);
[fill = black] (1h) circle (0.050);
[fill = black] (1i) circle (0.050);
[fill = black] (1j) circle (0.050);

[fill = black] (2a) circle (0.050);
[fill = black] (2b) circle (0.050);
[fill = black] (2c) circle (0.050);
[fill = black] (2d) circle (0.050);
[fill = black] (2e) circle (0.050);
[fill = black] (2f) circle (0.050);
[fill = black] (2g) circle (0.050);
[fill = black] (2h) circle (0.050);
[fill = black] (2i) circle (0.050);
[fill = black] (2j) circle (0.050);

[fill = black] (3a) circle (0.050);
[fill = black] (3b) circle (0.050);
[fill = black] (3c) circle (0.050);
[fill = black] (3d) circle (0.050);
[fill = black] (3e) circle (0.050);
[fill = black] (3f) circle (0.050);
[fill = black] (3g) circle (0.050);
[fill = black] (3h) circle (0.050);
[fill = black] (3i) circle (0.050);
[fill = black] (3j) circle (0.050);

[fill = black] (4a) circle (0.050);
[fill = black] (4b) circle (0.050);
[fill = black] (4c) circle (0.050);
[fill = black] (4d) circle (0.050);
[fill = black] (4e) circle (0.050);
[fill = black] (4f) circle (0.050);
[fill = black] (4g) circle (0.050);
[fill = black] (4h) circle (0.050);
[fill = black] (4i) circle (0.050);
[fill = black] (4j) circle (0.050);

[fill = black] (5a) circle (0.050);
[fill = black] (5b) circle (0.050);
[fill = black] (5c) circle (0.050);
[fill = black] (5d) circle (0.050);
[fill = black] (5e) circle (0.050);
[fill = black] (5f) circle (0.050);
[fill = black] (5g) circle (0.050);
[fill = black] (5h) circle (0.050);
[fill = black] (5i) circle (0.050);
[fill = black] (5j) circle (0.050);

[fill = black] (2,2) circle (0.015);
[fill = black] (2.2,1.8) circle (0.015);
[fill = black] (1.8,2.2) circle (0.015);
[fill = black] (4,4) circle (0.015);
[fill = black] (4.2,3.8) circle (0.015);
[fill = black] (3.8,4.2) circle (0.015);

The lower boundary paths for $ k $ paths: $ L_1, \dots, L_k$ (from top to bottom). The numbers on the left (and right) indicate the row that the corresponding points are on. The numbers on the top and bottom indicate the columns the corresponding points are on.

<Ref> shows $ L_1, \dots, L_k $. These paths appear in <cit.> as well. In the case when all rows of $ T $ have the same size, this family of paths will always give rise to a set of increasing subsequences of maximum combined length, <cit.>. When the rows or $ T $ have different sizes, this is no longer the case, and we have to allow our family of paths to be weakly above these in respective top to bottom order.

There exists a family of paths $P_1,\ldots,P_k$ that maximizes $ \ell(P_1, \dots, P_k) $ such that $ P_i $ is weakly above $ L_i $ for all $ i $, and each $P_i$ has a horizontal segment $(r - k + i - 1,r-i+1) - (q,r-i+1)$.

Let $P_1,\ldots,P_k$ be a family of lattice paths maximizing $ \ell(P_1, \dots, P_k) $. From Lemma <ref> we may assume that each $P_i$ starts at $(1,k-i+1)$. From repeated usage of top-down switching lemma we may assume that all paths do not cross (they may intersect) and hence come in a top to bottom order, say $ P_1, \dots, P_k $ from top to bottom.

We claim that for each $i$, we can make $P_i$ stays weakly above the bounding path $L_i$. For path $P_1$, left-shifting gives us a path such that it starts at $(1,k)$ and each horizontal segment has size $1$ before the path reaches the top row. Hence $P_1$ is weakly above $ L_1 $. Now inductively assume that path $ P_j $ lies above $ L_j $ for all $ j = 1, \dots, (i - 1) $. If $P_i$ dips below $L_i$ at some point, pick the earliest point that this happens. Then in this row, $P_i$ must have horizontal segment of size at least $2$. From the fact that $P_{i-1}$ is weakly above $L_{i-1}$, we have the empty space necessary to left-shift $P_i$ so it lies weakly above $L_i$ in this row using <Ref>. We continue to similarly adjust $ P_i $ by left-shifting any other points where $ P_i $ goes below $ L_i $, so we may assume without loss of generality that $ P_i $ stays weakly above $ L_i $, completing our induction.

The last step is to show that each path $P_i$ has the horizontal segment $(r - k + i - 1,r-i+1) - (q,r -i + 1)$. We again employ induction on $i$. For path $ P_1 $, which stays weakly above $L_1$, it has the desired horizontal segment because $ L_1 $ has it in the top row. Inductively assume that $P_{i-1}$ has the horizontal segment from $(r - k + i - 2, r - i + 2)$ to $(q,r - i + 2)$. As $ P_i $ is weakly below $ P_{i - 1} $ but weakly above $ L_i $, $ P_i $ must pass through $ (r - k + i - 1,r -i + 1) $ and end with a horizontal segment in either row $ r - i + 2 $ or row $ r -i + 1 $. Now for any other path $ P_i, P_{i + 1}, \dots, P_k $ that ends in row $ r - i + 2 $, we can reverse rectangular flip it, <Ref>, so it ends in row $ r - i + 1 $ instead because $ P_{i - 1} $ already uses the same portion of row $ r - i + 1 $. This maintains the top-down order of the paths, so we will use the same labels for the paths. Thus, we may assume without loss of generality that $ P_i $ ends in row $ r -i + 1 $. As it is also above $ L_i $, $P_i$ must end in the horizontal segment $(r - k + i - 1,r -i + 1) - (q, r -i + 1)$, completing our induction.

[scale = 0.6]
(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1a) – (1b);
[green,thick](1c) – (1b);
[green,thick](1c) – (4c);
[green,thick](4c) – (4d);
[green,thick](4d) – (6d);
[green,thick](6d) – (6f);
[green,thick](6f) – (9f);
[green,thick](9f) – (9g);
[green,thick](9g) – (10g);
[green,thick](10g) – (10j);

[red,thick](1a) – (4a);
[red,thick](4a) – (4d);
[red,thick](5d) – (4d);
[red,thick](5d) – (5g);
[red,thick](5g) – (9g);
[red,thick](9g) – (9j);
[red,thick](9j) – (10j);

[blue,thick](1a) – (2a);
[blue,thick](2a) – (2b);
[blue,thick](2b) – (3b);
[blue,thick](3b) – (3e);
[blue,thick](3e) – (7e);
[blue,thick](7e) – (7f);
[blue,thick](7f) – (8f);
[blue,thick](8f) – (8i);
[blue,thick](8i) – (8j);
[blue,thick](8j) – (10j);

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1a) – (1b);
[green,thick](1c) – (1b);
[green,thick](1c) – (4c);
[green,thick](4c) – (4d);
[green,thick](4d) – (6d);
[green,thick](6d) – (6f);
[green,thick](6f) – (9f);
[green,thick](9f) – (9g);
[green,thick](9g) – (10g);
[green,thick](10g) – (10j);

[red,thick](1a) – (4a);
[red,thick](4a) – (4d);
[red,thick](5d) – (4d);
[red,thick](5d) – (5g);
[red,thick](5g) – (9g);
[red,thick](9g) – (9j);
[red,thick](9j) – (10j);

[blue,thick](1b) – (2b);
[blue,thick](2b) – (3b);
[blue,thick](3b) – (3e);
[blue,thick](3e) – (7e);
[blue,thick](7e) – (7f);
[blue,thick](7f) – (8f);
[blue,thick](8f) – (8i);
[blue,thick](8i) – (8j);
[blue,thick](8j) – (10j);

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1c) – (4c);
[green,thick](4c) – (4d);
[green,thick](4d) – (6d);
[green,thick](6d) – (6f);
[green,thick](6f) – (9f);
[green,thick](9f) – (9g);
[green,thick](9g) – (10g);
[green,thick](10g) – (10j);

[red,thick](1a) – (4a);
[red,thick](4a) – (4d);
[red,thick](5d) – (4d);
[red,thick](5d) – (5g);
[red,thick](5g) – (9g);
[red,thick](9g) – (9j);
[red,thick](9j) – (10j);

[blue,thick](1b) – (2b);
[blue,thick](2b) – (3b);
[blue,thick](3b) – (3e);
[blue,thick](3e) – (7e);
[blue,thick](7e) – (7f);
[blue,thick](7f) – (8f);
[blue,thick](8f) – (8i);
[blue,thick](8i) – (8j);
[blue,thick](8j) – (10j);

Running example: Start with a family of paths. Apply rectangular flip(s) to get the family satisfying Lemma <ref>. After this we may ignore the vertical segments in the first column to get a family satisfying the conditions of Lemma <ref>.

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1a) – (1b);
[green,thick](1c) – (1b);
[green,thick](1c) – (3c);
[green,thick](3c) – (3e);
[green,thick](3e) – (5e);
[green,thick](5e) – (5g);
[green,thick](5g) – (8g);
[green,thick](8g) – (8j);
[green,thick](8j) – (10j);

[red,thick](1a) – (4a);
[red,thick](4a) – (4d);
[red,thick](6d) – (4d);
[red,thick](6d) – (6e);
[red,thick](6e) – (7e);
[red,thick](7e) – (7f);
[red,thick](7f) – (9f);
[red,thick](9f) – (9g);
[red,thick](9g) – (10g);
[red,thick](10j) – (10g);

[blue,thick](1a) – (1b);
[blue,thick](1b) – (2b);
[blue,thick](2b) – (3b);
[blue,thick](3b) – (3c);
[blue,thick](3c) – (4c);
[blue,thick](4d) – (5d);
[blue,thick](4d) – (4c);
[blue,thick](5d) – (5e);
[blue,thick](5e) – (6e);
[blue,thick](6f) – (6e);
[blue,thick](6f) – (8f);
[blue,thick](8f) – (8f);
[blue,thick](8f) – (8g);
[blue,thick](8g) – (9g);
[blue,thick](9g) – (9j);
[blue,thick](9j) – (10j);

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1c) – (1e);
[green,thick](1e) – (2e);
[green,thick](2e) – (2g);
[green,thick](2g) – (3g);
[green,thick](3g) – (3j);
[green,thick](3j) – (10j);

[red,thick](1a) – (4a);
[red,thick](4a) – (4d);
[red,thick](6d) – (4d);
[red,thick](6d) – (6e);
[red,thick](6e) – (7e);
[red,thick](7e) – (7f);
[red,thick](7f) – (9f);
[red,thick](9f) – (9g);
[red,thick](9g) – (10g);
[red,thick](10j) – (10g);

[blue,thick](1b) – (2b);
[blue,thick](2b) – (3b);
[blue,thick](3b) – (3c);
[blue,thick](3c) – (4c);
[blue,thick](4d) – (5d);
[blue,thick](4d) – (4c);
[blue,thick](5d) – (5e);
[blue,thick](5e) – (6e);
[blue,thick](6f) – (6e);
[blue,thick](6f) – (8f);
[blue,thick](8f) – (8f);
[blue,thick](8f) – (8g);
[blue,thick](8g) – (9g);
[blue,thick](9g) – (9j);
[blue,thick](9j) – (10j);

[black,dashed](1d) – (2d);
[black,dashed](2d) – (2e);
[black,dashed](2e) – (3e);
[black,dashed](3e) – (3f);
[black,dashed](3f) – (4f);
[black,dashed](4f) – (4g);
[black,dashed](4g) – (5g);
[black,dashed](5g) – (5h);
[black,dashed](5h) – (6h);
[black,dashed](6h) – (6i);
[black,dashed](6i) – (7i);
[black,dashed](7i) – (7j);
[black,dashed](7j) – (10j);

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1c) – (1e);
[green,thick](1e) – (2e);
[green,thick](2e) – (2g);
[green,thick](2g) – (3g);
[green,thick](3g) – (3j);
[green,thick](3j) – (10j);

[red,thick](1a) – (4a);
[red,thick](4a) – (4d);
[red,thick](6d) – (4d);
[red,thick](6d) – (6e);
[red,thick](6e) – (7e);
[red,thick](7e) – (7f);
[red,thick](7f) – (9f);
[red,thick](9f) – (9g);
[red,thick](9g) – (10g);
[red,thick](10j) – (10g);

[blue,thick](1b) – (1b);
[blue,thick](1b) – (1c);
[blue,thick](1c) – (2c);
[blue,thick](2c) – (2d);
[blue,thick](2d) – (3d);
[blue,thick](3d) – (3e);
[blue,thick](3e) – (4e);
[blue,thick](4e) – (4f);
[blue,thick](5f) – (4f);
[blue,thick](5f) – (5g);
[blue,thick](5g) – (6g);
[blue,thick](6g) – (6i);
[blue,thick](6i) – (9i);
[blue,thick](9i) – (9j);
[blue,thick](9j) – (10j);

[black,dashed](1c) – (1d);
[black,dashed](1d) – (2d);
[black,dashed](2d) – (2e);
[black,dashed](2e) – (3e);
[black,dashed](3e) – (3f);
[black,dashed](3f) – (4f);
[black,dashed](4f) – (4g);
[black,dashed](4g) – (5g);
[black,dashed](5g) – (5h);
[black,dashed](5h) – (6h);
[black,dashed](6h) – (6i);
[black,dashed](6i) – (7i);
[black,dashed](7i) – (7j);
[black,dashed](7j) – (10j);

[black,dashed](1b) – (2b);
[black,dashed](2c) – (2b);
[black,dashed](2c) – (3c);
[black,dashed](3c) – (3d);
[black,dashed](3d) – (4d);
[black,dashed](4d) – (4e);
[black,dashed](4e) – (5e);
[black,dashed](5e) – (5f);
[black,dashed](5f) – (6f);
[black,dashed](6f) – (6g);
[black,dashed](6g) – (7g);
[black,dashed](7g) – (7h);
[black,dashed](7h) – (8h);
[black,dashed](8h) – (8i);
[black,dashed](8i) – (10i);
[black,dashed](10i) – (10j);

Running example: Apply top-down switching to get a family of paths that do not cross. Next apply left-shift on $P_1$ to get a path that stays weakly above the bounding path $L_1$, drawn in black dotted lines. Do the same for $P_2$ afterwards.

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1c) – (1e);
[green,thick](1e) – (2e);
[green,thick](2e) – (2g);
[green,thick](2g) – (3g);
[green,thick](3g) – (3j);
[green,thick](3j) – (10j);

[red,thick](1a) – (2a);
[red,thick](2a) – (2b);
[red,thick](2b) – (3b);
[red,thick](3b) – (3c);
[red,thick](3c) – (4c);
[red,thick](4c) – (4d);
[red,thick](5d) – (4d);
[red,thick](5d) – (5e);
[red,thick](5e) – (6e);
[red,thick](6e) – (6f);
[red,thick](6f) – (7f);
[red,thick](7f) – (7g);
[red,thick](7g) – (8g);
[red,thick](8h) – (8g);
[red,thick](10h) – (8h);
[red,thick](10h) – (10j);

[blue,thick](1b) – (1c);
[blue,thick](1c) – (2c);
[blue,thick](2c) – (2d);
[blue,thick](2d) – (3d);
[blue,thick](3d) – (3e);
[blue,thick](3e) – (4e);
[blue,thick](4e) – (4f);
[blue,thick](5f) – (4f);
[blue,thick](5f) – (5g);
[blue,thick](5g) – (6g);
[blue,thick](6g) – (6i);
[blue,thick](6i) – (9i);
[blue,thick](9i) – (9j);
[blue,thick](9j) – (10j);

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1c) – (1e);
[green,thick](1e) – (2e);
[green,thick](2e) – (2g);
[green,thick](2g) – (3g);
[green,thick](3g) – (3j);
[green,thick](3j) – (10j);

[red,thick](1a) – (2a);
[red,thick](2a) – (2b);
[red,thick](2b) – (3b);
[red,thick](3b) – (3c);
[red,thick](3c) – (4c);
[red,thick](4c) – (4d);
[red,thick](5d) – (4d);
[red,thick](5d) – (5e);
[red,thick](5e) – (6e);
[red,thick](6e) – (6f);
[red,thick](6f) – (7f);
[red,thick](7f) – (7g);
[red,thick](7g) – (8g);
[red,thick](8h) – (8g);
[red,thick](10h) – (8h);
[red,thick](10h) – (10j);

[blue,thick](1b) – (1c);
[blue,thick](1c) – (2c);
[blue,thick](2c) – (2d);
[blue,thick](2d) – (3d);
[blue,thick](3d) – (3e);
[blue,thick](3e) – (4e);
[blue,thick](4e) – (4f);
[blue,thick](5f) – (4f);
[blue,thick](5f) – (5g);
[blue,thick](5g) – (6g);
[blue,thick](6g) – (6i);
[blue,thick](6i) – (9i);
[blue,thick](9i) – (10i);
[blue,thick](10i) – (10j);

[scale = 0.6]

(1a) at (1,1) ;
(1b) at (1,2) ;
(1c) at (1,3) ;
(1d) at (1,4) ;
(1e) at (1,5) ;
(1f) at (1,6) ;
(1g) at (1,7) ;
(1h) at (1,8) ;
(1i) at (1,9) ;
(1j) at (1,10) ;
(2a) at (2,1) ;
(2b) at (2,2) ;
(2c) at (2,3) ;
(2d) at (2,4) ;
(2e) at (2,5) ;
(2f) at (2,6) ;
(2g) at (2,7) ;
(2h) at (2,8) ;
(2i) at (2,9) ;
(2j) at (2,10) ;
(3a) at (3,1) ;
(3b) at (3,2) ;
(3c) at (3,3) ;
(3d) at (3,4) ;
(3e) at (3,5) ;
(3f) at (3,6) ;
(3g) at (3,7) ;
(3h) at (3,8) ;
(3i) at (3,9) ;
(3j) at (3,10) ;
(4a) at (4,1) ;
(4b) at (4,2) ;
(4c) at (4,3) ;
(4d) at (4,4) ;
(4e) at (4,5) ;
(4f) at (4,6) ;
(4g) at (4,7) ;
(4h) at (4,8) ;
(4i) at (4,9) ;
(4j) at (4,10) ;
(5a) at (5,1) ;
(5b) at (5,2) ;
(5c) at (5,3) ;
(5d) at (5,4) ;
(5e) at (5,5) ;
(5f) at (5,6) ;
(5g) at (5,7) ;
(5h) at (5,8) ;
(5i) at (5,9) ;
(5j) at (5,10) ;
(6a) at (6,1) ;
(6b) at (6,2) ;
(6c) at (6,3) ;
(6d) at (6,4) ;
(6e) at (6,5) ;
(6f) at (6,6) ;
(6g) at (6,7) ;
(6h) at (6,8) ;
(6i) at (6,9) ;
(6j) at (6,10) ;
(7a) at (7,1) ;
(7b) at (7,2) ;
(7c) at (7,3) ;
(7d) at (7,4) ;
(7e) at (7,5) ;
(7f) at (7,6) ;
(7g) at (7,7) ;
(7h) at (7,8) ;
(7i) at (7,9) ;
(7j) at (7,10) ;
(8a) at (8,1) ;
(8b) at (8,2) ;
(8c) at (8,3) ;
(8d) at (8,4) ;
(8e) at (8,5) ;
(8f) at (8,6) ;
(8g) at (8,7) ;
(8h) at (8,8) ;
(8i) at (8,9) ;
(8j) at (8,10) ;
(9a) at (9,1) ;
(9b) at (9,2) ;
(9c) at (9,3) ;
(9d) at (9,4) ;
(9e) at (9,5) ;
(9f) at (9,6) ;
(9g) at (9,7) ;
(9h) at (9,8) ;
(9i) at (9,9) ;
(9j) at (9,10) ;
(10a) at (10,1) ;
(10b) at (10,2) ;
(10c) at (10,3) ;
(10d) at (10,4) ;
(10e) at (10,5) ;
(10f) at (10,6) ;
(10g) at (10,7) ;
(10h) at (10,8) ;
(10i) at (10,9) ;
(10j) at (10,10) ;

[green,thick](1c) – (1e);
[green,thick](1e) – (2e);
[green,thick](2e) – (2g);
[green,thick](2g) – (3g);
[green,thick](3g) – (3j);
[green,thick](3j) – (10j);

[red,thick](1a) – (2a);
[red,thick](2a) – (2b);
[red,thick](2b) – (3b);
[red,thick](3b) – (3c);
[red,thick](3c) – (4c);
[red,thick](4c) – (4d);
[red,thick](5d) – (4d);
[red,thick](5d) – (5e);
[red,thick](5e) – (6e);
[red,thick](6e) – (6f);
[red,thick](6f) – (7f);
[red,thick](7f) – (7g);
[red,thick](7g) – (8g);
[red,thick](8h) – (8g);
[red,thick](10h) – (8h);

[blue,thick](1b) – (1c);
[blue,thick](1c) – (2c);
[blue,thick](2c) – (2d);
[blue,thick](2d) – (3d);
[blue,thick](3d) – (3e);
[blue,thick](3e) – (4e);
[blue,thick](4e) – (4f);
[blue,thick](5f) – (4f);
[blue,thick](5f) – (5g);
[blue,thick](5g) – (6g);
[blue,thick](6g) – (6i);
[blue,thick](6i) – (9i);
[blue,thick](9i) – (10i);

Running example: Apply left-shift on $P_3$. Lastly, apply reverse rectangular flip(s) to get the family satisfying Lemma <ref>.

For example start with a family of paths in the left figure of Figure <ref>. Using rectangular flip at the beginning portion gives us the figure in the middle, where the paths satisfy the property of Lemma <ref>. Hence we may assume the paths start at $(1,1),(1,2),(1,3)$ as in the rightmost figure of Figure <ref>.

Next using top-down switching lemma here gives us a family where we can label the paths $P_1,P_2,P_3$ from top to bottom in a way so that path $P_i$ is weakly above path $P_{i+1}$ for each $i$ as in the leftmost figure of Figure <ref>. Next use the left-shifting on the top path $P_1$ to get the middle figure of Figure <ref>. Notice the resulting modification of $P_1$ gives us a path that lies weakly above the bounding path $L_1$ drawn in black dashed lines. Next use left-shifting on $P_2$ to get the rightmost figure, where the resulting modification of $P_2$ lies weakly above the bounding path $L_2$. Now do the same for $P_3$ as well to get the left figure of Figure <ref>. Lastly use reverse rectangular flips at the end to get the desired family of Lemma <ref>.

Now we are ready to prove our main result.

For any skew standard tableaux $ T $ with $ r $ rows and weakly decreasing row sizes from top to bottom,

\[
\stab(T) \le r.
\]

Let $ \lam_1 \ge \dots \ge \lam_r $ be the row sizes of $ T $ from top to bottom. By Greene's theorem, [2], we have that

\[
\sum_{j = 1}^k \sh(\Rect(T^{(q)}))_j = \ell( \underbrace{M(q,T), \dots, M(q,T)}_{k \tx{ times} } )
\]

where $ M(q,T) $ represents the reading word of $ T $ - the rows are read bottom to top, left to right.

Now, for each $ q \ge r - 1 $, <Ref> tells us that $ \ell( \underbrace{M(q,T), \dots, M(q,T)}_{k \tx{ times} } ) $ is exhibited by increasing subsequences of some family of lattice paths $P_1, \dots, P_k $ where $ P_i $ ends in the horizontal segment $(r - k + i - 1,r-i+1) - (q,r-i+1)$ for all $ i = 1, \dots, k $. Note that because $ i \le k $, we always have $ r - k + i - 1 \le r - 1 \le q $.

In particular, to go from $ q = r - 1 $ to $ q = r $, we may simply add on the increasing sequences represented by the points $ (r,r), (r, r - 1), \dots, (r, r - k + 1) $ to a length-maximizing family for $ q = r  - 1 $ from top to bottom. As these points are sequences with sizes $ \lam_1, \dots, \lam_k $ respectively, we have

\begin{equation}
\begin{aligned}
\label{eq:r-1tor}
\sum_{j = 1}^k \sh(\Rect(T^{(r)}))_j & = \ell(\underbrace{M(r,T), \dots, M(r,T)}_{k \tx{ times} } ) \\
& \ge \ell(\underbrace{M(r - 1,T), \dots, M(r-1,T)}_{k \tx{ times} } ) + \lam_1 + \dots + \lam_k \\
& = \sum_{j = 1}^k \sh(\Rect(T^{(r - 1)}))_j + \lam_1 + \dots + \lam_k.
\end{aligned}
\end{equation}

On the other hand, if we remove the the points $ (r,r), (r, r - 1), \dots, (r, r - k + 1) $ from such a length-maximizing family of lattice paths for $ q = r $ - note we can assume the family contains these points by <Ref>, we get a family of paths for $ q = r - 1 $. Since we removed $ \lam_1 + \dots + \lam_k $ elements potentially used in the sequences, we deduce

\begin{equation}
\begin{aligned}
\label{eq:rtor-1}
\sum_{j = 1}^k \sh(\Rect(T^{(r - 1)}))_j & = \ell(\underbrace{M(r - 1,T), \dots, M(r-1,T)}_{k \tx{ times} }) \\
& \ge \ell(\underbrace{M(r,T), \dots, M(r,T)}_{k \tx{ times} } ) - (\lam_1 + \dots + \lam_k) \\
& = \sum_{j = 1}^k \sh(\Rect(T^{(r)}))_j - (\lam_1 + \dots + \lam_k).
\end{aligned}
\end{equation}

Putting (<ref>) and (<ref>) together,

\begin{align}
\label{eq:shapeincrease}
\sum_{j = 1}^k \sh(\Rect(T^{(r)}))_j - \sum_{j = 1}^k \sh(\Rect(T^{(r - 1)}))_j = \lam_1 + \dots + \lam_k.
\end{align}

Since (<ref>) holds for all $ k = 1, \dots, r $, we must have

\[
\sh(\Rect(T^{(r)}))_j - \sh(\Rect(T^{(r - 1)}))_j = \lam_j
\]

for all $ j = 1, \dots, r $. Hence the rows of $ \Rect(T^{(r)}) \mid_{[(r - 1)n + 1, rn]} $ have the same sizes as the rows of $ T + (r - 1)n $. But this can only happen if every element of $ T + (r - 1)n $ experiences no vertical slides. Therefore, $ T $ stabilizes at $ r $, so $ \stab(T) \le r $.

The main idea of our proof was to narrow our search for a length-maximizing family of lattice paths to those satisfying a certain property - namely lying above the bounding paths and ending in the same horizontal segments at the bounding paths. Is there is an efficient way to construct a particular family of length-maximizing paths given the tableau.

Given a skew tableau $T$, is there a simple method to find a length-maximizing family of $k$-paths in $M(q,T)$ for each $k$ and $q$?

We have found an upper bound on the stabilization index of a tableau. It seems a far-fetched goal at this moment to obtain this index without using Greene's theorem or constructing the rectification. A reasonable subclass of tableaux to see if such thing is possible would be tableaux constructed from permutations as in Figure <ref>. Given a permutation $w$, we can construct the skew tableau $T_w$ which has one entry per each row and $w$ as its reading word. Then we can define $\stab(w)$ as $\stab(T_w)$, which give us a new permutation statistic!

In Chapter 8 of [1], Ahlbach introduced the stabilization index as a permutation statistic. He showed that $ \stab(w) $ is bounded strictly below by the ascent statistic, <cit.>, showed that $ \stab(w) $ depends only the recording tableau $ Q(w) $, <cit.>, characterized the permutations with stab 1, <cit.>, and characterized the permutations with stab 2, <cit.>. But there are still many open questions! A full characterization of $ \stab(w) $ in terms of $ Q(w) $ would be ideal.

\[
S = \begin{ytableau} \none & \none & 2 \\ \none  & 3 \\ 1 \end{ytableau} \, , \qquad Q = \begin{ytableau} \none & \none & 3 \\ \none  & 2 \\ 1 \end{ytableau} \, ,
\]

\[
\Rect(S^{(3)}) = \begin{ytableau} 1 & 2 & *(orange) 5 & *(cyan) 8 \\ 3 & *(orange) 6 & *(cyan) 9 \\ *(orange) 4 & *(cyan) 7 \end{ytableau} \, , \qquad \Rect(Q^{(3)}) = \begin{ytableau} 1 & 2 & 3 & *(orange) 6  & *(cyan) 9\\ *(orange) 4 & *(orange) 5 & *(cyan) 8 \\   *(cyan) 7 \end{ytableau} \, ,
\]

Tableaux $S=T_{132}$ and $Q=T_{123}$. We can see that the stabilization index of $132$ is $2$ whereas the stabilization index of $123$ is $3$.

For a permutation $ w $, is there a way to find $ \stab(w) $ directly from the permutation (that is, without constructing the rectification of or using Greene's theorem)? What is the relationship between $ \stab(w) $ and $ Q(w) $?

§ ACKNOWLEDGEMENTS

This research was primarily conducted during the Summer 2020 High School Math Camp at Texas State University. The authors gratefully acknowledge the support from the camp and also thank Texas State University for providing support and a great working environment.

[1]
Connor Ahlbach.
Tableau stabilization and rectangular tableaux fixed by promotion
Journal of Algebraic Combinatorics, 2020.

[2]
C. Greene.
An extension of Schensted's theorem.
Advances in Math., 14:254–265, 1974.

[3]
B. Rhoades.
Cyclic sieving, promotion, and representation theory.
J. Combin. Theory Ser. A, 117(1):38–76, 2010.