\documentclass[submission]{FPSAC2019}

\articlenumber{84}
\addbibresource{84.bib}

\usepackage[utf8]{inputenc}
\usepackage[table]{xcolor}% http://ctan.org/pkg/xcolor
%\usepackage{hyperref}
\usepackage{enumerate}
\usepackage{mathtools}
\usepackage{ytableau}
\usepackage{blkarray}
%\usepackage[noabbrev,capitalize]{cleveref}
\usepackage{graphicx}
\usepackage[pdf]{graphviz}
\usepackage{tkz-euclide}
\def\lineThickness{.7}
\tikzset{every picture/.append style={scale=.5,
thinLine/.style={line width=\lineThickness pt},
thickLine/.style={line width=2*\lineThickness pt,line join=round}},
fillGrey/.style={fill=black!30},
entry/.style={xshift=5mm,yshift=5mm,font=\footnotesize},
circled/.style={circle,draw,inner sep=0pt,minimum size=1em}
}
\usepackage{caption, subcaption}

%\usepackage{todonotes}
%\presetkeys%%
%	{todonotes}%
%	{inline,backgroundcolor=yellow}{}

%\newcommand\marginal[1]{\marginpar[\raggedleft\tiny #1]{\raggedright\tiny #1}}
%\newcommand\XXX{XXX \marginal{XXX}}
%\newcommand\SL{\marginal{SL}}	
%\newcommand\SP{\marginal{SP}}	
%\newcommand\RS{\marginal{RS}}	

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

\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}
\crefname{sec}{Section}{Sections}

\newcommand{\arxiv}[1]{\href{https://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\newcommand{\doi}[1]{\href{http://doi.org/#1}{\texttt{doi.org/#1}}}
\newcommand{\isbn}[1]{ISBN~#1}
\newcommand{\jstor}[1]{\href{http://www.jstor.org/stable/#1}{\texttt{www.jstor.org/stable/#1}}}
\newcommand{\oeis}[1]{\href{http://oeis.org/#1}{#1}}
%%%
\newcommand{\adv}{Adv.\ Math.}
\newcommand{\aam}{Adv.\ in Appl.\ Math.}
\newcommand{\aujc}{Australas.\ J.~Combin.}
\newcommand{\cupr}{Cambridge Univ.\ Press}
\newcommand{\eljc}{Electron.\ J.~Combin.}
\newcommand{\eujc}{European J.~Combin.}
\newcommand{\jac}{J.~Algebr.~Comb.}
\newcommand{\jcta}{J.~Combin.\ Theory Ser.~A}
\newcommand{\pams}{Proc.\ Amer.\ Math.\ Soc.}
\newcommand{\slc}{S{\'e}m.~Lothar.\ Combin.}
%%%
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\bop}[1]{\boldsymbol{\operatorname{#1}}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\e}{\bop{e}}
\newcommand{\matd}{\mathrm{d}}
\newcommand{\E}{\mathbb{E}}
\newcommand{\Fix}{\operatorname{Fix}}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\n}{\bop{n}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\norm}[1]{\left\| #1 \right\|_{\infty}}
\newcommand{\op}[1]{\operatorname{#1}}
\renewcommand{\P}{\mathbb{P}}
\newcommand{\pr}{\operatorname{pr}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\qbinom}[2]{\begin{bmatrix} #1 \\ #2 \end{bmatrix}_q}
\newcommand{\R}{\mathbb{R}}
\newcommand{\RSK}{\operatorname{RSK}}
\newcommand{\s}{\bop{s}}
\renewcommand{\S}{\mathfrak{S}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\sh}{\operatorname{sh}}
\newcommand{\shf}[1]{f_{\operatorname{sh}}^{#1}}

\newcommand{\shh}[1]{h_{\operatorname{sh}}^{#1}}
\newcommand{\skal}[1]{\langle #1 \rangle}
\newcommand{\ssyt}{\operatorname{SSYT}}
\newcommand{\syt}{\operatorname{SYT}}
\newcommand{\tab}{T}
\newcommand{\T}[1]{\mathcal{T}_{#1}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\w}{\bop{w}}
\newcommand{\wo}{w_{0}}
\newcommand{\Y}{\mathcal{Y}}
\newcommand{\yd}[1]{#1^{\operatorname{dg}}}
\newcommand{\shyd}[1]{#1^{\operatorname{sh}}}
\newcommand{\Z}{\mathbb{Z}}

\usepackage{chngcntr}
\counterwithin{table}{section}
% \counterwithin{figure}{section}

%\usepackage[backend=bibtex, maxbibnames=9,maxcitenames=2]{biblatex}
%\addbibresource{132avoiding_short.bib}

\title[On random shifted SYT and 132-avoiding sorting networks]{On random shifted standard Young tableaux and 132-avoiding sorting networks}

%% 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}, Samu Potka\thanks{\href{mailto:potka@kth.se}{potka@kth.se}. Supported by the Swedish Research Council grant 621-2014-4780.}\addressmark{1}, \and Robin Sulzgruber\thanks{\href{mailto:robinsul@kth.se}{robinsul@kth.se}.}\addressmark{2}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, KTH Royal Institute of Technology, Stockholm, Sweden. \\ \addressmark{2}Department of Mathematics and Statistics, York University, Toronto, Canada.}

%% put the date of submission here
\received{November 15, 2018}

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

\abstract{We study shifted standard Young tableaux (SYT). The limiting surface of uniformly random shifted SYT of staircase shape is determined, with the integers in the SYT as heights. This implies via properties of the Edelman--Greene bijection results about random 132-avoiding sorting networks, including limit shapes for trajectories and intermediate permutations. Moreover, the expected number of adjacencies in SYT is considered. It is shown that on average each row and each column of a shifted SYT of staircase shape contains precisely one adjacency.}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{Shifted standard Young tableaux, random 132-avoiding sorting networks}

\begin{document}
\maketitle

% \section{Introduction}
A shifted standard Young tableau (SYT) of staircase shape is an increasing filling of the shifted diagram of the partition $(n-1,\dots,2,1)$ with the integers $1,2,\dots,\binom{n}{2}$.
See \cref{shifted_example} for an example and \cref{S:background} for the exact definition.

Shifted diagrams and tableaux are important combinatorial objects that appear in various contexts.
In representation theory shifted Young diagrams correspond to projective characters of the symmetric group, and shifted tableaux lend themselves to being studied via RSK-type methods.
% ~\cite{Sagan:shifted_tableaux,Stembridge:shifted_tableaux}.
In the theory of partially ordered sets shifted diagrams alongside non-shifted Young diagrams and rooted trees form the three most interesting families of $d$-complete posets. %, which are in turn connected to fully commutative elements of Coxeter groups~\cite{Stembridge:fully_commutative,Proc:d_complete_poset,NaruseOkada}.
The most salient property of $d$-complete posets is the fact that their linear extensions (in our case shifted SYT) are enumerated by elegant product formulas.
Shifted diagrams also appear as order filters in the root poset of type $B_n$, and shifted SYT play an important role in the enumeration of reduced words of elements of the Coxeter group of type $B_n$.
% ~\cite{Haiman:dual_equivalence,Kraskiewicz:reduced_decompositions_hyperoctahedral}.
Moreover, as is topical in this paper, shifted SYT are also relevant to the study of certain reduced words in the symmetric group.
% Recently Elizalde and Roichman related shifted diagrams and tableaux to unimodal permutations~\cite{ER14}.


\begin{figure}[t]%[!htbp]
\begin{subfigure}{.45\textwidth}
% \[ \ytableausetup{centertableaux}\begin{ytableau}
% \scriptstyle 1 & \scriptstyle 2 & \scriptstyle 4 & \scriptstyle 5\\
% \none & \scriptstyle 3 & \scriptstyle 6 & \scriptstyle 7\\
% \none & \none & \scriptstyle 8 & \scriptstyle 9\\
% \none & \none & \none & \scriptstyle 10\\
% \end{ytableau}\]
\centering
\begin{tikzpicture}
% tableau
\begin{scope}
% vertical and horizontal lines
\draw[thinLine](3,1)--(4,1)(2,2)--(4,2)(1,3)--(4,3)(1,3)--(1,4)(2,2)--(2,4)(3,1)--(3,4);
% border
\draw[thickLine](0,3)--(1,3)--(1,2)--(2,2)--(2,1)--(3,1)--(3,0)--(4,0)--(4,4)--(0,4)--cycle;
% entries
\draw[entry](0,3)node{$1$}(1,3)node{$2$}(2,3)node{$4$}(3,3)node{$5$}(1,2)node{$3$}(2,2)node{$6$}(3,2)node{$7$}(2,1)node{$8$}(3,1)node{$9$}(3,0)node{$10$};
\end{scope}
\end{tikzpicture}
\caption{A shifted SYT of staircase shape.}
\label{shifted_example}
\end{subfigure}
\begin{subfigure}{.45\textwidth}
\centering
\includegraphics[width=.7\textwidth]{shape.png}
\bigskip
\caption{The limit shape of uniformly random shifted SYT of staircase shape.}
\label[fig]{shape}
\end{subfigure}
\caption{}
\end{figure}

\smallskip
The topics of this paper can be divided into three parts.

\smallskip
In \cref{S:shape} we study the surface obtained by viewing the integers in random SYT as heights.
The study of limit phenomena for partitions and tableaux is an active field of research combining methods from combinatorics, probability theory and analysis.
We refer to~\cite{Romik} for a general survey.
Shifted objects have been treated as well, for example Ivanov~\cite{Ivanov} proves a central limit theorem for the Plancherel measure on shifted diagrams.
In the present paper we determine the limiting surface for uniformly random shifted SYT of staircase shape, see \cref{shape} and \cref{limit_shape}.
The deduction of our results relies on a paper by Pittel and Romik~\cite{PR07} where the limit shape for random rectangular SYT is determined. In fact, we end up with the same variational problem, and the limit surface for shifted staircase SYT is the surface for square SYT restricted to a triangle. This analogy is in part explained by a combinatorial identity \eqref{eq:fL} relating shifted and non-shifted tableaux.
There are very few shapes for which the limit surface has been determined previously. As far as we know the only other case is that of staircase SYT, where again the same limit surface appears, but cut along a different diagonal~\cite{AHRV07}.
Results of this type have applications in other fields of mathematics such as geometric complexity theory~\cite{PS:skew_howe_duality}.

%Our setting results in the same variational problem that is solved in \cite{PR07} and by a combinatorial construction called {\emph shift-symmetric} and by modifying some of their lemmas we obtain the desired result.

\smallskip
Secondly, we study \emph{132-avoiding sorting networks}, which are by definition reduced words $w_1 \dots w_{\binom n2}$ of the reverse permutation such that $s_{w_1} \cdots s_{w_k}$ is 132-avoiding for all $1 \leq k \leq \binom n2$.
These objects have received considerable recent interest and also appear in different guises, for example as chains of maximum length in the Tamari lattice~\cite{BW97}.
Fishel and Nelson~\cite{FN14} showed that 132-avoiding sorting networks are in bijection with shifted SYT of staircase shape via the Edelman--Greene correspondence.
This has been rediscovered several times~\cite{STWW,DavisSagan,LP18}. They are also in bijection with reduced words of the signed permutation $(-(n-1), -(n-2), \dots, -1)$ via the shift $s_i \mapsto s_{i-1}$ as was remarked in~\cite[Sec.~1.3]{STWW}.
In \cref{S:permutations} %,S:trajectories} 
the Edelman--Greene bijection is used to transfer the limit shape of shifted SYT to determine the limit shapes of intermediate permutations (\cref{intermediate_permutations}) and trajectories (\cref{scaled_trajectory}) in random 132-avoiding sorting networks.
These results are motivated by a remarkable paper of Angel, Holroyd, Romik and Vir{\'a}g~\cite{AHRV07} that contains a number of tantalising conjectures about random sorting networks, now
proven by Dauvergne~\cite{D18}.
See \cref{S:background} for a description of some of them.
Our results are a parallel to their (former) conjectures restricted to a subclass of random sorting networks. 

We remark that the limit surface for shifted SYT of staircase shape contains complete information on the limit surface for SYT of square shape.
% Heuristically shifted SYT behave (asymptotically) like symmetric SYT while asymptotically most SYT are close to being symmetric.
This suggests the perhaps less intuitive idea that the relatively small subset of 132-avoiding sorting networks contains a lot of information on random sorting networks in general.  

\smallskip
The third set of results is obtained in \cref{S:adj} and concerns patterns in 132-avoiding sorting networks.
We first observe that adjacencies in a shifted SYT (that is, integers $i$ and $i+1$ in neighbouring cells) translate directly to adjacencies in a 132-avoiding sorting network 
(that is, $j$ and $j+1$ next to each other in the reduced word). \cref{expected_adjacencies} asserts that the expected number of adjacencies in each column and each row in a shifted SYT of staircase shape is exactly 1. The proof uses promotion 
and evacuation techniques very similar to the methods used by Schilling, Thi{\'e}ry, White and Williams~\cite{STWW} to derive results on Yang--Baxter moves (that is, patterns of the form $j(j\pm1)j$) in 132-avoiding sorting networks.
Related results on general sorting networks are due to Reiner~\cite{Reiner} and Tenner~\cite{Tenner}.

This is an extended abstract of~\cite{LPS18}.


\section{Background}\label{S:background}

In this section we fix notation and review some facts about partitions, tableaux and random sorting networks.
For $n\in\N$ let $[n]=\{1,\dots,n\}$.
Throughout this paper we denote $N=\binom{n}{2}$.


% \subsection{Partitions and tableaux}\label{S:tableaux}

\smallskip
A \emph{partition} is a weakly decreasing sequence $\lambda=(\lambda_1,\dots,\lambda_n)$ of positive integers.
If a partition is strictly decreasing it is called \emph{strict}.
The sum $\sum\lambda_i$ is called the \emph{size} of the partition $\lambda$ and is denoted by $\abs{\lambda}$.
The number of entries $\lambda_i$ is called the \emph{length} of the partition and is denoted by $\ell(\lambda)$.
Define the \emph{staircase} partition as $\Delta_n=(n-1,\dots,2,1)$.
The \emph{Young diagram} of a partition $\lambda$ is defined as the set
% \begin{equation*}
$\yd{\lambda}=\{(i,j):i\in[\ell(\lambda)],j\in[\lambda_i]\}$.
% \end{equation*}
The elements $(i,j)$ are indexed with matrix notation and typically referred to as \emph{cells} of $\lambda$.
% The \emph{conjugate partition} $\lambda'$ of the partition $\lambda$ is the partition corresponding to the Young diagram $\{(j,i):(i,j)\in\yd{\lambda}\}$.
Given a strict partition $\lambda$ we also define its \emph{shifted Young diagram} as
\begin{equation*}
\shyd{\lambda}=\{(i,j+i-1):i\in[\ell(\lambda)],j\in[\lambda_i]\}.
\end{equation*}
Thus the shifted Young diagram is obtained from the normal Young diagram by shifting rows to the right, row $i$ by $i-1$ steps.
% These definitions are illustrated in \cref{young_diagram}.

% \begin{figure}[t]
% \centering
% \begin{tikzpicture}
% % partition
% \begin{scope}
% % vertical and horizontal lines
% \draw[thinLine](0,1)--(1,1)(0,2)--(2,2)(0,3)--(4,3)(1,1)--(1,4)(2,2)--(2,4)(3,2)--(3,4)(4,3)--(4,4)(5,3)--(5,4);
% % border
% \draw[thickLine](0,0)--(1,0)--(1,1)--(2,1)--(2,2)--(4,2)--(4,3)--(6,3)--(6,4)--(0,4)--cycle;
% \end{scope}
% % shifted diagram
% \begin{scope}[xshift=10cm]
% % vertical and horizontal lines
% \draw[thinLine](3,1)--(4,1)(2,2)--(4,2)(1,3)--(5,3)(1,3)--(1,4)(2,2)--(2,4)(3,1)--(3,4)(4,2)--(4,4)(5,3)--(5,4);
% % border
% \draw[thickLine](0,3)--(1,3)--(1,2)--(2,2)--(2,1)--(3,1)--(3,0)--(4,0)--(4,2)--(5,2)--(5,3)--(6,3)--(6,4)--(0,4)--cycle;
% \end{scope}
% \end{tikzpicture}
% \caption{The Young diagram $\yd{\lambda}$ (left) and the shifted Young diagram $\shyd{\lambda}$ (right) of the strict partition $\lambda=(6,4,2,1)$ drawn in \emph{English convention}, that is, $(1,1)$ is the top left cell.
% We have $\abs{\lambda}=13$ and $\ell(\lambda)=4$.
% % and $\lambda'=(4,3,2,2,1,1)$.
% }
% \label[fig]{young_diagram}
% \end{figure}

% Let $u=(i,j)$ be a cell in the Young diagram of a partition $\lambda$.
% The \emph{hook-length} of $u$, denoted by $h_{\lambda}(u)$, is defined as the number of cells in the same row as $u$ that lie to the right of $u$ plus the number of cells in the same column as $u$ that lie weakly below $u$ (that is, including $u$ itself).
% Thus, $h_{\lambda}(u)=\lambda_i-j+\lambda_j'-i+1$.
% Given a cell $u=(i,j)$ in the shifted Young diagram of a strict partition, we define its \emph{shifted hook-length} $\shh{\lambda}(u)$ as the number of cells in the same row as $u$ that lie to the right of $u$, respectively in the same column and weakly below $u$, plus the number of cells in the $(i+j)$-th row of the shifted Young diagram.
% See \cref{hook_lengths}.

% \begin{figure}[t]
% \centering
% \begin{tikzpicture}
% % tableau
% \begin{scope}
% % vertical and horizontal lines
% \draw[thinLine](0,1)--(1,1)(0,2)--(2,2)(0,3)--(4,3)(1,1)--(1,4)(2,2)--(2,4)(3,2)--(3,4)(4,3)--(4,4)(5,3)--(5,4);
% % border
% \draw[thickLine](0,0)--(1,0)--(1,1)--(2,1)--(2,2)--(4,2)--(4,3)--(6,3)--(6,4)--(0,4)--cycle;
% % entries
% \draw[entry](0,3)node{$9$}(1,3)node{$7$}(2,3)node{$5$}(3,3)node{$4$}(4,3)node{$2$}(5,3)node{$1$}(0,2)node{$6$}(1,2)node{$4$}(2,2)node{$2$}(3,2)node{$1$}(0,1)node{$3$}(1,1)node{$1$}(0,0)node{$1$};
% \end{scope}
% % shifted tableau
% \begin{scope}[xshift=10cm]
% % vertical and horizontal lines
% \draw[thinLine](3,1)--(4,1)(2,2)--(4,2)(1,3)--(5,3)(1,3)--(1,4)(2,2)--(2,4)(3,1)--(3,4)(4,2)--(4,4)(5,3)--(5,4);
% % border
% \draw[thickLine](0,3)--(1,3)--(1,2)--(2,2)--(2,1)--(3,1)--(3,0)--(4,0)--(4,2)--(5,2)--(5,3)--(6,3)--(6,4)--(0,4)--cycle;
% % entries
% \draw[entry](0,3)node{$10$}(1,3)node{$8$}(2,3)node{$7$}(3,3)node{$6$}(4,3)node{$3$}(5,3)node{$1$}(1,2)node{$6$}(2,2)node{$5$}(3,2)node{$4$}(4,2)node{$1$}(2,1)node{$3$}(3,1)node{$2$}(3,0)node{$1$};
% \end{scope}
% \end{tikzpicture}
% \caption{The (shifted) Young diagram of $\lambda=(6,4,2,1)$ with the (shifted) hook-lengths filled into each cell.}
% \label[fig]{hook_lengths}
% \end{figure}

% Given a cell $u=(i,j)\in\Z^2$, define the \emph{north}, \emph{east}, \emph{south}, and \emph{west neighbour} of $u$ as
% \begin{equation*}
% \n u=(i-1,j),\quad
% \e u=(i,j+1),\quad
% \s u=(i+1,j)\quad\text{and}\quad
% \w u=(i,j-1),
% \end{equation*}
% respectively.
A \emph{tableau} of \emph{shape} $\yd{\lambda}$ is a map $\tab:\yd{\lambda}\to\Z$.
A tableau $\tab$ is called a \emph{standard Young tableau (SYT)} if $\tab:\yd{\lambda}\to[n]$ is a bijection and $\tab(i,j)<\tab(i,j+1)$ and $\tab(i,j)<\tab(i+1,j)$ whenever the respective cells lie in $\yd{\lambda}$.
Similarly a \emph{shifted standard Young tableau} of \emph{shape} $\shyd{\lambda}$ is a bijection $\tab:\shyd{\lambda}\to[n]$ such that $\tab(i,j)<\tab(i,j+1)$ and $\tab(i,j)<\tab(i+1,j)$ whenever the respective cells lie in the shifted Young diagram $\shyd{\lambda}$.
Let $\T{n}$ denote the set of shifted SYT of shape $\shyd{\Delta_n}$.
For example, \cref{shifted_example} shows a shifted standard Young diagram of shape $\shyd{\Delta_5}$.
The number $f^{\lambda}$ of SYT of shape $\lambda$ and the number $\shf{\lambda}$ of shifted SYT of shape $\shyd{\lambda}$ are given by nice product formulas involving the hook-lengths of these diagrams \cite{FRT1954,T52}.

% \begin{thm}[Hook-length formula \cite{FRT1954,T52}]\label[thm]{hlf}

% Let $\lambda$ be a partition.
% Then the number of SYT of shape $\lambda$ is given by 
% \begin{equation*}
% f_{\lambda}=\frac{\abs{\lambda}!}{\prod_{u\in\yd{\lambda}}h_{\lambda}(u)}.
% \end{equation*}
% If $\lambda$ is strict then the number of shifted SYT of shape $\shyd{\lambda}$ is given by
% \begin{equation*}
% \shf{\lambda}=\frac{\abs{\lambda}!}{\prod_{u\in\shyd{\lambda}}\shh{\lambda}(u)}.
% \end{equation*}
% \end{thm}

% The literature offers a variety of proofs of different flavours for \cref{hlf}, for example using hook-walks~\cite{GNW,Sagan:selecting_random_shifted} or by means of jeu de taquin~\cite{NPS,Fischer2002}.

% \subsection{Random 132-avoiding sorting networks}
\smallskip

For $i\in[n-1]$ let $s_i=(i,i+1)$ denote the $i$-th \emph{adjacent transposition}.
The \emph{reverse permutation} $\wo\in\S_n$ is defined by $\wo(i)=n-i+1$ for $i \in [n]$.
A \emph{reduced word} of $\wo$ is a word $w=w_1\cdots w_N$ in the alphabet $[n-1]$ such that $w_0=s_{w_1}\cdots s_{w_N}$.

% Note that we perform the compositions of transpositions $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 $1231$. 
% Composing  $s_1 s_2 s_3 s_1$ from the left yields the permutation $(3, 2, 4, 1)$. In terms of permutation matrices, we have 
% 	\[\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$.

Angel, Holroyd, Romik and Vir\'ag introduced \emph{$n$-element random sorting networks} as the set of reduced words of the reverse permutation $\wo\in\S_n$ equipped with the uniform probability measure in~\cite{AHRV07}.
In the same paper, Angel et al.~pose several striking conjectures about random sorting networks, which have now been proven by Dauvergne~\cite{D18}.

Suppose $w = w_1 \dots w_N$ is a sorting network.
Then $w_1 \dots w_k$ defines the \emph{intermediate permutation} $\sigma_k=s_{w_1} \cdots s_{w_k}\in\S_n$ for all $k\in[N]$.
One of the consequences of \cite[Thm.~2]{D18} (previously~\cite[Conj.~2]{AHRV07}) is that asymptotically the 1s in the permutation matrices of intermediate configurations of random sorting networks lie inside ellipses. In particular, at half-time the permutation matrix is supported on a disc. \cref{matrices} provides an illustration.
\begin{figure}[t]%[!htbp]
	\centering
	\includegraphics[width=0.25\textwidth]{quartertime.pdf}
	\includegraphics[width=0.25\textwidth]{halftime.pdf}
	\includegraphics[width=0.25\textwidth]{threequarterstime.pdf}
	\caption{The intermediate permutation matrices of $\sigma_{\lfloor \alpha N \rfloor}$ of a 1000-element random sorting network at times $\alpha = \frac{1}{4}, \frac{1}{2}$ and $\frac{3}{4}$.}
	\label[fig]{matrices}
\end{figure}

For $0\le \alpha\le 1$, \cite[Thm.~1]{D18} (previously~\cite[Conj.~1]{AHRV07}) states that the scaled trajectories defined by
$f_{w, i}(\alpha)
=2\sigma_{\alpha N}^{-1}(i)/n - 1$
% \begin{equation*}
% f_{w, i}(\alpha)
% =\frac{2\sigma_{\alpha N}^{-1}(i)}{n} - 1
% \end{equation*}
for $\alpha N\in\Z$, and by linear interpolation otherwise, converge to random sine curves. See \cref{trajectories}. \begin{figure}[!htbp]
	\centering
	\begin{subfigure}[b]{.49\textwidth}
	\centering
	\includegraphics[width=0.8\textwidth]{trajs.png}
	\caption{}
	\label[fig]{trajectories}
	\end{subfigure}
	\begin{subfigure}[b]{.49\textwidth}
	\centering
	\includegraphics[width=0.8\textwidth]{trajs_sh}
	\caption{}
	\label[fig]{traj_sh}
	\end{subfigure}
	\caption{Scaled trajectories in a random (a) ordinary and (b) 132-avoiding sorting network with 1000 elements.}
\end{figure}

The \emph{permutahedron} is an embedding of $\S_n$ into a sphere in $\mathbb{R}^n$ defined by $\sigma \mapsto (\sigma^{-1}(1), \dots, \sigma^{-1}(n))$.
% Every permutation $\sigma \in \S_n$ lies on the sphere
% \begin{equation*}
% \mathbb{S}^{n-2}
% =\Big\{z \in \R^n : \sum_{i = 1}^n z_i = \frac{n(n+1)}{2}
% % \Big\}\cap \Big\{z \in \R^n : 
% \text{ and }
% \sum_{i = 1}^n z_i^2 = \frac{n(n+1)(2n+1)}{6}\Big\}
% \,.
% \end{equation*}
Random sorting networks correspond to paths on the permutahedron.
The strongest theorem, \cite[Thm.~4]{D18} (previously \cite[Conj.~3]{AHRV07}), which implies both of the previous ones, states that these paths are close to great circles.

\smallskip
This paper considers similar questions restricted to \emph{132-avoiding sorting networks}, that is, those reduced words $w_1 \dots w_N$ of the reverse permutation in $\S_n$ such that $s_{w_1} \cdots s_{w_k}$ is 132-avoiding for all $k\in[N]$.
For background on pattern avoidance in permutations the reader is referred to \cite{K11}.
With a  \emph{random 132-avoiding sorting network}, we will refer to uniform distribution among all such networks of the same length.
% This restriction is very natural since it was proven by

The connection between 132-avoiding sorting networks and shifted SYT is the following. Let $w = w_1 \dots w_N$ be a 132-avoiding sorting network. Then, for $k \in [N]$, define a SYT $Q_{w_1 \dots w_k}$ by letting its $j$-th column consist of the indices $m \in [k]$ such that $w_m = j$. Furthermore, define a shifted SYT $Q_{w_1 \dots w_k}^{\rightarrow}$ by shifting the rows of $Q_{w_1 \dots w_k}$.
For example, the reduced word $w=1213423121$ corresponds to the shifted SYT in \cref{shifted_example}.
% \cref{eg} shows an example.

\begin{thm}[{\cite[Thm.~3.3 and Thm.~4.6]{FN14}}]
For all $n \in \N$, the map $w \mapsto Q_w^{\rightarrow}$ is a bijection from $n$-element 132-avoiding sorting networks to shifted SYT of shape $\Delta^{\sh}_n$. The map $w \mapsto Q_w$ agrees with the restriction of the Edelman--Greene correspondence to 132-avoiding sorting networks.
\end{thm}
The same bijection was also described in~\cite{LP18}, \cite[Fig.~4]{STWW} in terms of heaps, and \cite[Prop.~5.2]{DavisSagan} in terms of descent sets.
% 
%One such bijection is given by the Edelman--Greene bijection \cite{EG87}, which, as discussed in \cite{FN14} in the proof of Theorem 4.6 and in \cite{LP18}, in the case of 132-avoiding sorting networks reduces to the following:
% For example,
% \[\ytableausetup{centertableaux}
% w = 123121 \mapsto Q_w = \begin{ytableau}
% \scriptstyle 1 & \scriptstyle 2 & \scriptstyle 3\\
% \scriptstyle 4 & \scriptstyle 5 \\
% \scriptstyle 6\end{ytableau} \mapsto \begin{ytableau}
% \scriptstyle 1 & \scriptstyle 2 & \scriptstyle 3\\
% \none & \scriptstyle 4 & \scriptstyle 5 \\
% \none & \none & \scriptstyle 6\end{ytableau} = Q_w^{\rightarrow}.
% \]
% 
% \begin{figure}[b]
% \centering
% \begin{tikzpicture}
% % reduced word
% \draw[xshift=-5mm,yshift=15mm](0,0)node[anchor=east]{$w=1213423121$};
% % arrow
% \draw[xshift=5mm,yshift=15mm,thickLine,->](0,0)--(1,0);
% % tableau
% \begin{scope}[xshift=3cm]
% % vertical and horizontal lines
% \draw[thinLine](0,1)--(1,1)(0,2)--(2,2)(0,3)--(3,3)(1,1)--(1,4)(2,2)--(2,4)(3,3)--(3,4);
% % border
% \draw[thickLine](0,0)--(1,0)--(1,1)--(2,1)--(2,2)--(3,2)--(3,3)--(4,3)--(4,4)--(0,4)--cycle;
% % entries
% \draw[entry](0,3)node{$1$}(1,3)node{$2$}(2,3)node{$4$}(3,3)node{$5$}(0,2)node{$3$}(1,2)node{$6$}(2,2)node{$7$}(0,1)node{$8$}(1,1)node{$9$}(0,0)node{$10$};
% \end{scope}
% % arrow
% \draw[xshift=8cm,yshift=15mm,thickLine,->](0,0)--(1,0);
% % shifted tableau
% \begin{scope}[xshift=10cm]
% % vertical and horizontal lines
% \draw[thinLine](3,1)--(4,1)(2,2)--(4,2)(1,3)--(4,3)(1,3)--(1,4)(2,2)--(2,4)(3,1)--(3,4);
% % border
% \draw[thickLine](0,3)--(1,3)--(1,2)--(2,2)--(2,1)--(3,1)--(3,0)--(4,0)--(4,4)--(0,4)--cycle;
% % entries
% \draw[entry](0,3)node{$1$}(1,3)node{$2$}(2,3)node{$4$}(3,3)node{$5$}(1,2)node{$3$}(2,2)node{$6$}(3,2)node{$7$}(2,1)node{$8$}(3,1)node{$9$}(3,0)node{$10$};
% \end{scope}
% \end{tikzpicture}
% \caption{The Edelman--Greene correspondence for a 5-element 132-avoiding sorting network.}
% \label[fig]{eg}
% \end{figure}

Reversing a sorting network preserves the property of being 132-avoiding. See \cite{LP18} for a proof.
\begin{prop}\label{symmetry}
	A reduced word $w_1 \dots w_N$ is a 132-avoiding sorting network if and only if $w_N \dots w_1$ is.
\end{prop}

\section{The limit shape}\label{S:shape}
In this section we present a limit shape for random shifted SYT of staircase shape.
We may interpret a shifted SYT $\tab\in\T{n}$ as the graph of a function $L_{\tab}$
% \begin{equation*}
% L_{\tab}:\big\{(x,y)\in\R^2:0<x<y<1\big\}\to\R_{\geq0}
% \end{equation*}
by viewing the entries as heights.
% \begin{equation*}
% L_{\tab}(x,y)=\frac{1}{N}\tab\big(\ceil{(n-1)x},\ceil{(n-1)y}).
% \end{equation*}
Our main result, \cref{limit_shape}, states that with a suitable choice of scaling, the functions $L_{\tab^{(n)}}$ converge with probability 1 to the surface depicted in \cref{shape}, for a sequence of tableaux $\tab^{(n)}\in\T{n}$ chosen uniformly at random.
The proof of \cref{limit_shape} relies heavily on the work of Pittel and Romik~\cite{PR07}.
%, and O.~Angel et al.~\cite{AHRV07}.
In this extended abstract we only outline the ideas that lead to \cref{limit_shape}.

\smallskip
% Recall our conventions from \cref{S:tableaux}.
An important concept for connecting the shifted case to the setting of Pittel and Romik is the following definition.
Given a strict partition $\lambda$ define a partition $\Lambda$ by letting its Young diagram equal
\begin{equation*}
\yd{\Lambda}
=\big\{(i,j+1):(i,j)\in\shyd{\lambda}\big\}
\cup\big\{(j,i):(i,j)\in\shyd{\lambda}\big\}.
\end{equation*}
It is easy to see that this really is the Young diagram of a partition.
See \cref{shiftsymm}.
We call $\Lambda$ the \emph{shift-symmetric} partition corresponding to $\lambda$.
The motivation for this definition is the fact that shifted hook-lengths of the cells in $\shyd{\lambda}$ correspond to hook-lengths of cells in $\yd{\Lambda}$.

The following proposition is not new and can be obtained by extracting coefficients from an identity of symmetric functions found in \cite[Chap.~III, Sec.~8, Example~9.(b)]{Macdonald}.
Alternatively, one can give a simple proof using induction and the hook-length formula.

\begin{figure}[t]
\centering
\scalebox{0.9}{
\begin{tikzpicture}
\begin{scope}
\fill[fillGrey,xshift=1cm,yshift=2cm](0,3)--(1,3)--(1,2)--(2,2)--(2,1)--(3,1)--(3,0)--(4,0)--(4,2)--(5,2)--(5,3)--(6,3)--(6,4)--(0,4)--cycle;
% vertical and horizontal lines
\draw[thinLine](0,1)--(1,1)(0,2)--(2,2)(0,3)--(5,3)(0,4)--(5,4)(0,5)--(6,5)(1,1)--(1,6)(2,2)--(2,6)(3,2)--(3,6)(4,2)--(4,6)(5,4)--(5,6)(6,5)--(6,6);
% border
\draw[thickLine](0,0)--(1,0)--(1,1)--(2,1)--(2,2)--(5,2)--(5,4)--(6,4)--(6,5)--(7,5)--(7,6)--(0,6)--cycle;
\end{scope}
\end{tikzpicture}
}
\caption{The shift-symmetric partition $\Lambda=(7,6,5,5,2,1)$ of the strict partition $\lambda=(6,4,2,1)$.\vspace{-2ex}}
\label[fig]{shiftsymm}
\end{figure}

\begin{prop}\label[prop]{fL}
Let $\lambda$ be a strict partition and $\Lambda$ its shift-symmetric partition.
Then
\begin{equation}\label{eq:fL}
f^{\Lambda}=(\shf{\lambda})^2\cdot\binom{2\abs{\lambda}}{\abs{\lambda}}\cdot2^{-\ell(\lambda)}.
\end{equation}
\end{prop}

% \begin{figure}[t]
% \centering
% \begin{subfigure}{.2\textwidth}
% \begin{tikzpicture}
% % diagonal cells
% \begin{scope}
% \fill[fillGrey,xshift=1cm](0,3)--(1,3)--(1,2)--(2,2)--(2,1)--(3,1)--(3,0)--(4,0)--(4,4)--(0,4)--cycle;
% % vertical and horizontal lines
% \draw[thinLine](0,1)--(5,1)(0,2)--(5,2)(0,3)--(5,3)(1,0)--(1,4)(2,0)--(2,4)(3,0)--(3,4)(4,0)--(4,4);
% % border
% \draw[thickLine](0,0)--(5,0)--(5,4)--(0,4)--cycle;
% % hook-lengths
% \draw[entry]
% (0,3)node[circled]{$8$}(1,2)node[circled]{$6$}(2,1)node[circled]{$4$}(3,0)node[circled]{$2$}(4,3)node[circled]{$4$}(4,2)node[circled]{$3$}(4,1)node[circled]{$2$}(4,0)node[circled]{$1$};
% \end{scope}
% \end{tikzpicture}
% \caption{}
% \label[fig]{diag_hook_lengths}
% \end{subfigure}
% %%--------------------------------------------------
% \begin{subfigure}{.2\textwidth}
% \begin{tikzpicture}
% % other cells
% \begin{scope}
% \fill[fillGrey,xshift=1cm](0,3)--(1,3)--(1,2)--(2,2)--(2,1)--(3,1)--(3,0)--(4,0)--(4,4)--(0,4)--cycle;
% % vertical and horizontal lines
% \draw[thinLine](0,1)--(5,1)(0,2)--(5,2)(0,3)--(5,3)(1,0)--(1,4)(2,0)--(2,4)(3,0)--(3,4)(4,0)--(4,4);
% % border
% \draw[thickLine](0,0)--(5,0)--(5,4)--(0,4)--cycle;
% % hook-lengths
% \draw[entry](1,3)node{$7$}(2,3)node{$6$}(3,3)node{$5$}(2,2)node{$5$}(3,2)node{$4$}(3,1)node{$3$}(0,2)node{$7$}(0,1)node{$6$}(1,1)node{$5$}(0,0)node{$5$}(1,0)node{$4$}(2,0)node{$3$};
% \end{scope}
% \end{tikzpicture}
% \caption{}
% \label[fig]{other_hook_lengths}
% \end{subfigure}
% %%--------------------------------------------------
% \begin{subfigure}{.58\textwidth}
% \begin{tikzpicture}
% % before add cell
% \begin{scope}
% \fill[fillGrey,xshift=1cm,yshift=2cm](0,3)--(1,3)--(1,2)--(2,2)--(2,1)--(3,1)--(3,0)--(4,0)--(4,2)--(5,2)--(5,3)--(6,3)--(6,4)--(0,4)--cycle;
% % vertical and horizontal lines
% \draw[thinLine](0,1)--(1,1)(0,2)--(2,2)(0,3)--(5,3)(0,4)--(5,4)(0,5)--(6,5)(1,1)--(1,6)(2,2)--(2,6)(3,2)--(3,6)(4,2)--(4,6)(5,4)--(5,6)(6,5)--(6,6);
% % border
% \draw[thickLine](0,0)--(1,0)--(1,1)--(2,1)--(2,2)--(5,2)--(5,4)--(6,4)--(6,5)--(7,5)--(7,6)--(0,6)--cycle;
% % hook lengths
% \draw[entry](5,5)node{$3$}(5,4)node{$1$}(0,3)node{$8$}(1,3)node{$6$}(2,3)node[circled]{$4$}(3,3)node{$3$}(4,3)node[circled]{$2$}(2,5)node{$8$}(2,4)node{$6$}(2,2)node{$3$}(0,1)node{$3$}(1,1)node{$1$};
% \end{scope}
% % arrow
% \draw[->,thickLine,xshift=58mm](0,3)--(1,3);
% % after add cell
% \begin{scope}[xshift=75mm]
% \fill[fillGrey,xshift=1cm,yshift=2cm](0,3)--(1,3)--(1,2)--(2,2)--(2,1)--(3,1)--(3,0)--(4,0)--(4,1)--(5,1)--(5,3)--(6,3)--(6,4)--(0,4)--cycle;
% % vertical and horizontal lines
% \draw[thinLine](0,1)--(1,1)(0,2)--(3,2)(0,3)--(5,3)(0,4)--(6,4)(0,5)--(6,5)(1,1)--(1,6)(2,1)--(2,6)(3,2)--(3,6)(4,2)--(4,6)(5,3)--(5,6)(6,5)--(6,6);
% % border
% \draw[thickLine](0,0)--(1,0)--(1,1)--(3,1)--(3,2)--(5,2)--(5,3)--(6,3)--(6,5)--(7,5)--(7,6)--(0,6)--cycle;
% % hook-length
% \draw[entry](5,5)node{$4$}(5,4)node{$2$}(5,3)node{$1$}(0,3)node{$9$}(1,3)node{$7$}(2,3)node[circled]{$6$}(3,3)node{$4$}(4,3)node[circled]{$3$}(2,5)node{$9$}(2,4)node{$7$}(2,2)node{$4$}(2,1)node{$1$}(0,1)node{$4$}(1,1)node{$2$};
% \end{scope}
% \end{tikzpicture}
% \caption{}
% \label{add_cell}
% \end{subfigure}
% \caption{Matching the hook-lengths of a strict partition and its shift-symmetric partition.}
% \label[fig]{proof_HL}
% \end{figure}

% \begin{prob} The fact that all quantities in \eqref{eq:fL} have natural combinatorial interpretations suggests that there might be a purely bijective proof of \cref{fL} that relies only on the manipulation of tableaux.
% The authors are unaware of such a proof and it would be interesting to see one.
% \end{prob}

% The following two results provide an estimate for the probability that a fixed sub-diagram $\shyd{\lambda}$ of size $k$ of the shifted staircase contains precisely the entries $1,\dots,k$ in a shifted SYT of shape $\shyd{\Delta_n}$ chosen uniformly at random.

% Let $\T{n}$ denote the set of shifted SYT of shape $\shyd{\Delta_n}$ where $\Delta_n$ is the staircase partition of size $\binom{n}{2}$.
% Let $\P_n$ denote the uniform probability measure on $\T{n}$.

% Let $m,n\in\N$, $\Box=(n^m)$, and $\lambda$ be a partition.
% If $\yd{\lambda}\subseteq\yd{\Box}$ define a partition $\Box\setminus\lambda$ by setting
% \begin{equation*}
% \yd{(\Box\setminus\lambda)}
% =\big\{(m-i+1,n-j+1):(i,j)\in\yd{\Box}\setminus\yd{\lambda}\big\}
% \,.
% \end{equation*}
% Moreover, if $\lambda$ is strict and $\shyd{\lambda}\subseteq\shyd{\Delta_n}$, define a strict partition $\Delta_n\setminus\lambda$ by setting
% \begin{equation*}
% \shyd{(\Delta_n\setminus\lambda)}
% =\big\{(n-j,n-i):(i,j)\in\shyd{\Delta_n}\setminus\shyd{\lambda}\big\}.
% \end{equation*}

% \begin{figure}[b]
% \centering
% \begin{tikzpicture}
% \begin{scope}
% \fill[fillGrey,xshift=1cm](0,5)--(1,5)--(1,4)--(2,4)--(2,3)--(3,3)--(3,2)--(4,2)--(4,1)--(5,1)--(5,0)--(6,0)--(6,6)--(0,6)--cycle;
% \draw[thinLine](0,0)grid(7,6);
% \draw[thickLine](0,0)rectangle(7,6)(1,0)--(1,1)--(2,1)--(2,2)--(5,2)--(5,4)--(6,4)--(6,5)--(7,5);
% \end{scope}
% \end{tikzpicture}
% \caption{We have $\Box_7=(7^6)$, $\lambda=(6,4,2,1)$, $\Lambda=(7,6,5,5,2,1)$, and $\Box_7\setminus\Lambda=(6,5,2,2,1)$ is the shift-symmetric partition of $\Delta_7\setminus\lambda=(5,3)$.}
% \label[fig]{shift_symm_rect}
% \end{figure}

% \begin{lem}\label[lem]{prob}
% Let $n\in\N$, $\lambda$ be a strict partition of size $k$ with $\lambda_1<n$, and let $\P_n$ denote the uniform probability measure on $\T{n}$.
% % Then the probability that $t(\lambda)=[k]$, where $t$ is a shifted SYT of shape $\shyd{\Delta}$ chosen uniformly at random, is given by
% Then
% \begin{equation}\label{eq:prob}
% \P_n\big(\tab\in\T{n}:\tab(\shyd{\lambda})=[k]\big)
% =\binom{N}{k}^{-1}\cdot\sqrt{\binom{2N}{2k}\frac{f_\Lambda\cdot f_{\Box_n\setminus \Lambda}}{f_{\Box_n}}}
% \,,
% \end{equation}
% where $\Lambda$ and $\Box_n$ are the shift-symmetric partitions corresponding to $\lambda$ and $\Delta_n$ respectively.
% % , and $\Box_n\setminus\Lambda$, being the complement of a partition inside a rectangle, corresponds to a Young diagram itself after a rotation.
% \end{lem}

% The right hand side of \eqref{eq:prob} is essentially the same as \cite[Eq.~(7)]{PR07}.

\cref{fL} allows us to transfer many of the results of Pittel and Romik to the shifted staircase.
The first important step is to obtain an analogue of \cite[Lem.~1]{PR07}, which introduces a \emph{hook-integral} in order to estimate the probability that a fixed subdiagram $\shyd{\lambda}\subseteq\shyd{\Delta_n}$ contains precisely the integers $1,\dots,k$ in a random SYT of shape $\shyd{\Delta_n}$ chosen uniformly at random.

\smallskip
Fix $n$ and let $\lambda$ be a partition with $\abs{\lambda}=k$.
Define a function $\gamma_{\lambda}:\R_{>0}\to\R_{\geq0}$ by
$\gamma_{\lambda}(x)=\lambda_{\ceil{(n-1)x}}/(n-1)$,
% \begin{equation*}
% \gamma_{\lambda}(x)=\frac{1}{n-1}\lambda_{\ceil{(n-1)x}}
% \,,
% \end{equation*}
where by convention $\lambda_i=0$ for $i>\ell(\lambda)$.
See \cref{shifted_russian}.
% It is often more convenient to work with rotated coordinates
% \begin{equation}\label{eq:uv}
% u=\frac{x-y}{\sqrt{2}},\qquad
% v=\frac{x+y}{\sqrt{2}}.
% \end{equation}
% Define $g_{\lambda}:\R\to\R_{\geq0}$ by
% \begin{equation*}
% g_{\lambda}(u)
% =\sup\big\{v:v=\abs{u}\text{ or }x>0,y\leq\gamma_{\lambda}(x)\big\}
% \,.
% \end{equation*}
% The function $g_{\lambda}$ is just a rotated version of the function $\gamma_{\lambda}$, however, it has the advantage of being $1$-Lipschitz while $\gamma_{\lambda}$ is only non-increasing.
% Note that
% \begin{equation*}
% \int_{0}^{\infty}\gamma_{\lambda}(x)\matd x
% =\int_{\R}g_{\lambda}(u)-\abs{u}\matd u
% =\frac{k}{(n-1)^2}
% \,.
% \end{equation*}
% Note that $g_{\lambda}$ describes the boundary of the scaled Young diagram $\yd{\lambda}$ in \emph{Russian convention}.
% If the partition $\lambda$ is strict we define $G_{\lambda}:\R_{\leq0}\to\R_{\geq0}$ by
% \begin{equation*}
% G_{\lambda}(u)
% =\sup\Big\{v:v=\abs{u}\text{ or }x>0,y\leq\gamma_{\lambda}(x)+\frac{\ceil{(n-1)x}-1}{(n-1)}\Big\}
% \,.
% \end{equation*}
% The function $G_{\lambda}$ describes the boundary of the scaled shifted Young diagram $\shyd{\lambda}$.
% See \cref{shifted_russian}.

% \begin{figure}[t]
% \centering
% \begin{tikzpicture}
% % gamma
% \begin{scope}
% \draw[thinLine,black!30](0,1)--(3,1)(0,2)--(2,2)(0,3)--(2,3)(0,4)--(1,4)(0,5)--(1,5)(1,0)--(1,6)(2,0)--(2,4)(3,0)--(3,2)(4,0)--(4,1);
% \draw[thinLine,->](0,0)--(0,7)node[anchor=south]{$y$};
% \draw[thinLine,->](0,0)--(7,0)node[anchor=west]{$x$};
% \draw[thickLine,blue](0,6)--(1,6)(1,4)--(2,4)(2,2)--(3,2)(3,1)--(4,1)(4,0)--(6,0);
% \draw(4,0)node[anchor=north]{$\frac{4}{n-1}$};
% \draw[blue](3,3)node{$\gamma_{\lambda}$};
% \end{scope}
% % g
% \begin{scope}[xshift=16cm,scale=.7071]
% \draw[thinLine,black!30](-7,7)--(0,0)--(7,7)(-5,5)--(-4,6)(-4,4)--(-3,5)--(1,1)(-3,3)--(-1,5)(-2,2)--(0,4)--(2,2)(-1,1)--(2,4)--(3,3);
% \draw[thinLine,->](0,0)--(0,9)node[anchor=south]{$v$};
% \draw[thinLine,->](-8,0)--(8,0)node[anchor=west]{$u$};
% \draw[thinLine,dashed]
% (-6,0)node[anchor=north]{$-\frac{3\sqrt{2}}{n-1}$}--(-6,6)
% (4,0)node[anchor=north]{$\frac{2\sqrt{2}}{n-1}$}--(4,4);
% \draw[thickLine,blue](-7,7)--(-6,6)--(-5,7)--(-3,5)--(-2,6)--(0,4)--(1,5)--(2,4)--(3,5)--(4,4)--(7,7);
% \draw[blue](2,6)node{$g_{\lambda}$};
% \end{scope}
% % % G
% % \begin{scope}[xshift=25cm,scale=.7071]
% % \draw[thinLine,black!30]
% % (-7,7)--(0,0)--(1,1)
% % (-5,5)--(-4,6)--(1,1)
% % (-4,4)--(-2,6)--(1,3)--(-1,1)
% % (-3,3)--(1,7)--(0,8)
% % (-2,2)--(1,5)--(-1,7)
% % ;
% % \draw[thinLine,->](0,0)--(0,9)node[anchor=south]{$v$};
% % \draw[thinLine,->](-8,0)--(3,0)node[anchor=west]{$u$};
% % \draw[thinLine,dashed]
% % (-6,0)node[anchor=north]{$-\frac{3\sqrt{2}}{n}$}--(-6,6)
% % (0,0)node[anchor=north]{$0$};
% % \draw[thickLine,blue](-7,7)--(-6,6)--(-5,7)--(-4,6)--(-3,7)--(-2,6)--(0,8);
% % \draw[blue](-4,8)node{$G_{\lambda}$};
% % \end{scope}
% \end{tikzpicture}
% \caption{The functions $\gamma_{\lambda}$ and $g_{\lambda}$ for the partition $(6,4,2,1)$.}
% \label[fig]{russian}
% \end{figure}

\begin{figure}[]
\centering
\begin{subfigure}[b]{.4\textwidth}
\begin{tikzpicture}
% gamma
\begin{scope}
\draw[thinLine,black!30](0,1)--(3,1)(0,2)--(2,2)(0,3)--(2,3)(0,4)--(1,4)(0,5)--(1,5)(1,0)--(1,6)(2,0)--(2,4)(3,0)--(3,2)(4,0)--(4,1);
\draw[thinLine,->](0,0)--(0,7)node[anchor=south]{$y$};
\draw[thinLine,->](0,0)--(7,0)node[anchor=west]{$x$};
\draw[thickLine,blue](0,6)--(1,6)(1,4)--(2,4)(2,2)--(3,2)(3,1)--(4,1)(4,0)--(6,0);
\draw(4,0)node[anchor=north]{$\frac{4}{n-1}$};
\draw[blue](3,3)node{$\gamma_{\lambda}$};
\end{scope}
% G
% \begin{scope}[scale=.7071]
% \draw[thinLine,black!30](-8,8)--(0,0)--(1,1)(-5,5)--(-4,6)--(1,1)(-4,4)--(-2,6)--(1,3)--(-1,1)(-3,3)--(1,7)--(0,8)(-2,2)--(1,5)--(-1,7);
% \draw[thinLine,->](0,0)--(0,9)node[anchor=south]{$v$};
% \draw[thinLine,->](-9,0)--(3,0)node[anchor=west]{$u$};
% \draw[thinLine,dashed]
% (-6,0)node[anchor=north]{$-\frac{3\sqrt{2}}{n-1}$}--(-6,6)
% (0,0)node[anchor=north]{$0$};
% \draw[thickLine,blue](-8,8)--(-6,6)--(-5,7)--(-4,6)--(-3,7)--(-2,6)--(0,8);
% \draw[blue](-4,8)node{$G_{\lambda}$};
% \end{scope}
\end{tikzpicture}
% \caption{The function $G_{\lambda}$ for the partition $(6,4,2,1)$.}
\caption{The function $\gamma_{\lambda}$ for $\lambda = (6,4,2,1)$.\\ \phantom{jim}}
\label[fig]{shifted_russian}
\end{subfigure}
\hspace{2em}
\begin{subfigure}[b]{.5\textwidth}
\centering
\includegraphics[width=0.62\textwidth]{g_alpha_full.pdf}
\caption{The curves $v = \tilde{g}_{\alpha}(u)$ for $\alpha = 0.05, 0.1, \dots, 0.95$.}
\label[fig]{g_alpha}
\end{subfigure}
\caption{}
\end{figure}

\begin{lem}\label[lem]{variational_problem}
Let $\alpha\in(0,1)$, $k=k(n)$ be a sequence such that $k/N\to\alpha$ as $n\to\infty$, and let $\P_n$ denote the uniform probability measure on $\T{n}$.
Then, as $n\to\infty$,
\begin{equation*}
\P_n\big(\tab\in\T{n}:\tab(\shyd{\lambda})=[k]\big)=
\exp\Big(-\big(1+o(1)\big)\frac{n^2}{2}\big(I(\gamma_{\Lambda})+H(\alpha)+C\big)\Big)
\end{equation*}
uniformly over all strict partitions $\lambda$ of $k$ with $\lambda_1<n$, where 
\begin{align*}
% \begin{equation*}
% \begin{split}
C&=\frac{3}{2}-2\ln2,&
I(\gamma)&=\int_0^1\int_0^1\ln\abs{\gamma(x)+\gamma^{-1}(y)-x-y}\matd y\matd x,\\
H(\alpha)&=-\alpha\ln(\alpha)-(1-\alpha)\ln(1-\alpha),&
\gamma^{-1}(y)&=\inf\{x\in[0,1]:\gamma(x)\leq y\}
% \gamma_{\Lambda}(x)&=\frac{1}{n}\Lambda_{\ceil{nx}}
\,,
% \end{split}
% \end{equation*}
\end{align*}
and $\Lambda$ denotes the shift-symmetric partition of $\lambda$.
\end{lem}

Results of the type of \cref{variational_problem} lead to a so-called large deviation principle, which heuristically can be understood as follows:
Suppose that $n$ is large, and let $\lambda$ be the strict partition of size $k=\floor{\alpha N}$ with shift-symmetric partition $\Lambda$ minimising $I(\gamma_{\Lambda})$.
Let $\mu$ be another strict partition of size $k$ with shift-symmetric partition $M$, which deviates from $\lambda$, meaning that $I(\gamma_M)>I(\gamma_{\Lambda})+\varepsilon$.
Then the probability that $\mu$ contains the numbers $1,\dots,k$ in a random shifted SYT $\tab\in\T{n}$ is exponentially smaller (by a factor $\exp(-\varepsilon n^2/2)$) than the probability that $\lambda$ contains these numbers.
Hence the shape formed by the entries $1,\dots,k$ in a random shifted SYT will be close to the minimising partition $\lambda$ with high probability.
% Suppose that $\lambda$ is the strict partition of size $k$ with $\lambda_1<n$ such that its shift-symmetric partition $\Lambda$ minimises the integral $I(\gamma_{\Lambda})$.
% If $\mu$ is a different strict partition of size $k$ with $\mu_1<n$ then by \cref{variational_problem} the probability that $\mu$ contains the numbers $1,\dots,k$ in a random shifted SYT $\tab\in\T{n}$ decays exponentially as $\mu$ deviates from $\lambda$.
% This means that the shape formed by the entries $1,\dots,k$ in a random shifted SYT will be close to the minimising partition $\lambda$ with high probability.
This leads to the variational problem of identifying the function $\gamma$ in a certain search space depending on $\alpha$ that minimises the integral $I(\gamma)$.

A function
$g:[-\sqrt{2}/2,\sqrt{2}/2]\to[0,\sqrt{2}]$
% \begin{equation*}
% \end{equation*}
is called \emph{$\alpha$-admissible} if it is $1$-Lipschitz and satisfies
\begin{equation*}
\int_{-\sqrt{2}/2}^{\sqrt{2}/2} \left(g(u)-\abs{u}\right)\matd u=\alpha
\,.
\end{equation*}
As is explained in \cite[Sec.~2.2]{PR07} our problem is equivalent the following formulation:
For each $\alpha\in(0,1)$ find the unique $\alpha$-admissible function $g$ which is symmetric, that is, $g(-u)=g(u)$, and minimises the integral
\begin{equation}\label{eq:variational_K}
K(g)=-\frac{1}{2}
\int_{-\sqrt{2}/2}^{\sqrt{2}/2}
\int_{-\sqrt{2}/2}^{\sqrt{2}/2}
g'(s)g'(t)\ln\abs{s-t}\matd s\matd t
\,.
\end{equation}
The only difference between our situation and the situation in \cite{PR07} is the fact that our search space is a subset of theirs since we require that $\Lambda$ is the shift-symmetric partition of a strict partition.
In \cite[Sec.~2 and~3]{PR07} Pittel and Romik show that the variational problem \eqref{eq:variational_K} without the assumption $g(-u)=g(u)$ has the unique solution $\tilde{g}_{\alpha}$.
%  given by
% \begin{equation}\label[eq]{g_tilde}
% \tilde{g}_{\alpha}(u)=
% \begin{cases}
% g_{\alpha}(u)&\quad\text{if }\abs{u}\leq\sqrt{2\alpha(1-\alpha)},\\
% \abs{u}&\quad\text{if }\sqrt{2\alpha(1-\alpha)}\leq\abs{u}\leq\sqrt{2}/2,
% \end{cases}
% \end{equation}
% where
% \begin{equation*}
% g_{\alpha}:[-\sqrt{2\alpha(1-\alpha)},\sqrt{2\alpha(1-\alpha)}]\to\R
% \end{equation*}
% is defined as
% \begin{equation*}
% g_{\alpha}(u)
% =\frac{2u}{\pi}\tan^{-1}\Bigg(\frac{(1-2\alpha)u}{\sqrt{2\alpha(1-\alpha)-u^2}}\Bigg)
% +\frac{\sqrt{2}}{\pi}\tan^{-1}\Bigg(\frac{\sqrt{2(2\alpha(1-\alpha)-u^2)}}{1-2\alpha}\Bigg)
% \,,
% \end{equation*}
% if $0<\alpha<1/2$, and
% % \begin{equation*}
% % \begin{split}
% % g_{\alpha}(u)
% % &=\sqrt{2}-\frac{2u}{\pi}\tan^{-1}\Bigg(\frac{(1-2\alpha)u}{\sqrt{2\alpha(1-\alpha)-u^2}}\Bigg)
% % \\&\qquad
% % -\frac{\sqrt{2}}{\pi}\tan^{-1}\Bigg(\frac{\sqrt{2(2\alpha(1-\alpha)-u^2)}}{1-2\alpha}\Bigg)
% % \end{split}
% % \end{equation*}
% % if $\frac{1}{2}<\alpha\leq 1$, and
% \begin{equation*}
% \tilde{g}_{\alpha}(u)=\sqrt{2}-\tilde{g}_{1-\alpha}(u)
% \end{equation*}
% for $1/2<\alpha<1$, and
% \begin{equation*}
% \tilde{g}_{1/2}(u)
% =\frac{\sqrt{2}}{2}
% \,.
% \end{equation*}
The family of functions $\tilde{g}_{\alpha}$ is illustrated in \cref{g_alpha}. Since this solution already exhibits the additional symmetry $\tilde{g}_{\alpha}(-u)=\tilde{g}_{\alpha}(u)$, we may apply it to the shifted case as well.

Our limit shape result is an analogue of \cite[Thm.~1]{PR07}.
The obtained limit shape is the same as the limit shape for random SYT of square shape except that the domain is restricted from a square to a triangle.
Let
\begin{equation*}
\overline{L}:\big\{(u,v)\in\R^2:-\sqrt{2}/2\leq u\leq 0,\abs{u}\leq v\leq\sqrt{2}-\abs{u}\big\}\to\R_{\geq0}
\end{equation*}
be the surface defined by the level curves given by $\tilde{g}_{\alpha}(u)$ for $\alpha\in(0,1)$.
Let
\begin{equation*}
L:\big\{(x,y)\in\R^2:0\leq x\leq y\leq1\big\}\to\R_{\geq0}
\end{equation*}
be the rotated version of $\overline{L}$.
% , that is, $L(x,y)=\overline{L}(u,v)$, where $(x,y)$ and $(u,v)$ are related as in \eqref{eq:uv}.

% \smallskip
% The following lemma collects analytic results on the integral $K(g)$ and the functions $\tilde{g}_{\alpha}$.

% \begin{lem}\label{analysis}
% \begin{enumerate}[(i)]
% \item\label{Kcontinuous}
% There exists a constant $c_K>0$ such that for all $1$-Lipschitz functions $g,h$ we have
% \begin{equation*}
% \abs{K(g)-K(h)}\leq c_K\norm{g-h}
% \,.
% \end{equation*}
% \item\label{ana1}
% There exists a function $c:(2,3)\to\R_{>0}$ such that for all $r\in(2,3)$ and all $\alpha$-admissible functions $g$ we have
% \begin{equation*}%\label{eq:r_ineq}
% K(g)+H(\alpha)-\ln2\geq c(r)\norm{g-\tilde{g}_{\alpha}}^r
% \,.
% \end{equation*}
% \item\label{ana2}
% Let $(x,y)\in(0,1)\times(0,1)$, let $(u,v)$ be given as in \eqref{eq:uv}, set $\alpha=\overline{L}(u,v)$, and set
% \begin{equation*}
% \sigma(x,y)=\min\big(xy,(1-x)(1-y)\big)
% \,.
% \end{equation*}
% Then there exist constants $c_1>0$ and $c_2>0$ such that for all $\beta\in(0,1)$ and all $\delta<c_2\sigma(x,y)^2$ we have
% \begin{equation*}
% \abs{\tilde{g}_{\alpha}(u)-\tilde{g}_{\beta}(u)}<\delta c_1\sqrt{\sigma(x,y)}
% \qquad\Rightarrow\qquad
% \abs{\alpha-\beta}<\delta
% \,.
% \end{equation*}
% \end{enumerate}
% \end{lem}

% \smallskip
% The last needed ingredient is a bound on the expected number of entries less than $k$ in the first row of a random shifted SYT.
% We start with an auxiliary result. 
% Given a partition $\lambda$, let $\lambda^+$ denote the partition obtained from $\lambda$ by adding a cell to the first row, that is, $\lambda^+=(\lambda_1+1,\lambda_2,\dots,\lambda_{\ell(\lambda)})$.
% 
% \begin{lem}\label[lem]{amusing}
% Let $m,n\in\N$, $\Box=(n^m)$ be a rectangle and $\lambda$ a partition such that $\yd{(\lambda^+)}\subseteq\yd{\Box}$.
% Then
% \begin{equation*}
% \frac{f_{\lambda}\cdot f_{\Box\setminus\lambda^+}}{f_{\lambda^+}\cdot f_{\Box\setminus\lambda}}
% =\frac{(m+\lambda_1)(n-\lambda_1)}{(\abs{\lambda}+1)(mn-\abs{\lambda})}.
% \end{equation*}
% \end{lem}
% 
% The following lemma provides us with an analogue of \cite[Eq.~(75)]{PR07} for the shifted case.
% % and allows us deduce an analogue of \cite[Lem.~10]{PR07}.
% Given $n,k\in\N$ with $k<N$, let $I_{n,k}:\T{n}\to\{0,1\}$ denote the random variable that takes the value $1$ if the entry $k$ is contained in the first row, and $0$ otherwise.
% Moreover, let $J_{n,k}=\sum_{i=1}^kI_{n,i}$ denote the number of entries at most $k$ in the first row of a shifted SYT.

% \begin{lem}\label[lem]{expected}
% Let $k,n\in\N$ with $k<N$, and let $\E_n$ denote the expected value with respect to the uniform probability measure $\P_n$ on $\T{n}$.
% Then
% \begin{equation*}
% \E_n^2[I_{n,k}]
% <\E_{n}\left[\frac{2N-(J_{n,k})^2}{k(N-k+1)}\right]
% \,.
% \end{equation*}
% \end{lem}

% We now prove the limit shape theorem for shifted SYT of staircase shape chosen uniformly at random.


\begin{thm}\label[thm]{limit_shape}
For $n\in\N$ let $\Delta_n$ denote the staircase partition of size $N=\binom{n}{2}$, $\T{n}$ the set of shifted SYT of shape $\shyd{\Delta_n}$, and $\P_n$ the uniform probability measure on $\T{n}$.
Then for all $\epsilon>0$
\begin{equation}\label{eq:shape}
\lim_{n\to\infty}\P_n\left(\tab\in\T{n}:
\max_{(i,j)\in\shyd{\Delta_n}}
\abs{\frac{\tab(i,j)}{N}
-L\Big(\frac{i}{n},\frac{j}{n}\Big)}
% -L\Big(\frac{i-j}{n\sqrt{2}},\frac{i+j}{n\sqrt{2}}\Big)}
>\epsilon\right)=0
\,.
\end{equation}
Moreover for all $p\in(0,1/2)$ and all $q\in(0,p/2)$ such that $2p+q<1$
\begin{equation}\label{eq:convergence_rate}
\lim_{n\to\infty}\P_n\Bigg(\tab\in\T{n}:
\max_{\substack{(i,j)\in\shyd{\Delta_n}\\
\sigma(i/n,j/n)>n^{-q}}}
\abs{\frac{\tab(i,j)}{N}
-L\Big(\frac{i}{n},\frac{j}{n}\Big)}
% -L\Big(\frac{i-j}{n\sqrt{2}},\frac{i+j}{n\sqrt{2}}\Big)}
>n^{-p}
\Bigg)=0
\,,
\end{equation}
where $\sigma(x,y)=\min\{xy,(1-x)(1-y)\}$.
\end{thm}

In particular \eqref{eq:shape} provides point-wise convergence to the limit surface, while \eqref{eq:convergence_rate} specifies the rate of convergence if we assume a sufficient distance to the sides.


\section{Intermediate permutations and trajectories}\label{S:permutations}
This section considers the limit of intermediate permutation matrices in random 132-avoiding sorting networks, a parallel to \cite[Thm.~2]{D18} (previously \cite[Conj.~2]{AHRV07}). 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)$.
\begin{thm}[{\cite[Thm.~3.1, Cor.~3.4]{LP18}}]\label[thm]{diag}
Let $w = w_1 \cdots w_N$ be a 132-avoiding sorting network. Then the Young diagram of the shape of $Q_{w_1 \dots w_k}$ is $D(\sigma_k)$.
\end{thm}
Hence, the diagrams of intermediate permutation matrices are obtained by rotating and shifting the level curves $v = \tilde{g}_{\alpha}(u)$ of the limit surface $\bar{L}$.
\begin{thm}\label[thm]{intermediate_permutations}
Let $\sigma_0 = \text{id}$ and $\sigma_k = s_{w_1} \cdots s_{w_k}$ for $k \in [N]$, where $w = w_1 \dots w_N$ is a sorting network. Let $\P_n$ be the uniform probability measure on $\mathcal{R}^{132}_n$, the set of $n$-element 132-avoiding sorting networks. Finally, let
\[J_w(\alpha) = \big\{j \in [n] : \sigma_{\lfloor \alpha N \rfloor}(j) \leq \sigma_{\lfloor \alpha N \rfloor}(1)\big\}\] and $J_w^c(\alpha) = [n] \setminus J_n(\alpha)$. For all $0 \leq \alpha \leq 1$, $\epsilon > 0$, \[\P_n\biggl(w \in \mathcal{R}^{132}_n : \max_{j \in J_w(\alpha)}\biggl\vert\frac{\sigma_{\lfloor \alpha N \rfloor}(j)}{n} - \frac{1}{\sqrt{2}}\biggl(\tilde{g}_{\alpha}\biggl(\frac{-j}{n\sqrt{2}}\biggr) - \frac{j}{n\sqrt{2}}\biggr)\biggr\vert > \epsilon\biggr) \rightarrow 0,\] as $n \rightarrow \infty$. By symmetry, for all $0 \leq \alpha \leq 1$, $\epsilon > 0$, \[\P_n\biggl(w \in \mathcal{R}^{132}_n : \max_{j \in J_w^c(\alpha)}\biggl\vert\frac{\sigma_{\lfloor \alpha N \rfloor}(j)}{n} + \frac{1}{\sqrt{2}}\biggl(\tilde{g}_{1 - \alpha}\biggl(\frac{-j}{n\sqrt{2}}\biggr) - \frac{j}{n\sqrt{2}}\biggr) - 1\biggr\vert > \epsilon\biggr) \rightarrow 0,\] as $n \rightarrow \infty.$\end{thm}
\begin{figure}[t]
	\begin{center}
		\includegraphics[width=.3\textwidth]{conf-1.pdf}
		\quad
		\includegraphics[width=.3\textwidth]{conf-2.pdf}
		\quad
		\includegraphics[width=.3\textwidth]{conf-3.pdf}
	\end{center}
	\caption{The intermediate permutation matrices of a random 132-avoiding sorting network with 1000 elements at times $\alpha = \frac{1}{4}, \frac{1}{2}$ and $\frac{3}{4}$.\vspace{-2ex}}
	\label[fig]{matrix_sh}
\end{figure}

% \section{Trajectories}\label{S:trajectories}
%See \cref{traj_ex}.
%\begin{figure}[ht]
%	\begin{center}
%		\includegraphics[width=1.0\textwidth]{traj_ex.pdf}
%	\end{center}
%	\caption{Trajectories in the 132-avoiding sorting network 121321. The permutations $\sigma_k$ are $\sigma_0 = 1234$, $\sigma_1 = 2134$, $\sigma_2 = 2314$, $%\sigma_3 = 3214$, $\sigma_4 = 3241$, $\sigma_5 = 3421$ and $\sigma_6 = 4 3 2 1$. Hence the trajectory of the element 3 is 3, 3, 2, 1, 1, 1, 2.}
%	\label[fig]{traj_ex}
%\end{figure}
Next, inspired by the former sine trajectories conjecture \cite[Conj.~1]{AHRV07} of Angel et al. (now \cite[Thm.~1]{D18}), we study trajectories in random 132-avoiding sorting networks. The \emph{trajectory} of the element $i \in [n]$ in $w = w_1 \dots w_N$ is the function $k \mapsto \sigma_k^{-1}(i)$. The \emph{scaled trajectory} $f_i(\alpha) = f_{w,i}(\alpha)$ of $i$ in an $n$-element 132-avoiding sorting network $w$ is defined by $f_i(\alpha) = \sigma^{-1}_{\alpha N}(i)/n$
% \[f_i(\alpha) = \frac{\sigma^{-1}_{\alpha N}(i)}{n}\] 
for $\alpha N \in \Z$, and by linear interpolation for other $\alpha \in [0, 1]$. \cref{traj_sh} contains some examples. Using \cref{diag} and \cref{symmetry}, we get that the trajectories are given by the limit shape as follows.
\begin{thm}\label[thm]{scaled_trajectory}
Fix $m/n = \beta$. Let $D_{\beta} = \big\{(x, y) \in \R^2 : 0 \leq x \leq y \leq 1, y = \beta\ \text{or}\ x = \beta\big\}$.
Define $\mathfrak{f}_{\beta}(\alpha) = y - x$, where $L^{-1}(\alpha) = (x, y) \in D_{\beta}$, and \[\mathfrak{t}_{\beta}(\alpha) = \begin{cases} 
	\beta & \text{if}\ 0 \leq \alpha \leq \frac{1-\sqrt{1-\beta^2}}{2}, \\
	\mathfrak{f}_{\beta}(\alpha) & \text{if}\ \frac{1-\sqrt{1-\beta^2}}{2} < \alpha < \frac{1+\sqrt{2\beta-\beta^2}}{2},\\
	1 - \beta & \text{if}\ \frac{1+\sqrt{2\beta-\beta^2}}{2} \leq \alpha \leq 1.
	\end{cases}\]
Finally, let $\mathcal{R}^{132}_n$ denote the set of $n$-element 132-avoiding sorting networks and let $\P_n$ be the uniform probability measure on $\mathcal{R}^{132}_n$.
	Then for all $\epsilon > 0$,
	\[\lim_{n\rightarrow \infty} \P_n\Big(w \in \mathcal{R}^{132}_n : \sup_{0 \leq \alpha \leq 1} \big|f_{w, \lfloor \beta n \rfloor}(\alpha) - \mathfrak{t}_{\beta}(\alpha)\big| > \epsilon\Big) = 0.\]
\end{thm}
Informally, we can trace the trajectory of $\lfloor \beta n \rfloor$ by following the limit shape along $y = \beta$ until $x = y$, and then along $x = \beta$. If the height $\alpha = L(x', y')$ is given by some point $(x', y')$ along this curve, then the trajectory of $\lfloor \beta n\rfloor$ is at height $y'-x'$ at time $\alpha$. 
% \cref{traj_shape} illustrates this.
This combined with the implicit definition of $L(x, y)$ means that it is difficult to compute the trajectories of arbitrary elements explicitly. However, an accessible special case, the scaled trajectory of $1$ (the curve starting at the origin in \cref{traj_sh}) converges in probability to \[\mathfrak{t}_0(\alpha)=\begin{cases} 
	2\sqrt{\alpha-\alpha^2} & \text{if}\ 0 \leq \alpha \leq \frac{1}{2},  \\
	1 & \text{if}\ \frac{1}{2} < \alpha \leq 1.
	\end{cases}\]
% This corresponds to the curve starting at the origin in \cref{traj_sh}.
By symmetry, the trajectory of $n$ is given by the transformation $\alpha \mapsto 1 - \alpha$.
% \begin{figure}[t]
% 	\begin{center}
% \includegraphics[width=.25\textwidth]{3d-18.png}
% \quad
% \includegraphics[width=.32\textwidth]{traj.png}
% \end{center}
% 	\caption{A curve (in red) determining the trajectory shown on the right from the limit shape.}
% 	\label[fig]{traj_shape}
% \end{figure}

\vspace{-2ex}
\section{Adjacencies}\label{S:adj}

Motivated by the former great circle conjecture~\cite[Conj.~3]{AHRV07} (now~\cite[Thm.~4]{D18}) and trying to understand the geometry of random 132-avoiding sorting networks on the permutahedron, we next study adjacencies. 

Let $w$ be a reduced word of the longest element in $\S_n$. An index $k \in [N-1]$ is called an \emph{adjacency} of $w$ if $\abs{w_{k+1}-w_k}=1$. In the permutahedron, an adjacency corresponds to a pair of adjacent edges at an angle of $\frac{\pi}{3}$. In the case of $\abs{w_{k+1}-w_k} > 1$ the edges corresponding to $w_k$ and $w_{k+1}$ are orthogonal. Adjacencies in a 132-avoiding sorting network $w$ correspond directly to adjacencies in the SYT $Q_w^{\rightarrow}$ as follows.

Let $\yd{\lambda}$ be a Young diagram.
A pair $(\tab,u)$ of a cell $u=(i,j)\in\yd{\lambda}$ and a standard tableaux $\tab$ of shape $\lambda$ is called a \emph{horizontal adjacency} if $\tab(i,j+1)=\tab(u)+1$.
The pair $(\tab,u)$ is called a \emph{vertical adjacency} if $\tab(i+1,j)=\tab(u)+1$. The same definitions apply to shifted diagrams $\lambda^{\sh}$. For example, consider the tableau of \cref{shifted_example}.
% \[\begin{tikzpicture}
% % shifted tableau
% \begin{scope}
% % vertical and horizontal lines
% \draw[thinLine](2,1)--(3,1)(1,2)--(3,2)(1,2)--(1,3)(2,1)--(2,3);
% % border
% \draw[thickLine](0,2)--(1,2)--(1,1)--(2,1)--(2,0)--(3,0)--(3,3)--(0,3)--cycle;
% % entries
% \draw[entry](0,2)node{$1$}(1,2)node{$2$}(2,2)node{$3$}(1,1)node{$4$}(2,1)node{$5$}(2,0)node{$6$};
% \draw(0,1.5)node[anchor=east]{$\tab = $};
% \end{scope}
% \end{tikzpicture}\]
%Then, for example, $(\tab, (1, 3))$, $(\tab, (2, 3))$ are horizontal adjacencies, whereas $(\tab, (1, 2))$ is a vertical adjacency.
Then the horizontal adjacencies are $(\tab, (1, 1))$, $(\tab, (1, 3))$, $(\tab, (2, 3))$ and $(\tab, (3, 3))$, whereas $(\tab, (1, 2))$ and $(\tab, (3, 4))$ are the vertical adjacencies.

\begin{prop}
Let $w$ be a $132$-avoiding sorting network.
Then $(w_k,w_{k+1})=(j,j+1)$ if and only if $(Q_w^{\rightarrow},(Q_w^{\rightarrow})^{-1}(k))$ is a horizontal adjacency.
Similarly $(w_k,w_{k+1})=(j+1,j)$ if and only if $(Q_w^{\rightarrow},(Q_w^{\rightarrow})^{-1}(k))$ is a vertical adjacency.
\end{prop}

We next enumerate adjacencies in Young tableaux.

\begin{thm}\label[thm]{adjacencies}
Let $\lambda$ be a (possibly strict) partition and $A_c(\lambda)$ be the set of horizontal adjacencies $(T, (i, c))$ in column $c$ of any (possibly shifted) standard Young tableau $T$ of shape $\lambda$.
Then $\abs{A_c(\lambda)}$ is equal to the number of (possibly shifted) SYT of shape $\lambda$ with largest entry in or after column $c+1$. 
\end{thm}

Techniques similar to those used in the proof of \cref{adjacencies} also appear in \cite{STWW}. Theorem 4.2 implies the following two results on the expected number of adjacencies.
\begin{cor}\label[cor]{expected_adjacencies}
The expected number of horizontal (resp.~vertical) adjacencies in column $c < n-1$ (resp.~row $r < n - 1$) of a uniformly random shifted staircase SYT is equal to 1.
\end{cor}
\begin{cor}
The expected number of adjacencies in a random 132-avoiding sorting network of length $N$ is $2(n-2)$.
\end{cor}

Compare this with the result of Schilling et al.~below.
\begin{thm}[{\cite[Thm.~1.3]{STWW}}]
The expected number of $i\ (i + 1)\ i $, $1 \leq i \leq n-1$, in a random 132-avoiding sorting network of length $N$ is 1.
\end{thm}

% Some other corollaries of \cref{adjacencies} are listed next. 
% \begin{cor}
% For any strict partition $\lambda$, the expected number of horizontal adjacencies in column $c< \ell(\lambda)$ of a random shifted SYT of shape $\shyd{\lambda}$ is 1.
% \end{cor}

% A (shifted) Young diagram is called a \emph{(shifted) rectangle} if there is a cell that contains the largest entry in all standard tableaux of this shape. That is $\lambda=(\lambda_1,\dots,\lambda_{\ell})$ is a shifted rectangle if and only if
% $\lambda_i=\lambda_1-i+1$ for all $1\le i\le \ell$.

% \begin{cor}
% Let $\yd{\lambda}$ (resp.~$\shyd{\lambda}$) be a (shifted) rectangle and fix a column $c$ of $\yd{\lambda}$ (resp.~$\shyd{\lambda}$).
% Then the number of adjacencies in column $c$ is equal to $f_{\lambda}$ (resp.~$\shf{\lambda}$).
% \end{cor}

% \begin{cor}
% Let $\Box=(n^m)$ be a rectangle.
% Then
% \begin{equation*}
% \sum_{\yd{\mu}\subseteq\yd{\nu}\subseteq\yd{\Box}}f_{\mu}\cdot f_{\Box\setminus\nu}
% =(n-1)f_{\Box},
% \end{equation*}
% where the sum is taken over all Young diagrams such that $\yd{\nu}=\yd{\mu}\cup\{u,\e u\}$ for some cell $u\in\yd{\Box}\setminus\yd{\mu}$.
% Similarly,
% \begin{equation}\label{E:shrectangle}
% \sum_{\shyd{\mu}\subseteq\shyd{\nu}\subseteq\shyd{\Delta_n}}\shf{\mu}\cdot \shf{\Delta_n\setminus\nu}
% =(n-2)\shf{\Delta_n},
% \end{equation}
% where the sum is taken over all shifted Young diagrams such that $\shyd{\nu}=\shyd{\mu}\cup\{u,\e u\}$ for some cell $u\in\shyd{\Delta_n}\setminus\shyd{\mu}$.
% \end{cor}
% % \begin{cor}
% % Let $\yd{\lambda}$ be a rectangle.
% % Then
% % \begin{equation*}
% % \sum_{\yd{\lambda}=\yd{\mu}\cup\{u,\e u\}\cup\yd{\nu}}f_{\mu}\cdot f_{\nu}
% % =(\lambda_1-1)f_{\lambda},
% % \end{equation*}
% % where the sum is taken over all disjoint unions such that $\yd{\mu}$ and $\yd{\mu}\cup\{u,\e u\}$ are Young diagrams. Similarly, if $\shyd{\lambda}$ is a shifted rectangle, then 
% % \begin{equation}\label{E:shrectangle}
% % \sum_{\shyd{\lambda}=\shyd{\mu}\cup\{u,\e u\}\cup\shyd{\nu}}\shf{\mu}\cdot \shf{\nu}
% % =(\lambda_1-1)\shf{\lambda},
% % \end{equation}
% % where the sum is taken over all disjoint unions such that $\shyd{\mu}$ and $\shyd{\mu}\cup\{u,\e u\}$ are shifted Young diagrams.
% % \end{cor}

% Compare \eqref{E:shrectangle} to the identities
% \begin{equation}\label{E:STWW}
% \sum_{\shyd{\mu}\subseteq\shyd{\nu}\subseteq\shyd{\Delta_n}}\shf{\mu}\cdot\shf{\Delta_n\setminus\nu}
% =\shf{\Delta_n},
% \end{equation}
% where the sum is taken over all shifted Young diagrams such that $\shyd{\nu}=\shyd{\mu}\cup\{u,\e u,\e\s u\}$ for some cell $u\in\shyd{\Delta_n}\setminus\shyd{\mu}$, and
% \begin{equation}\label{E:trivial}
% \sum_{\shyd{\mu}\subseteq\shyd{\nu}\subseteq\shyd{\Delta_n}}\shf{\mu}\cdot\shf{\Delta_n\setminus\nu}
% =\binom{n}{2}\shf{\Delta_n},
% \end{equation}
% where the sum is taken over all shifted Young diagrams such that $\shyd{\nu}=\shyd{\mu}\cup\{u\}$ for some cell $u\in\shyd{\Delta_n}\setminus\shyd{\mu}$.
% % Compare \eqref{E:shrectangle} to %for $\lambda=\Delta_n$,
% % \begin{equation}\label{E:STWW}
% % \sum_{\shyd{\Delta_n}=\shyd{\mu}\cup\{u,\w u, \s u\}\cup\shyd{\nu}}\shf{\mu}\cdot \shf{\nu}
% % =\shf{\Delta_n},
% % \end{equation}
% % %where the sum is taken over all disjoint unions such that $\shyd{\mu}$ and $\shyd{\mu}\cup\{u,\w u, \s u\}$ are shifted Young diagrams. And the trivial
% % \begin{equation}\label{E:trivial}
% % \sum_{\shyd{\Delta_n}=\shyd{\mu}\cup\{u\}\cup\shyd{\nu}}\shf{\mu}\cdot \shf{\nu}
% % =\binom{n}{2}\shf{\Delta_n},
% % \end{equation}
% % where the sums are taken over all disjoint unions such that $\shyd{\mu}$ and $\shyd{\mu}\cup\{u,\w u, \s u\}$, (respectively $\shyd{\mu}\cup\{u\}$) are shifted Young diagrams. 
% The first identity follows from the result in \cite{STWW} mentioned above and the second is trivially true.

% \begin{prob} Can equations \eqref{E:shrectangle}, \eqref{E:STWW} and \eqref{E:trivial} be generalised?
% \end{prob}

% \smallskip 
%  If $w=s_i v$ is a reduced word for the reverse permutation in $\S_n$, then so is $v s_{n-i-1}$. Thus we know that the probability 
% of an adjacency is the same at every position in a random sorting network. This implies that the expected number of adjacencies before any position in a random sorting network grows linearly. 
% Experiments suggest that the distribution of adjacencies converges also in probability to the uniform distribution, see \cref{distances}. Also the number of adjacencies in a 132-avoiding sorting network seems to grow in a nice 
% manner.


% \begin{figure}[t]
% \begin{center}
% \includegraphics[width=.45\textwidth]{distrib_adj_n1000}
% \quad
% \includegraphics[width=.45\textwidth]{distrib_adj_shn2000}
% \end{center}
% \caption{The numbers of adjacencies in an initial segment of a random sorting network of size $n=1000$, (left) seems to grow linearly. The number of adjacencies in an initial segment of a random $132$-avoiding sorting network of size $n=2000$ (right) seems to grow like a square root for the first half.}
% \label[fig]{distances}
% \end{figure}


% \begin{conj}
% Let $Y_n(\alpha)$ and $X_n(\alpha)$ denote the number of adjacencies $1\leq k<\alpha\binom{n}{2}$ in a random sorting network and in a random $132$-avoiding sorting network of size $n$ respectively.

% Then $Y_n(\alpha)/\E[Y_n(1)]$ converges in probability to $c\alpha$ for some constant $c$ and 
% \begin{equation*}
% \lim_{n\to\infty}\P\left(\max_{0 \leq \alpha \leq 1}\abs{X_n(\alpha)/(2(n-2))-g(\alpha)}>\epsilon\right)=0,
% \end{equation*} where
% \begin{equation*}
% g(\alpha)=
% \begin{cases}
% \sqrt{\frac{\alpha}{2}}&\quad\text{if }\alpha\in[0,\frac{1}{2}],\\
% 1-\sqrt{\frac{1-\alpha}{2}}&\quad\text{if }\alpha\in[\frac{1}{2},1].
% \end{cases}
% \end{equation*}
% \end{conj}

% As an interesting problem for further study, we would also like to mention the behaviour of distances in value of adjacent elements in sorting networks, see \cref{adj_diff}. For example, if $\{w_k,w_{k+1}\}=\{j,j+2\}$ in a 132-avoiding sorting network, 
% then $k$ and $k+1$ are diagonally adjacent in the corresponding shifted SYT $Q_w^{\rightarrow}$. 

% \begin{figure}[ht]
% \begin{center}
% \includegraphics[width=.45\textwidth]{diff_adj_n1500}
% \quad
% \includegraphics[width=.45\textwidth]{diff_adj_shn2000}
% \end{center}
% \caption{The number of occurrences of distances between adjacent entries in a random sorting network of size $n=1500$ (left) and a random $132$-avoiding sorting network of size $n=2000$ (right).}
% \label[fig]{adj_diff}
% \end{figure}

%\bibliographystyle{plain}
%\bibliography{132avoiding_short}

\vspace{-2ex}
\acknowledgements{
The authors thank Dan Romik and John Stembridge for informative correspondences, and the referees for their valuable comments.
This paper benefited from experimentation with \texttt{Sage}~\cite{sage}.
}

\vspace{-1ex}
\printbibliography

\end{document}
