%% 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]{FPSAC2018}
\articlenumber{79}
%% 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[table]{xcolor}% http://ctan.org/pkg/xcolor
%\usepackage{hyperref}
\usepackage{ytableau}
\usepackage[noabbrev,capitalize]{cleveref}
%\usepackage{caption, subcaption}
\usepackage{blkarray}

\newtheorem{thm}{Theorem}[section]
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{defn}[thm]{Definition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{cor}[thm]{Corollary}

\crefname{defn}{Definition}{Definitions}
\crefname{lem}{Lemma}{Lemmata}
\crefname{thm}{Theorem}{Theorems}
\crefname{prop}{Proposition}{Propositions}
\crefname{cor}{Corollary}{Corollaries}
\crefname{fig}{Figure}{Figures}
\crefname{conj}{Conjecture}{Conjectures}

%% define your title in the usual way
\title[Properties of the Edelman-Greene bijection (extended
abstract)]{Properties of the Edelman-Greene bijection\\~(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{Svante
Linusson\thanks{\href{mailto:linusson@math.kth.se}{linusson@math.kth.se}.
Supported by the Swedish Research Council, grant
621-2014-4780.}\addressmark{1} \and Samu
Potka\thanks{\href{mailto:potka@kth.se}{potka@kth.se}. Supported by the
Swedish Research Council, grant 621-2014-4780.}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, KTH Royal Institute of
Technology, Stockholm, Sweden}

%% put the date of submission here
\received{November 14, 2017}

%% leave this blank until submitting a revised version
\revised{April 1, 2018}

%% 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{Edelman and Greene constructed a bijective correspondence between the reduced words of the reverse permutation in the symmetric group $S_n$ and standard Young tableaux of the staircase shape $(n-1, n-2, \dots, 1)$. Our motivation originates from random sorting networks, a line of research initiated by Angel, Holroyd, Romik and Vir\'ag. We reformulate one of their conjectures on the shapes of intermediate configurations coming from random sorting networks. Properties of the Edelman--Greene bijection restricted to 132-avoiding and 2143-avoiding permutations are presented. We also consider the Edelman--Greene bijection applied to non-reduced words.}

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

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Edelman--Greene correspondence, reduced words, Young tableaux, random sorting networks}

%% 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{79-Linusson-Potka.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}
In 1982, Richard Stanley conjectured, and later proved algebraically in
\cite{St84} that the number of maximal chains in the weak Bruhat order on
the symmetric group $S_n$ is equal to the number of staircase shape
standard Young tableaux. Motivated to find a bijective proof, Edelman and
Greene \cite{EG87} constructed such a correspondence based on the
celebrated Robinson--Schensted--Knuth (RSK) algorithm and Sch\"utzenberger's jeu de taquin. Much later, Little \cite{L03} found another bijection proved to be equivalent to the Edelman--Greene correspondence by Hamaker and Young in \cite{HY14}. 

Our motivation to study the Edelman--Greene (EG) bijection stems from
studies on \emph{random sorting networks} which are reduced words, $w =
w_1 \dots w_{\binom{n}{2}}$, of the \emph{reverse permutation} $n (n - 1)
\dots 2 1$ in $S_n$ chosen uniformly at random among all such words.

Let $s_i := (i \ i+1)$ denote \emph{swaps}, adjacent transpositions. Then $w_1 \dots w_k$ defines the permutation $s_{w_1} \cdots s_{w_k}$ in $S_n$ for any $1 \leq k \leq \binom{n}{2}$. 

Based on extensive computational evidence, Angel, Holroyd, Romik and Vir\'ag \cite{AHRV07} stated several tantalizing
conjectures on random sorting networks, a proof of which has recently been announced in \cite{D18}. One consequence would be that asymptotically the permutation matrices corresponding to the intermediate configurations coming from random sorting networks are supported on a family of ellipses, or, in other words, have their 1s inside an elliptic region of the matrix. In particular, at half-time the permutation matrix is supported on a disc. \cref{matrices} provides an illustration.
\begin{figure}[!htbp]
	\centering
	\includegraphics[scale=0.28]{quartertime.pdf}
	\includegraphics[scale=0.28]{halftime.pdf}
	\includegraphics[scale=0.28]{threequarterstime.pdf}
	\caption{The intermediate permutation matrices $M(\sigma_t)$ of a 1000-element random sorting network at times $t = \frac{1}{4}, \frac{1}{2}$ and $\frac{3}{4}$.}
	\label[fig]{matrices}
\end{figure}

\noindent To avoid technicalities, we just state the conjecture informally. See \cite[Conjecture 2]{AHRV07} for more details. Note that the permutation matrices therein are flipped vertically.
\begin{conj}[A consequence of {\cite[Conjecture 2]{AHRV07}}]\label[conj]{ellipseconseq}
	Let $w = w_1 \dots w_{\binom{n}{2}}$ be a random sorting network and $\sigma_t$ be the permutation defined by $w_1 \dots w_{\lfloor t\binom{n}{2} \rfloor}$. For all $t \in (0, 1)$, the limit shape of the scaled permutation matrix $(\frac{2i}{n} - 1, 1 - \frac{2\sigma(i)}{n})_{1 \leq i \leq n}$ is $A_t = \{(x, y) \in \mathbb{R}^2 : \sin^2(\pi t) - 2xy\cos(\pi t) - x^2 - y^2 = 0\}.$
\end{conj}

Our main result, \cref{frozendiagram}, is that the shape of the empty area (Rothe diagram) in the upper left corner of the permutation matrix
is exactly the same as a region in the insertion tableaux generated by the EG-bijection which we call the \emph{frozen region}. This leads to a reformulation of \cref{ellipseconseq} directly in terms of the EG-bijection.

As a side-product, we obtain some new observations and simple reproofs of previous results on the reduced words of 132-avoiding permutations. We also study sorting networks whose intermediate permutations are required to be 132-avoiding.

\cref{S:nonreduced} treats the Edelman--Greene insertion applied to non-reduced words. In particular, we study the sets of words yielding the same pairs of Young tableaux under the Edelman--Greene correspondence and define a natural partial order on this set which turns out to have some nice and surprising properties. There is a different generalization of the Edelman--Greene bijection for non-reduced words called Hecke insertion~\cite{BKSTY08}.

All proofs are omitted in this extended abstract of~\cite{LP18}.

\acknowledgements{
The authors thank the referees for their valuable comments. This paper
benefited from experimentation with \texttt{Sage}~\cite{sage}.}

\section{Preliminaries}
\subsection{Notation}
The notation $w \in \mathbb{N}^*$ means that $w$ is a word with positive
integer letters. We define len$(w)$ to be the length of $w$. The set of
reduced words of $\sigma \in S_n$ is denoted by $\mathcal{R}(\sigma)$,
and, for convenience, in the case of $\sigma = n( n - 1 ) \dots 2 1$ we use the abbreviation $\mathcal{R}(n)$.

It is important to note that we perform the compositions of swaps
$s_{w_i}$ corresponding to a word $w = w_1 \dots w_m$ from the left. As
an example, consider $S_4$ and the reduced word $1213$. Composing the
swaps $s_1 s_2 s_1 s_3$ from the left yields the permutation $3241$. In terms of permutation matrices, we would have, for example, 
\[\begin{blockarray}{cccc}
\mathbf{2} & \mathbf{1} & \mathbf{3} & \mathbf{4} \\
\begin{block}{(cccc)}
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
\end{block}
\BAmulticolumn{4}{c}{s_1} \\
\end{blockarray}\quad \quad  \begin{blockarray}{cccc}
\mathbf{2} & \mathbf{3} & \mathbf{1} & \mathbf{4} \\
\begin{block}{(cccc)}
0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 \\
\end{block}
\BAmulticolumn{4}{c}{s_1 s_2} \\
\end{blockarray}\quad \quad  \begin{blockarray}{cccc}
\mathbf{3} & \mathbf{2} & \mathbf{1} & \mathbf{4} \\ 
\begin{block}{(cccc)}
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
\end{block}
\BAmulticolumn{4}{c}{s_1 s_2 s_1} \\
\end{blockarray} \quad \quad  \begin{blockarray}{cccc}
\mathbf{3} & \mathbf{2} & \mathbf{4} & \mathbf{1} \\ 
\begin{block}{(cccc)}
0 & 0 & 0 & 1 \\
0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 \\
\end{block}
\BAmulticolumn{4}{c}{s_1 s_2 s_1 s_3} \\
\end{blockarray}\vspace{-\baselineskip}\]
where we can see that $s_i$ corresponds to swapping the columns $i$ and $i+1$.

Given a partition $\lambda$, $\mathrm{len}(\lambda)$ denotes its length. We define the Young diagram of $\lambda$ as $\{(i, j) \in \mathbb{N}^2 : 1 \leq i \leq \mathrm{len}(\lambda), 1 \leq j \leq \lambda_i\}$ and use the English notation, that is, draw it as a collection of square boxes corresponding to the \emph{cells} $(i, j)$ with $i$ increasing downwards and $j$ to the right. We let $\mathrm{SYT}(\lambda)$ be the set of standard Young tableaux of the shape $\lambda$.

\subsection{The Edelman--Greene bijection}
The Edelman--Greene correspondence is a bijection between $\mathcal{R}(n)$, that is, maximal chains in the weak Bruhat order on $S_n$, and standard Young tableaux of the \emph{staircase shape} $\mathrm{sc}_n = (n-1, n-2, \dots, 1)$.

\begin{defn}[The Edelman--Greene insertion]
	Suppose $P$ is a Young tableau with strictly increasing rows $P_1, \dots, P_{\ell}$ and $x_0 \in \mathbb{N}$ is to be inserted in $P$. The insertion procedure is as follows for each $0 \leq i \leq \ell$:\begin{itemize}
		\item If $x_i > z$ for all $z \in P_{i+1}$, place $x_i$ at the end of $P_{i+1}$ and stop.
		\item If $x_i = z'$ for some $z' \in P_{i+1}$, insert $x_{i+1} = z' + 1$ in $P_{i+2}$.
		\item Otherwise, $x_i < z$ for some $z \in P_{i+1}$, and we let $z'$ be the least such $z$, replace it by $x_i$ and insert $x_{i+1} = z'$ in $P_{i+2}$. In both this and the case above we say that $x_i$ \textbf{bumps} $z'$.
	\end{itemize} Repeat the insertion until for some $i$ the $x_i$ is inserted at the end of $P_{i+1}$ and the algorithm stops. This could be a previously empty row $P_{\ell + 1}$.
\end{defn}

We should mention that our definition of the insertion differs from that
of \cite{EG87}, where they also use the different name \emph{Coxeter--Knuth insertion}. However, using for example the proof of \cite[Lemma 6.23]{EG87}, one can show that the two definitions coincide for reduced words. Note also that except for a difference in handling equal elements bumping, the Edelman--Greene insertion and the RSK insertion are the same.
\begin{defn}[The Edelman--Greene correspondence]\label[defn]{egbij}
	Let $w = w_1 \dots w_i \dots w_m \in \mathbb{N}^*$. Initialize $P^{(0)} = \emptyset$.
	\begin{itemize}
		\item For each $1 \leq i \leq m$, insert $w_i$ in $P^{(i-1)}$ and denote the result by $P^{(i)}$.
	\end{itemize}
	Let $P^{(m)} := P(w)$ and let $Q(w)$ be the Young tableau obtained by setting $Q(w)_{i, j} = k$ for the unique cell $(i, j) \in P^{(k)}\setminus P^{(k-1)}$. Set $\mathrm{EG}(w) := Q(w)$.
\end{defn}

As an example, consider the reduced word $w = 321232$. Then the $P^{(k)}, 1 \leq k \leq 6$, form the following sequence
\[ \ytableausetup{smalltableaux, centertableaux}
\begin{ytableau}
\scriptstyle 3 \\
\none \\
\none
\end{ytableau}\ \longrightarrow\ \begin{ytableau}
\scriptstyle 2 \\
\scriptstyle 3 \\
\none
\end{ytableau}\ \longrightarrow\ \begin{ytableau}
\scriptstyle 1 \\
\scriptstyle 2\\
\scriptstyle 3
\end{ytableau}\ \longrightarrow\ \begin{ytableau}
\scriptstyle 1 & \scriptstyle 2\\
\scriptstyle 2\\
\scriptstyle 3
\end{ytableau}\ \longrightarrow\ \begin{ytableau}
\scriptstyle 1 & \scriptstyle 2 & \scriptstyle 3\\
\scriptstyle 2\\
\scriptstyle 3
\end{ytableau}\ \longrightarrow\ \begin{ytableau}
\scriptstyle 1 & \scriptstyle 2 & \scriptstyle 3\\
\scriptstyle 2 & \scriptstyle 3 \\
\scriptstyle 3
\end{ytableau}\] so that \[ P(321232) = \begin{ytableau} \scriptstyle 1 & \scriptstyle 2 & \scriptstyle 3\\
\scriptstyle 2 & \scriptstyle 3 \\
\scriptstyle 3 \end{ytableau}\ \mathrm{and}\ \mathrm{EG}(321232) := Q(321232) = \begin{ytableau} \scriptstyle 1 & \scriptstyle 4 & \scriptstyle 5\\
\scriptstyle 2 & \scriptstyle 6 \\
\scriptstyle 3 \end{ytableau}.\]

The tableau $P(w)$ is called the \emph{insertion tableau} and the tableau $Q(w)$ the \emph{recording tableau} since it records the growth of $P(w)$. Note that $P(w)$ and $Q(w)$ are always of the same shape for a fixed $w$. To state one of the main results of Edelman and Greene, let the \emph{reading word} $r(P)$ of an insertion tableau $P$ be the word obtained by collecting the entries of $P$ row by row from left to right starting from the bottom row.

\begin{thm}[{\cite[Theorem 6.25]{EG87}}]\label[thm]{egmain}
	The correspondence $w \mapsto (P(w), Q(w))$ is a bijection between $\cup_{\sigma \in S_n} \mathcal{R}(\sigma)$ and the set of pairs of tableaux $(P, Q)$ such that $P$ is row and column strict, $r(P)$ is reduced, $P$ and $Q$ have the same shape, and $Q$ is standard.
\end{thm}

Each of the $P^{(k)}$, $1 \leq k \leq m$, is going to contain some amount of entries such that $P^{(k)}_{i, j} = i + j - 1$. We call the region of $P^{(k)}$ formed by such entries the \emph{frozen region} and say that an insertion tableau is \emph{frozen} if the tableau is entirely a frozen region. The reason for using this terminology is that the frozen region does not change during the Edelman--Greene insertion. See $P$ in \cref{diagram}. The frozen region is white in the example. It turns out that $P(w)$ is always frozen when $w \in \mathcal{R}(n)$, and in fact, as we will see later in \cref{frozenp}, more generally if and only if $w \in \mathcal{R}(\sigma)$ with $\sigma$ 132-avoiding. Frozen tableaux have previously appeared in the literature on the combinatorics of K-theory under the name \emph{minimal increasing tableaux}, see~\cite{BS16} and the subsequent papers.

\begin{thm}[{\cite[Theorem 6.26]{EG87}}]\label[thm]{egstaircase}
	Suppose $w \in \mathcal{R}(n)$. Then $P(w)$ is frozen and $Q(w) \in \mathrm{SYT}(\mathrm{sc}_n)$. The map $\mathrm{EG}(w): w \mapsto Q(w)$ is a bijection from $\mathcal{R}(n)$ to $\mathrm{SYT}(\mathrm{sc}_n)$.
\end{thm}

Continuing in the setting of \cref{egstaircase}, if $w \in \mathcal{R}(n)$, the inverse to the Edelman--Greene bijection takes a very special form. To define it, we have to introduce Sch\"utzenberger's \emph{jeu de taquin}. For a good introduction, one could refer to~\cite{St99}, although the terminology is slightly different.

Let $T$ be a partially filled Young diagram with increasing rows and columns, and each entry $1 \leq k \leq \max_{(i, j) \in T} T_{i, j}$ occurring exactly once. The \emph{evacuation path} of $T$ is a sequence of cells $\pi_1, \dots, \pi_s$ such that \begin{itemize}
	\item $\pi_1 = (i_{\mathrm{max}}, j_{\mathrm{max}})$, the location of the largest entry of $T$,
	\item if $\pi_k = (i, j)$, $\pi_{k+1} = (i', j') \in T$ such that $T_{i', j'} = \max \{T_{i, j-1}, T_{i-1, j}\} > -\infty$ with the convention $T_{i, j} := -\infty$ for $(i, j) \not \in T$ and for unlabeled $(i, j) \in T$.
\end{itemize} 
Next, define the tableau $T^{\partial}$ by \begin{itemize}
	\item removing the label of $T_{\pi_1}$,
	\item and sliding the labels along the evacuation path: $T_{\pi_1} \leftarrow T_{\pi_2} \leftarrow \dots \leftarrow T_{\pi_s}$.
\end{itemize}
A single application of $\partial$ is called an \emph{elementary promotion}. Whenever a label $1 \leq \ell \leq T_{\pi_1}$ slides from some cell $(i, j)$ to $(i, j+1)$ (respectively $(i+1, j)$) in applying $\partial$ until all labels have been removed is referred to as a \emph{right slide} (respectively \emph{downslide}). For $w \in \mathcal{R}(n)$, the inverse to the Edelman--Greene bijection can then be defined as follows. 

\begin{thm}[{\cite[Theorem 7.18]{EG87}}]
	Suppose $Q \in \mathrm{SYT}(\mathrm{sc}_n)$. Apply $\partial$ until all labels have been cleared and say that $\pi_1^{(k)} = (i_k, j_k)$ is the first cell of the evacuation path $\pi^{(k)}$ for the $k$:th iteration. Then $\mathrm{EG}^{-1}(Q) = j_{\binom{n}{2}} \dots j_k \dots j_1$.
\end{thm}

Consider again the example following \cref{egbij}. Applying $\partial$ yields the sequence \[
Q = \begin{ytableau} \scriptstyle 1 & \scriptstyle 4 & \scriptstyle 5\\
\scriptstyle 2 & \scriptstyle 6 \\
\scriptstyle 3 \end{ytableau}\ \overset{\partial}{\longrightarrow}\ \begin{ytableau} \  & \scriptstyle 1 & \scriptstyle 5\\
\scriptstyle 2 & \scriptstyle 4 \\
\scriptstyle 3 \end{ytableau}\ \overset{\partial}{\longrightarrow}\ \begin{ytableau} \ & \ & \scriptstyle 1\\
\scriptstyle 2 & \scriptstyle 4 \\
\scriptstyle 3 \end{ytableau}\ \overset{\partial}{\longrightarrow}\ \begin{ytableau} \ & \ & \scriptstyle 1\\
\ & \scriptstyle 2 \\
\scriptstyle 3 \end{ytableau}\ \overset{\partial}{\longrightarrow}\ \begin{ytableau} \ & \ & \scriptstyle 1\\
\ & \scriptstyle 2 \\ \ \end{ytableau}\ \overset{\partial}{\longrightarrow}\ \begin{ytableau} \ & \ & \scriptstyle 1 \\ \ & \ \\ \ \end{ytableau}\ \overset{\partial}{\longrightarrow}\ \begin{ytableau} \ & \ & \ \\ \ & \ \\ \ \end{ytableau}. \] The largest entries are in the cells $\pi_1^{(1)} = (2, 2), \pi_1^{(2)} = (1, 3) , \pi_1^{(3)} = (2, 2), \pi_1^{(4)} = (3, 1), \pi_1^{(5)} = (2, 2)$ and $\pi_1^{(6)} = (1, 3)$. Hence, $\mathrm{EG}^{-1}(Q) = 321232$ as expected.

\section{Frozen regions and diagrams}
This section aims to show that \cref{ellipseconseq} can be formulated in terms of the frozen regions of insertion tableaux. Our goal is to prove that the shape of the frozen region of $P^{(k)}$ corresponds to the shape of one part of the so-called diagram of $\sigma = s_{w_1}s_{w_2} \dots s_{w_k}$. The (Rothe) \emph{diagram} $D(\sigma)$ of a permutation $\sigma$ is the set of cells left unshaded when we shade all the cells weakly to the east and south of 1-entries in the permutation matrix $M(\sigma)$. In particular, we consider the (possibly empty) connected component of $D(\sigma)$ containing $(1, 1)$ which we call the \emph{top-left component} of the diagram and denote by $D_{(1,1)}(\sigma)$. The top-left component induces a partition which is denoted by $\lambda(\sigma)$. Similarly, the frozen region of the insertion tableau of a reduced word induces a partition $\lambda_f(w)$ since by \cref{egmain} the tableau is row and column strict.
See \cref{diagram} for an example.

\begin{figure}[htbp!]
	\centering $D(\sigma) =
	\begin{ytableau}
		\scriptstyle 0 & \scriptstyle 0 & *(lightgray)\scriptstyle 1 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 0 \\
		\scriptstyle 0 & \scriptstyle 0 & *(lightgray)\scriptstyle 0 & \scriptstyle 0 & *(lightgray) \scriptstyle 1 & *(lightgray)\scriptstyle 0 \\
		\scriptstyle 0 & \scriptstyle 0 & *(lightgray)\scriptstyle 0 & \scriptstyle 0 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 1 \\
		\scriptstyle 0 & \scriptstyle 0 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 1 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 0 \\
		*(lightgray)\scriptstyle 1 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 0 \\
		*(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 1 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 0 & *(lightgray)\scriptstyle 0 \\
	\end{ytableau}\quad
	P = \begin{ytableau}
	\scriptstyle 1 & \scriptstyle 2 & *(lightgray) \scriptstyle 4\\
	\scriptstyle 2 & \scriptstyle 3 & *(lightgray) \scriptstyle 5\\
	\scriptstyle 3 & \scriptstyle 4\\
	\scriptstyle 4 & \scriptstyle 5\\
	\end{ytableau}$
	\caption{The diagram $D(\sigma)$ and $P = P(w)$ for any $w \in \mathcal{R}(\sigma)$ for $\sigma = 5 6 1 4 2 3$. The top-left component $D_{(1,1)}(\sigma)$ induces the partition $\lambda(\sigma) = (2, 2, 2, 2)$ and the frozen region of $P$ the partition $\lambda_f(w) = (2, 2, 2, 2)$.}
	\label[fig]{diagram}
\end{figure}
The following is our main result.
\begin{thm}\label[thm]{frozendiagram}
	If $w = w_1 \cdots w_{\ell}$ is reduced, then $\lambda(s_{w_1}\dots s_{w_{\ell}}) = \lambda_f(w)$. That is, the top-left component of the diagram of $s_{w_1}\dots s_{w_{\ell}}$ has the same shape as the frozen region of $P(w)$.
\end{thm}
\begin{proof} Omitted in this extended abstract. A key observation is that by \cite[Lemma 6.22 and Lemma 6.23]{EG87} it is enough to consider the case when $w$ is a reading word. \end{proof}

\begin{cor}\label[cor]{altconj}
	Let $w$ be a random sorting network. \cref{ellipseconseq}~holds if and only if for all $t \in (0, 1)$, the limit shape of the scaled frozen region $F_t = \{ (\frac{2j}{n}-1, 1-\frac{2i}{n}) \in \mathbb{R}^2: (i, j) \in \lambda_f(w_1\dots w_{\lfloor t \binom{n}{2}\rfloor})\}$ is determined by $\{(x, y) \in \mathbb{R}^2 : x \leq -\cos(\pi t), y \geq \cos(\pi t), \sin^2(\pi t) - 2xy\cos(\pi t) - x^2 - y^2 = 0\}.$
\end{cor}
\cref{altconj} follows from \cref{frozendiagram} by symmetries proved by Edelman and Greene. The interpretation of \cref{ellipseconseq} offered by \cref{altconj} is illustrated in \cref{comparison}.

\begin{figure}[htbp!]
	\centering
	\includegraphics[scale=0.33]{threequarterstime.pdf}
	\includegraphics[scale=0.33]{threequarterstimefrozen.pdf}
	\caption{A comparison at $t = \frac{3}{4}$ illustrating how the same shapes occur in both permutation matrices and frozen regions.}
	\label[fig]{comparison}
\end{figure}

\subsection{Pattern avoidance}

\cref{frozendiagram} also connects our work with the study of pattern-avoiding permutations. The set of 132-avoiding permutations of $[n]$, $S_n(132)$, is of particular interest here. The reason is an observation of Fulton.

\begin{lem}[{\cite[Proposition 9.19]{Fu92}}]\label[lem]{fulton132}
	Let $\sigma \in S_n$. Then $\sigma$ is 132-avoiding if and only if $D(\sigma) = D_{(1,1)}(\sigma)$.
\end{lem}

Since the length of a reduced word of $\sigma \in S_n$ is exactly the number of inversions in $\sigma$, that is $\mathrm{inv}(\sigma)$, \cref{fulton132} suggests we also need the following well-known fact: if $\sigma \in S_n$, then $|D(\sigma)| = \mathrm{inv}(\sigma)$. Note that by \cref{fulton132}, this can also be stated as $\lambda(\sigma) \vdash \mathrm{inv}(\sigma)$ for $\sigma \in S_n(132)$, meaning that $\lambda(\sigma)$ is a partition of $\mathrm{inv}(\sigma)$. We then obtain the characterization below.
\begin{cor}\label[cor]{frozenp}
	Let $w \in \mathcal{R}(\sigma)$. The insertion tableau $P(w)$ is frozen if and only if $\sigma$ is 132-avoiding. 
\end{cor}
Somewhat related, Tenner showed in \cite[Theorem 5.15]{Te17} that the set of 132-avoiding permutations of any length with $k$ inversions is in bijection with partitions of $k$. 

The proof method of \cite[Theorem 8.1, part 2]{EG87} would also lead to a proof of \cref{frozenp}. Moreover, it in fact allows us to prove something stronger. A permutation is said to be \emph{vexillary} if it is 2143-avoiding. 
We have the following result.
	\begin{thm}
		Let $w \in \mathcal{R}(\sigma)$. If $\sigma$ is vexillary, then the cell $(i, j)$ of $P(w)$ contains the entry $(i + j - 1) + k, k \geq 0$, if and only if $(i + k, j + k)$ is in $D(\sigma)$, where $k$ is the number of 1s north-west of $(i + k, j + k)$. Furthermore, if the set of cells $(i + k, j + k)$ for entries $(i + j - 1) + k, k \geq 0$, in cells $(i, j)$ in $P(w)$ is the diagram of a vexillary permutation, then $\sigma$ is vexillary.
	\end{thm}
\begin{proof} Omitted in this extended abstract. \end{proof}
We refer to \cref{diagram} for an example. Note that the entries with $k = 0$ are in the frozen region of $P(w)$.

The corollary below is mostly a reproof of consequences of results by Stanley \cite[Theorem 4.1]{St84}, and Edelman and Greene \cite[Theorem 8.1]{EG87}. We have added the observation that each shape $\lambda \subset \mathrm{sc}_n$ appears for exactly one $\sigma \in S_n(132)$ (and the consequent second bijection), which also follows from their works by properties of 132-avoiding permutations but is not discussed.
\begin{cor}\label[cor]{132av}
	If $\sigma$ is 132-avoiding, then $P(w)$ is frozen and has the same shape $\lambda(\sigma)$ for all $w \in \mathcal{R}(\sigma)$. Furthermore, each shape $\lambda \subset \mathrm{sc}_n$ appears for exactly one $\sigma \in S_n(132)$. Hence, $\mathrm{EG}(w): w \mapsto Q(w)$ defines a bijection \[\mathcal{R}(\sigma) \rightarrow \mathrm{SYT}(\lambda(\sigma)),\] and a bijection \[\bigcup\limits_{\sigma \in S_n(132)}\mathcal{R}(\sigma) \rightarrow \bigcup\limits_{\lambda \subset \mathrm{sc}_n} \mathrm{SYT}(\lambda).\]
\end{cor}

\begin{cor}
	Let $f^{\lambda} = |\mathrm{SYT}(\lambda)|$. Then
	\[\left\vert{\bigcup\limits_{\sigma \in S_n(p)}\mathcal{R}(\sigma)}\right\vert = \sum\limits_{\lambda \subset \mathrm{sc}_n} f^{\lambda},\] where $p \in \{132, 213\}.$
\end{cor}
This is implied by \cref{132av} and symmetries proved by Edelman and Greene. However, we have not been able to simplify the sum on the right-hand side.

Having in mind that the insertion tableau $P(w)$ becomes frozen for any reduced word $w$ of the reverse permutation, it could be interesting to restrict to \emph{132-avoiding sorting networks}, that is, those reduced words $w = w_1 \dots w_{\binom{n}{2}} \in \mathcal{R}(n)$ such that for any $1 \leq i \leq \binom{n}{2}$ the permutation $s_{w_1} \cdots s_{w_i}$ is 132-avoiding, or, equivalently, $P(w_1 \dots w_i)$ is frozen. This corresponds to considering the maximum length chains in the weak Bruhat order on $S_n$ restricted to 132-avoiding permutations. Bj\"orner and Wachs showed in \cite{BW97} that the restriction yields a sublattice isomorphic to the \emph{Tamari lattice} $\mathcal{T}_n$.

Using results from the next section, we can characterize 132-avoiding sorting networks in terms of \emph{shifted standard Young tableaux}, which was first proved by Fishel and Nelson~\cite[Theorem 4.6]{FN14}. These are standard Young tableaux for which each row $i$ can be shifted $(i-1)$ steps to the right without breaking the rule that the columns are increasing downwards. For example, \[\ytableausetup{centertableaux} \begin{ytableau}
\scriptstyle 1 & \scriptstyle 2 & \scriptstyle 4\\
\scriptstyle 3 & \scriptstyle 5 \\
\scriptstyle 6 
\end{ytableau} \longrightarrow\ \begin{ytableau}
\scriptstyle 1 & \scriptstyle 2 & \scriptstyle 4\\
\none & \scriptstyle 3 & \scriptstyle 5 \\
\none & \none & \scriptstyle 6 
\end{ytableau}.\]

\begin{prop}{\cite[Theorem 4.6]{FN14}}\label[prop]{132sort}
	Let $w = w_1 \dots w_{\binom{n}{2}}$ be a sorting network.\\ It is 132-avoiding if and only if $Q_{i, j} > Q_{i-1, j+1}$ for all $(i, j), (i-1, j + 1) \in Q$, or in other words, $Q$ is a shifted standard Young tableau of the shape $\mathrm{sc}_n$, where $Q = \mathrm{EG}(w)$.\\	
	It is 213-avoiding if and only if $Q_{i, j} < Q_{i-1, j+1}$ for all $(i, j), (i-1, j + 1) \in Q$ where $Q = \mathrm{EG}(w)$.
\end{prop}
\begin{proof} Omitted. We use \cref{zeroheight}. The second statement follows from the first by symmetries. \end{proof}
This subclass of sorting networks has also been studied by Schilling,
Thi\'ery, White and Williams in \cite{STWW17}. Note in particular the
observation that 132-avoiding sorting networks form a commutation class,
that is, each 132-avoiding sorting network is reachable from another by a
sequence of commutations: $s_i s_j \mapsto s_j s_i$ if $|i-j| > 1$. They
also observed that by \cite[Lemma 2.2]{STWW17} $n$-element 132-avoiding
sorting networks are in bijection with reduced words of the signed
permutation ${-(n-1)}\ {-(n-2)}\ \dots\ {-1}$ by $s_i \mapsto s_{i-1}$. 

Another characterization of 132-avoiding sorting networks is in terms of lattice words (also called lattice permutations or Yamanouchi words). A \emph{lattice word} of type $\lambda = (\lambda_1, \dots, \lambda_m)$ is a word $w = w_1 \dots w_m$ in which for each $2 \leq i+1 \leq m$ there is at least one $i$ before it, and $i$ occurs $\lambda_i$ times in $w$.
\begin{prop}\label[prop]{132lattice}
	Let $w = w_1 \dots w_{\binom{n}{2}}$ be a sorting network and let $\bar{w} = \bar{w}_1 \dots \bar{w}_k$, where $\bar{w}_i = n - w_i$ for $1 \leq i \leq k$. Then $w$ is 132-avoiding if and only if $w$ (or equivalently, $w^{\text{rev}}$) is a lattice word of type $\mathrm{sc}_n$.
	It is 213-avoiding if and only if $\bar{w}$ (or equivalently, $\bar{w}^{\text{rev}}$) is a lattice word of type $\mathrm{sc}_n$.
\end{prop}
\begin{proof} Omitted in this extended abstract. Similarly to \cref{132sort}, uses \cref{zeroheight}. The second statement follows from the first. \end{proof}

Fishel and Nelson proved the ``$\Rightarrow$''-direction of \cref{132lattice} in \cite[Corollary 4.5]{FN14}. Note that if $w = w_1 \dots w_k$ is a 132-avoiding sorting network, $w^{\text{rev}} = w_k \dots w_1$ is a 132-avoiding sorting network as well, since $Q(w^{\text{rev}})$ can be obtained by shifting $Q(w)$, reflecting the result anti-diagonally, complementing the entries: $m \mapsto \binom{n}{2} - m + 1$, and (un)shifting back.

We should emphasize that 132-avoiding and 312-avoiding sorting networks coincide.
\begin{prop}
	A sorting network is 132-avoiding if and only if it is 312-avoiding. Similarly, a sorting network is 213-avoiding if and only if it is 231-avoiding.
\end{prop}
\begin{proof} Omitted in this extended abstract. \end{proof}

The following enumerative result was, stated in another form, first obtained by Fishel and Nelson \cite[Corollary 3.4]{FN14} who enumerated the maximum length chains in $\mathcal{T}_n$ using a different set of methods. However, it is also a reformulation of \cref{heightenum} by \cref{132sort}.

\begin{cor}[{\cite[Corollary 3.4]{FN14}}]
	The number of 132-avoiding sorting networks of length $\binom{n}{2}$ is \[{\binom{n}{2}}!\frac{1!2!\dots(n-2)!}{1!3!\dots(2n-3)!}.\] The same holds for 213-avoiding sorting networks.
\end{cor}

\section{Non-reduced words} \label{S:nonreduced}
The Edelman--Greene bijection takes as its argument a reduced word. In order to understand the insertion better, we study its interaction with non-reduced words as well. Simultaneously, we obtain \cref{zeroheight} which can be used to prove \cref{132sort} and \cref{132lattice}.

Fix a standard Young tableau $Q$ and let $\mathcal{W}_Q = \{w \in \mathbb{N}^* :  \mathrm{EG}(w) = Q, P(w) \ \mathrm{frozen}\}$. Recall that by \cref{frozenp} the reduced words in the sets $\mathcal{W}_Q$ are reduced words of 132-avoiding permutations. Note that since the tableau $Q(w) = \textrm{EG}(w)$ has $\textrm{len}(w)$ entries, all words in $\mathcal{W}_Q$ have the same length.  Also, since the Edelman--Greene correspondence is a bijection between $\mathcal{R}(\sigma)$ and $\mathrm{SYT}(\lambda(\sigma))$ for $\sigma \in S_n(132)$, $\mathcal{W}_Q$ contains exactly one reduced word.

We define the poset $\mathcal{P}_Q = (\mathcal{W}_Q, \preceq)$ by setting $v \preceq w$ for $v, w \in \mathcal{W}_Q$ if $v_i \leq w_i$ for all $1 \leq i \leq \textrm{len}(v) = \textrm{len}(w)$. \cref{posets} contains some examples.

\begin{figure}[!h]
	\centering
	\includegraphics[scale=0.5]{poset1.pdf}
	\quad \quad
	\includegraphics[scale=0.5]{poset2.pdf}
	\quad \quad
	\includegraphics[scale=0.5]{poset13.pdf}
	\caption{Some examples of the 16 posets $\mathcal{P}_Q$ for $Q \in \mathrm{SYT}(\mathrm{sc}_4)$.}
	\label[fig]{posets}
\end{figure}

\subsection{Properties of \texorpdfstring{$\mathcal{P}_Q$}{PQ}}
%All proofs are omitted in this extended abstract, see~\cite{LP18}.
First, we extend a result of Edelman and Greene~\cite[Theorem
6.27]{EG87}. The \emph{descents} of a standard Young tableau $T$ are
entries $k$ such that if $T_{i, j} = k$, then $T_{i', j'} = k + 1$ for
$i' > i$, in other words $k + 1$ is strictly south of $k$. Let
$\mathrm{Des}(T) := \{k : k \text{ is a descent of } T\}$ be the set of
descents of $T$. Correspondingly, for $w \in \mathbb{N}^*$, let $\mathrm{Des}(w) := \{1 \leq i \leq \mathrm{len}(w) - 1 : w_i \geq w_{i+1}\}$.

\begin{prop}\label[prop]{descents}
	For all $w \in \mathcal{P}_Q$, $\mathrm{Des}(w) = \mathrm{Des}(Q)$.
\end{prop}

Suppose $Q$ is a standard Young tableau with $m$ entries. Define $c(Q) := c_1 \dots c_i \dots c_m$, where $c_i$ is the column of $i$ in $Q$ for $1 \leq i \leq m$. Then we say that $c(Q)$ is the \emph{column word} of $Q$. Note that this term is used differently by other authors. Column words of standard Young tableaux are, by their definition, lattice words.

\begin{prop}\label[prop]{topbottom}
	For $Q \in \mathrm{SYT(sc}_n)$, $\hat{0} = c(Q)$ is the unique bottom element in $\mathcal{P}_Q$.
\end{prop}

We conjecture that $\mathrm{EG}^{-1}(Q)$ is maximal in $\mathcal{P}_Q$. However, in general it is not the top element. As an example, take a reduced word of the reverse permutation in $S_6$ starting $4521343\dots$ and a non-reduced word $2431343\dots$ in the same poset $\mathcal{P}_Q$, both ending with the same subword.
The \emph{height} $h(P)$ of a poset $P$ is the length of its longest
chain. Let $[\cdot, \cdot]$ denote an interval in $\mathcal{P}_Q$ and
$\ell_Q :=  h([c(Q), \mathrm{EG}^{-1}(Q)])$. In other words, $\ell_Q$ is
the length of a maximum length chain from $c(Q)$ to
$\mathrm{EG}^{-1}(Q)$. Then $\ell_Q \leq \sum_{i = 1}^{\mathrm{len}(c(Q))} (\mathrm{EG}^{-1}(Q)_i - c(Q)_i)$. However, computations suggest that we have equality for $Q \in \mathrm{SYT(sc}_n)$.

\begin{conj}\label[conj]{height}
		For $Q \in \mathrm{SYT(sc}_n)$, we conjecture that
		$\mathrm{EG}^{-1}(Q)$ is a maximal element in
		$\mathcal{P}_Q$ and $\ell_Q = \sum_{i = 1}^{\mathrm{len}(c(Q))} (\mathrm{EG}^{-1}(Q)_i - c(Q)_i)$.
\end{conj}

Note that $\sum_{i = 1}^{\mathrm{len}(c(Q))} (\mathrm{EG}^{-1}(Q)_i -
c(Q)_i)$ is the amount of right slides when performing ${EG}^{-1}$ on
$Q$. Hence $\ell_Q\le \binom{n}{3}$ for the shape $\mathrm{sc}_n$. Let
$\eta_{n, i}$ denote the number of $Q \in \mathrm{SYT(sc}_n)$ such that
$\ell_Q = i, 0 \leq i \leq \binom{n}{3}$. The tableaux $Q$ contributing to $\eta_{n, 0}$ are simple to characterize. Then $\mathcal{P}_Q$ only contains the column word $c(Q)$.

\begin{prop}\label[prop]{zeroheight}
	If $Q \in \mathrm{SYT}(\mathrm{sc}_n)$, then $\ell_Q = 0$ if and only if $Q_{i, j} > Q_{i-1, j+1}$ for all $(i, j), (i-1, j + 1) \in Q$.
\end{prop}

The staircase standard Young tableaux in \cref{zeroheight} have been
enumerated previously and can also be reinterpreted in terms of several
other combinatorial objects, for example Gelfand--Tsetlin patterns (see the entry A003121 in the OEIS \cite{OEIS}).
\begin{cor}\label[cor]{heightenum}
	We have $\eta_{n, 0} = {\binom{n}{2}}!\frac{1!2!\dots(n-2)!}{1!3!\dots(2n-3)!}.$
\end{cor}

We end with some consequences of \cref{height}.
\begin{prop}\label[prop]{consequences} Assume the second part of \cref{height} holds and $Q \in \mathrm{SYT(sc}_n)$. Then\\	
	\indent a) $\ell_{Q^t} = \binom{n}{3} - \ell_{Q}$, so the sequence $\eta_{n, i}, 0 \leq i \leq \binom{n}{3}$, is symmetric,\\
    \indent b) the Sch\"utzenberger involution $S$ preserves $\ell_Q$,
    that is, $\ell_Q = \ell_{Q^S}$,\\
    \indent c) the number $\eta_{n, i}$ is even for all $n \geq 4$, $0 \leq i \leq \binom{n}{3}$,\\  
	\indent d) and $\ell_Q = \binom{n}{3}$ if and only if $Q_{i, j} < Q_{i-1, j+1}$ for all $(i, j), (i-1, j + 1) \in Q$.
\end{prop}

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