%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2021}
\articlenumber{4}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{Macros,subfig,standalone, amsthm, amsmath, amssymb, amsfonts, comment}

\newcommand{\newword}[1]{\textbf{\emph{#1}}}
\newcommand{\subseq}{\preceq}

\newtheorem{thm}{Theorem}[section]
\newtheorem{lem}[thm]{Lemma}

%\usepackage{lipsum}

%% define your title in the usual way
\title[Tableau Stabilization]{Tableau Stabilization and Lattice paths (extended abstract)}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{ Connor Ahlbach\addressmark{1}, Jacob David\addressmark{2}, Suho Oh\addressmark{1}, \and Christopher Wu\addressmark{3} }

%\author[Optional shorter names]{Connor Ahlbach\thanks{\href{mailto:hello@world.c}{hello@world.c}. Longer names me was partially supported by Grant 2017.11.14.$\partial$\;supp.}\addressmark{1}, \and you\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Texas State University, San Marcos, TX\\ \addressmark{2}Philips Exeter Academy, Exeter, NH\\ \addressmark{3}Westlake High School, Austin, TX}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{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 extended abstract 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.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Young Tableau, RSK, Green's theorem, Lattice paths, Increasing sequences, Jeu-De-Taquin}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations, ie. [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{04Ahlbach.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands

\begin{document}

\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above
\section{Introduction}

Tableau stabilization was introduced in \cite{TabStab} 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 \cite{MR2087303} for the action of promotion on rectangular tableaux \cite{MR2557880}. Alexandersson, Oğuz, and Linusson have recently found similar results for certain families of semistandard Young tableaux, like stretched hooks, disjoint rectangles, and special cases of small ribbons \cite{PromSSYT}. Moreover, Alexandersson, Pfannerer, Rubey, and Uhlin showed that whenever the fake degree polynomial $ f^{\lam/\mu}(q) $ associated to a skew shape $ \lam/\mu $ evaluates to a nonnegative integer at roots of unity, then there is a CSP triple $ ( \SSYT(\lam/\mu), C_n, f^{\lam/\mu}(q)) $ for some cyclic action $ C_n $ on $ \SSYT(\lam/\mu)$, not necessarily promotion \cite{SkewCSP}.

But while many of these CSPs count fixed points of promotion, they say nothing about what the actual fixed points are. Purbhoo first found all rectangular tableaux of shape $ (a^b) $ fixed by $ a $ promotions for $ b \ge a $ \cite{MR3625918}. More recently, Ahlbach exhibited all sufficiently large rectangular tableaux fixed by a given power of promotion by applying the rectification operator to skew tableaux formed by attaching shifted copies of a skew tableaux to itself \cite{TabStab}. This naturally gives rise to the notion of tableaux stabilization. 

\begin{Definition} \label{def:stab} For any skew standard 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 skew standard tableau. Let $ n $ denote the size of $ T $ and $ k $ be a positive integer. Let $ \Rect $ denote Sch\"utzenberger's rectification operator \cite{MR0498826}. We say $ T $ \emph{stabilizes} at $ k $ if each element of $[(k - 1)n + 1, kn]$ lies in the same row in $\Rect(S^{(k)})$ as it does in $S^{(k)}$. Let $ \stab(S) $ denote the minimum value at which $ S $ stabilizes.

\end{Definition}

\begin{Remark} Having weakly decreasing row sizes from top to bottom is required for $ T^{(k)} $ to be a skew standard tableau for all $ k \ge 1 $. If this is not the case, $ T^{(k)} $ need not be standard. Consider \Cref{fig:tabincrow}, where $ T^{(2)} $
\begin{figure}[htbp]
    \input{Figures/tabincrow}
\caption{The number of boxes in each row has to be weakly decreasing from top to bottom, or else $ T^{(k)} $ need not be standard.}
\label{fig:tabincrow}
\end{figure}
is not a skew tableau both because of its shape and the third column not being increasing.


\end{Remark}


\begin{Example} \label{ex:stab}
%\begin{figure}[htbp]
%    \input{Figures/tabexamplepadding1}
% \caption{Example of a skew tableau $S$, the tableau $S^{(3)}$ constructed from $S$, and its rectification.}
% \label{fig:tabexamplepadding1}
% \end{figure}
% In Figure~\ref{fig:tabexamplepadding1}, $ 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{fig:tabexamplepadding2}, 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{figure}[htbp]
    \input{Figures/tabexamplepadding2}
\caption{Example of a skew tableau $T$, the tableau $T^{(3)}$ constructed from $T$, and its rectification.}
\label{fig:tabexamplepadding2}
\end{figure}


\end{Example}

Ahlbach proved that once a tableaux stabilizes at a value, it continues to stabilize for higher values, \cite[Lemma 3.9]{TabStab}. 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 $, \cite[Theorem 1.6]{TabStab}, and used it to show that any tableaux with $ r $ rows of the same size stabilizes at $ r $, \cite[Theorem 1.4]{TabStab}. 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.

\begin{Theorem} \label{thm:main} For any skew standard tableaux $ T $ with $ r $ rows and weakly decreasing row sizes from top to bottom,
\[
    \stab(T) \le r.
\]
\end{Theorem}

The proof of the same-size-rows case of \Cref{thm:main} in \cite{TabStab} relied on a formula for the shape of the stabilized tableau. 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 \cite{TabStab} to prove \Cref{thm:main}. Our argument relies on Greene's Theorem \cite{MR0354395} characterizing the shape of the insertion tableaux of words coming from the RSK-correspondence \cite{schensted_1961}, in terms of their increasing subsequences and a careful analysis of the increasing subsequences of reading words of $ T^{(k)} $ for skew standard 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 subsequences. In section 4, we prove the main result using the tools developed in the previous sections.


\section{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. For a more detailed introduction and applications of longest increasing sequences, we recommend the reader to~\cite{romik_2015}. Before we introduce the essential tools, we will briefly explain why we need them.

%\begin{Remark}

% 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 de taquin, the result need not be unique, unlike rectifying all at once \cite{MR0498826}. Figure~\ref{fig:obviousbad} demonstrates this. Hence we instead look at longest increasing sequences and Greene's theorem to analyze the shape of $\Rect(T^{(k)})$.
%\end{Remark}

% \begin{figure}[htbp]
%    \input{Figures/obviousbad}
%  \caption{If we rectify only the white copy first, rectifying the orange copy can produce two different outcomes depending on the order of the slides.}
% \label{fig:obviousbad}
% \end{figure}



\subsection{Greene's theorem}


\begin{Definition}(Reading Word)
The \emph{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.
\end{Definition}

\begin{figure}[htbp]
    \input{Figures/Tforreading}
 \caption{The reading word of $ T $ is $273591468$. The tableau to the right is its rectification, and $ \sh(\Rect(T)) = (5,3,1). $}
 \label{fig:Tforreading}
\end{figure}

\begin{Theorem}[Greene's Theorem, \cite{MR0354395}]
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(\pi) = \sh(\Rect(T))_1 + \cdots + \sh(\Rect(T))_k.
\]
\end{Theorem}

% Consider the tableau in Figure~\ref{fig:Tforreading}. 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.


%In \cite{TabStab}, Ahlbach used lattice paths on a matrix to represent increasing subsequences of the skew tableau.


\subsection{Lattice paths}

%This part should probably come way before
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 $(i-1)n$. 

\begin{Remark}
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. We will also read matrices from left to right, then top to bottom for the purpose of reading words.

% We will use an unusual labeling of each of the entries in the matrix. An entry $M_{i,j}$, the $(i,j)$-entry of the matrix $M$, will denote the entry at the $i$-th column from the left and $j$-th row from the bottom. Notice that this is essentially how the integer points in the positive quadrant of the $xy$-plane is labeled. The reason we follow this unusual convention is to focus on lattice paths, so it is more natural to use the convention of the points in the $xy$-plane.
\end{Remark}



\begin{Example} With $ T $ as in \Cref{fig:Tforreading}, 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}$.
\end{Example}


\begin{Definition} 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 A.
\]

\end{Definition}

%Actual start of section

% \begin{Remark}\label{rem:inc}
% The words in column $ j $ of $M$ use the letters $I_j \coloneqq \{(j-1)n+1,\ldots,jn\}$ without repetition. Hence any entry used in column $ j $ of $M$ is bigger than any entry used in the previous columns.
% \end{Remark}

A \newword{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$.

\begin{Definition} \label{def:mclis} 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$ \newword{exhibits} $\ell(A_1,\ldots,A_k)$ if $|S_1|+\cdots+|S_k|=\ell(A_1,\ldots,A_k)$.
\end{Definition}

% For any lattice path $S$, let $\LIS(S)$ denote an increasing sequence of maximum length that takes elements from $ S $. $\LIS(S_1,\ldots,S_t)$ on multiple paths $S_1,\ldots,S_t$ will denote disjoint increasing sequences within each $S_i$ such that the total combined length of the sequences are maximized. And $l(S_1,\ldots,S_t)$ is going to denote the length of $\LIS(S_1,\ldots,S_t)$. 


% 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.

% \bs
% Why are investigating lattice paths within matrix $M$?

\begin{Lemma} \label{lem:LPsubseq}
Any increasing subsequence of the reading word of $T^{(k)}$ is a subsequence of a lattice path within $M$.
\end{Lemma}

\begin{Example}
% Take a look at the tableau in Figure~\ref{fig:Tforlatticepath}.
% \begin{figure}[htbp]
%    \input{Figures/Tforlatticepath}
% \caption{}
% \label{fig:Tforlatticepath}
% \end{figure}
% This tableau has a reading word of $473691258$. Then the grid would be 
% \begin{align}
%    \begin{matrix} 1258 & \color{}1258 & \color{cyan}1258 \\ 369 & \color{orange}369 & \color{cyan}369 \\ 47 & \color{orange}47 & \color{cyan}47 \color{black} \end{matrix}
% \end{align}

With $ T $ as in \Cref{fig:Tforreading}, 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 \Cref{fig:latticepath1}.
\begin{figure}[htbp]
    \input{Figures/latticepath1}
\caption{The lattice path 273591468\color{orange}{1468}\color{cyan}{1468} \color{black} containing $ 23568\color{orange}{1468} \color{cyan}{1468} $.}
\label{fig:latticepath1}
\end{figure}
Note this agrees with Greene's Theorem since $ \lam_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 \Cref{fig:latticepath2}.
\begin{figure}[htbp]
    \input{Figures/latticepath2}
\caption{The minimal lattice paths containing $ 1468\color{orange}{1468} \color{cyan}{1468} $ and $ 2359\color{orange}{359} \color{cyan}{359} $.}
\label{fig:latticepath2}
\end{figure}
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 \Cref{fig:latticepath3}.
% \begin{figure}[htbp]
%     \input{Figures/latticepath3}
% \caption{The minimal 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} $.}
% \label{fig:latticepath3}
% \end{figure}
% 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 as we did in \Cref{lem:LPsubseq} and \Cref{fig:latticepath1}. What we are really interested in is the increasing subsequences they contain. By \Cref{lem:LPsubseq}, we can view any $ k $ disjoint increasing subsequences of the reading word of $ T^{(q)} $ as contained within a family of $ k $ possibly intersecting 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 \Cref{def:mclis}.


% increasing subsequence $ 2359\color{orange}3568\color{cyan}1468\color{black} $ is part of the

\end{Example}
\color{black}

% \subsection{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 a key tool in the following section.

% \begin{Lemma}\label{lem:ColumnSplitting}(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,*}).
% \]
% \end{Lemma} 

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




\section{Lattice Path Tools} 
\label{sec:LPtools}
%In this section we will introduce and prove various tools we will need for the proof of our main result. Given a family of paths, we will show several operations that modify those paths while weakly increasing the maximum combined length of increasing subsequences they contain. 


In this section, we will introduce some transformations on the family of lattice paths so that the maximum combined length of increasing subsequences they contain weakly increases.

  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 portions of 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.


%do something similar for horizontal segments instead.

%Once all the operations are introduced, we will show how they are applied on a running example. We recommend the first time reader look at that subsection first before going through this section.

%\begin{figure}[htbp]
%    \centering
%    \input{Figures/mainbeginning}
%     \caption{3 Lattice paths on a 10 x 10 matrix}
%     \label{fig:mainbeginning}
%\end{figure}



\subsection{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{fig:topdown}.


    \begin{figure}
        \centering
        \subfloat[Crossing paths.]{\input{Figures/topdown}}
        \qquad
        \subfloat[After switching.]{\input{Figures/topdown2}}
    \caption{The top-down switching process.}
    \label{fig:topdown}
    \end{figure}


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{fig:topdown}. After this top-down switch, 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.

%Top-Down Switching
%\begin{Lemma}(Top-Down Switching) \label{lem:TDS}
%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 \Cref{fig:topdown},
%\[
%    \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 $.
%\end{Lemma}


An example of top-down switching is given in going from rightmost figure of Figure~\ref{fig:running1} to leftmost figure of Figure~\ref{fig:running2}. 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 $. 





\subsection{Left-shifting}


\begin{Definition}
A \newword{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{fig:leftshift1}.
\end{Definition}

\begin{figure}[htbp]

\begin{center}
    \input{Figures/leftshift1}
\end{center}
\caption{Left-shifting applied to a lattice path}
\label{fig:leftshift1}
\end{figure}


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

%Applying left-shift on the top path of the running example of our section (Figure~\ref{fig:mainendsplitting}) gives Figure~\ref{fig:mainleftshift1}. Don't worry about the dashed path yet: we will define it in the next section.

An example of left-shifting is given in going from leftmost figure to the middle figure in Figure~\ref{fig:running2}. Beware that 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 paths above.


%Notice that after applying left-shifting on the top-path, it lies above the black path that looks like a staircase. This is an example of a \newword{bounding path} which will be defined and used in the next section.

  %  \begin{figure}[htbp]
  %      \centering
  %      \subfloat[]{\input{Figures/exleftshift1}}
  %      \qquad
  %      \subfloat[]{\input{Figures/exleftshift2}}
  %      \qquad
  %      \subfloat[]{\input{Figures/exleftshift3}}
  %      \qquad
  %      \subfloat[]{\input{Figures/exleftshift4}}
  %  \caption{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.}
  %  \label{fig:newleftshift1}
  %  \end{figure}


%\begin{figure}
%        \input{Figures/mainleftshift1}
%   \caption{Left-shift $P_1$ so that it is weakly above the bounding path $L_1$.}
%    \label{fig:mainleftshift1}
%\end{figure}
   


\subsection{Rectangular flip and reverse rectangular flip.}

A rectangular flip is given in Figure~\ref{fig:rectflip}. 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 going from leftmost figure to the middle figure in Figure~\ref{fig:running1}. %Notice that in the left figure of Figure~\ref{fig:newrectflip}, the blue and red path share a horizontal segment at the beginning. After the rectangular flip, the red and blue paths do not share a horizontal segment from $ (a,i) $ to $ (b, i) $. Also after this operation, the green path goes through $(1,3)$, the blue goes through $(1,2)$ and the red path goes through $(1,1)$. In the next section, we will show at least one length-maximizing family of paths has the property of starting at these points.

\begin{figure}[htbp]
\centering
    \input{Figures/rectflip}
\caption{A rectangular flip on the blue path with respect to the red path}
\label{fig:rectflip}
\end{figure}


% An example of rectangular flip is given in Figure~\ref{fig:rectflip}. 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{fig:newrectflip}. Notice that in the left figure of Figure~\ref{fig:newrectflip}, the blue and red path share a horizontal segment at the beginning. After the rectangular flip, the red and blue paths do not share a horizontal segment from $ (a,i) $ to $ (b, i) $. Also after this operation, the green path goes through $(1,3)$, the blue goes through $(1,2)$ and the red path goes through $(1,1)$. In the next section, we will show at least one length-maximizing family of paths has the property of starting at these points.


A reverse rectangular flip is given in Figure~\ref{fig:revrectflip}. 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 a reverse rectangular flip used in a family of paths is illustrated in going from middle figure to the rightmost figure in Figure~\ref{fig:running3}. 
%Notice that in the left figure of Figure~\ref{fig:newrevrectflip}, the green and blue paths share a horizontal segment in the top row. After the reverse rectangular flip, the green and blue paths do not share a horizontal segment in the top row. 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.


\begin{figure}[htbp]
\centering
    \input{Figures/rectflip-1}
\caption{A reverse rectangular flip on the blue path with respect to the red path}
\label{fig:revrectflip}
\end{figure} 


% An example of a reverse rectangular flip is given in Figure~\ref{fig:revrectflip}. 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 a reverse rectangular flip used in a family of paths is illustrated in Figure~\ref{fig:newrevrectflip}. Notice that in the left figure of Figure~\ref{fig:newrevrectflip}, the green and blue paths share a horizontal segment in the top row. After the reverse rectangular flip, the green and blue paths do not share a horizontal segment in the top row. 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.





\section{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. In this section we provide an example of how we use these tools to transform a family of paths while weakly increasing the combined length of increasing sequences they encode, proving \Cref{thm:main}.

\begin{Lemma}
\label{lem:startingvertices}
There exists a length-maximizing family of $ k $ lattice paths $P_1,\ldots,P_k$ where for each $i$, the path $P_i$ starts at the point $(1,k+1-i)$ in the matrix.
\end{Lemma}


% For example, take a look at family of paths in the left figure of Figure~\ref{fig:newrectflip}. Using a rectangular flip, we can modify this to a family of paths in the right figure of Figure~\ref{fig:newrectflip}. In this figure, notice that the three paths pass through the points $(1,3),(1,2),(1,1)$ respectively. 

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{fig:newleftshift1}.


%\begin{figure}[htbp]
%    \centering

    %\input{Figures/firstcolumn}
    %    \caption{}
    %    \label{fig:First column}
%\end{figure}

\bs

% 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 \newword{bounding path} $ L_i $ is given by:

% \begin{enumerate}[(a)]
% \item Walk horizontally from $ (1, k-i + 1) $ to $ % (i, k-i+1) $, then
% \item Alternate between $ (0,1) $ and $ (1,0) $ steps, starting with $ (0,1) $, until reaching $ (r-k+i-1, r-i+1) $, then
%  \item Walk horizontally to $ (q,r-i+1) $.
% \end{enumerate}



% that the corresponding points are on. The numbers on the top and bottom indicate the columns the corresponding points are on.


\begin{figure} 
\input{Figures/lowerboundpaths}
\caption{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 indices and the numbers on the top and bottom indicate the column indices.}
\label{fig:lowerboundpaths}
\end{figure}


\Cref{fig:lowerboundpaths} shows $ L_1, \dots, L_k $. These paths appear in \cite[Lemma 4.2]{TabStab} as well. If all rows of $ T $ have the same size, this family of paths is a length-maximizing family \cite[Lemma 4.2]{TabStab}. If the rows or $ T $ have different sizes, this may no longer be the case, and we have to allow our family of paths to be weakly above these in respective top to bottom order.


\begin{Lemma}
\label{lem:horizseg}
There exists a length-maximizing family of paths $P_1,\ldots,P_k$ such that $ P_i $ is weakly above $ L_i $ for all $ i $, and each $P_i$ contains the horizontal segment $(r - k + i - 1,r-i+1) - (q,r-i+1)$.
\end{Lemma}


\begin{figure}[htbp]
    \centering
     \scalebox{.7}{\input{Figures/newfig}}
     \qquad
     \scalebox{.7}{\input{Figures/newrectflip}}
     \qquad
     \scalebox{0.7}{\input{Figures/newrectflipcopy}}
     
     \caption{Running example: Start with a family of paths. Apply rectangular flip(s) to get a family satisfying Lemma~\ref{lem:startingvertices}. After this we may ignore the vertical segments in the first column to get a family satisfying the conditions of Lemma~\ref{lem:startingvertices}.}
     \label{fig:running1}
\end{figure}

\begin{figure}[htbp]
    \centering
     \scalebox{.7}{\input{Figures/newtopdown}}
     \qquad
     \scalebox{.7}{\input{Figures/newleftshift1}}
     \qquad
     \scalebox{.7}{\input{Figures/newleftshift2}}
     \caption{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.}
     \label{fig:running2}
\end{figure}

\begin{figure}[htbp]
     \centering
     \scalebox{0.7}{\input{Figures/newleftshift3}}
     \qquad
     \scalebox{0.7}{\input{Figures/newrectflip-1}}
     \qquad
     \scalebox{0.7}{\input{Figures/newrectflip-2}}
     % \scale
\caption{Running example: Apply left-shift on $P_3$. Lastly, apply reverse rectangular flip(s) to get a family satisfying Lemma~\ref{lem:horizseg}.}
\label{fig:running3}
\end{figure}







% For example, start with the family of paths in the left figure of Figure~\ref{fig:running1}. Using a rectangular flips at the beginning portion gives us the figure in the middle and then the figure on the right, where the paths satisfy the property of Lemma~\ref{lem:startingvertices}. Hence we may assume the paths start at $(1,1),(1,2),(1,3)$ as in the rightmost figure of Figure~\ref{fig:running1}.

% 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{fig:running2}. Next use the left-shifting on the top path $P_1$ to get the middle figure of Figure~\ref{fig:running2}. 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{fig:running3}. Lastly use reverse rectangular flips at the end to get the desired family of Lemma~\ref{lem:horizseg}.

%Lemma~\ref{lem:startingvertices} (powered by the rectangular flip lemma) tells us that we can modify the three paths so that each pass through $(1,3),(1,2),(1,1)$ as in the right side of Figure~\ref{fig:mainrectflip}. Now after using top-down switching Lemma allows us to label the paths from top-to-bottom as $P_1,P_2,P_3$ just like in Figure~\ref{fig:maintopdown}. 

Figures~\ref{fig:running1} through \ref{fig:running3} illustrates the the whole transformation process using the tools we have developed so far. From using the horizontal segments of the family we produced and Green's theorem, \ref{thm:main} follows:

% \begin{customthm}{\ref{thm:main}}
% For any skew standard tableaux $ T $ with $ r $ rows and weakly decreasing row sizes from top to bottom,
% \[
%     \stab(T) \le r.
% \]
% \end{customthm}

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?

\begin{Problem}
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$?
\end{Problem}

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 restrict attention to would be tableaux constructed from permutations as in \Cref{fig:permutationexample}. Given a permutation $w$, we can construct the skew tableau $T_w$ which has one entry per row and $w$ as its reading word. Then we can define $\stab(w)$ as $\stab(T_w)$, which give us a permutation statistic!

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

\begin{figure}
   \input{Figures/permutationexample}
   \caption{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$.}
\label{fig:permutationexample}
\end{figure}

\begin{Problem}[\cite{TabStab}]
 For a permutation $ w $, is there a way to find $ \stab(w) $ directly from the permutation or its recording tableau (that is, without constructing the rectification or using Greene's theorem)? What is the relationship between $ \stab(w) $ and $ Q(w) $?
\end{Problem}


\acknowledgments{
This research was primarily conducted during the 2020 Honors Summer 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.}

%\bibliographystyle{plain}    % (uses file "plain.bst")
%\usepackage[backend=bibtex]{biblatex}
%\bibliography{04Ahlbach.bib}

%% if you use biblatex then this generates the bibliography
%% if you use some other method then remove this and do it your own way
\printbibliography



\end{document}
