% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.9}{21(3)}{2014}

\usepackage{ytableau,calc,enumitem,float}

% Please remove all other commands that change parameters such as
% margins or pagesizes.

% only use standard LaTeX packages
% only include packages that you actually need

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; 
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{prop}{Proposition}[section]
\newtheorem{cor}[prop]{Corollary}
\newtheorem{thm}[prop]{Theorem}
\newtheorem{lemma}[prop]{Lemma}
\newtheorem{conj}[prop]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[prop]{Definition}
\newtheorem{qn}[prop]{Question}

\theoremstyle{remark}
\newtheorem{eg}[prop]{Example}
\newtheorem{remark}[prop]{Remark}
\newtheorem{NB}[prop]{Note}

\newenvironment{casework}{
    \begin{enumerate}[labelindent=15pt,labelwidth=\widthof{Case 9: },leftmargin=!]
    \renewcommand{\labelenumi}{\bf{\text{Case } \arabic{enumi}\text{: }}}}
{\end{enumerate}}
\newenvironment{subcasework}{
    \begin{enumerate}[labelindent=-15pt,labelwidth=\widthof{Subcase 9.9: },leftmargin=!]
    \renewcommand{\labelenumii}{\bf{\text{Subcase } \arabic{enumi}.\arabic{enumii}\text{: }}}}
{\end{enumerate}}


\newcommand{\oddeq}{\underset{\text{odd}}{\sim}}
\newcommand{\oddreq}{\underset{\text{odd}}{\sim^r}}
\newcommand{\eveneq}{\underset{\text{even}}{\sim}}
\newcommand{\evenreq}{\underset{\text{even}}{\sim^r}}

\newcommand{\sea}[1]{\underset{#1-\text{ASE}}{\sim}}
\newcommand{\sesa}[1]{\underset{#1-\text{SASE}}{\sim}}

\DeclareMathOperator\asc{Asc}
\DeclareMathOperator\des{Des}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf Ascent-Descent Young Diagrams\\ and Pattern Avoidance\\ in Alternating Permutations}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Ravi Jagadeesan\\
\small Phillips Exeter Academy\\[-0.8ex]
\small Exeter, NH, U.S.A.\\
\small\tt ravi.jagadeesan@gmail.com\\
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Mar 27, 2013}{Jul 11, 2014}{Jul 21, 2014}\\
\small Mathematics Subject Classifications: 05A05, 05A19}

\begin{document}

\maketitle

\begin{abstract}
  We investigate pattern avoidance in alternating permutations and an alternating analogue of Young diagrams. In particular, using an extension of Babson and West's notion of shape-Wilf equivalence described in our recent paper (with N. Gowravaram), we generalize results of Backelin, West, and Xin and Ouchterlony to alternating permutations.  Unlike Ouchterlony and B\'{o}na's bijections, our bijections are not the restrictions of Backelin, West, and Xin's bijections to alternating permutations. This paper is the second of a two-paper series presenting the work of \emph{Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux} (with N. Gowravaram, \arxiv{1301.6796v1}). The first paper in the series is \emph{Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux} (with N. Gowravaram, \emph{Electronic Journal of Combinatorics} 20(4):\#P17, 2013).

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:}  pattern avoidance; alternating permutation; shape-Wilf equivalence
\end{abstract}

\section{Introduction}
This paper proves a special case of a conjecture of Gowravaram and the author~\cite{OldPaper,PaperI}.
We now review the definitions of AD-Young diagrams and the alternating and semi-alternating conditions from the recent paper~\cite{PaperI} in order to state our main result.

\subsection{AD-Young diagrams and the shape-equivalence of permutation matrices}

For a nonnegative integer $n$, let $[n]$ denote the set $\{1,2,3,\ldots,n\}$.
Given a permutation $p$, let $M(p)$ denote its permutation matrix,
and given matrices $A$ and $B$, let $A \oplus B = \begin{bmatrix}
A & 0 \\
0 & B
\end{bmatrix}. $
We assume that the reader is familiar with the basic terminology
of Young diagrams and tableaux; see, for example, \cite[Chapters 2 and 6]{BonaBook}. 
We draw Young diagrams in English notation and use matrix coordinates, and
for example $(1,2)$ is the second square in the first row of a Young diagram.  Furthermore,
we require all Young diagrams to have the same number of rows and columns.  

\begin{definition}[\cite{PaperI}, Definition 2.1]
\label{ADYoung}
Let $Y$ be a Young diagram with $k$ rows.  %(we require all our Young diagrams to have the same number of rows and columns). 
If $A$ and $D$ are disjoint subsets of $[k-1]$
such that if $i \in A \cup D$, then the $i$th and $(i+1)$st rows of $Y$
have the same length, then we call the triple $\mathcal{Y} = (Y, A, D)$ an
\emph{AD-Young diagram}. 
We call $Y$ the Young diagram of $\mathcal{Y}$,
$A$ the \emph{required ascent set} of $\mathcal{Y}$, and $D$ the \emph{required descent set} of $\mathcal{Y}$. 
Figure~\ref{fig:ADYoungDef} gives an example of an AD-Young diagram.
\end{definition}

\begin{figure}[!h]
\center{
\begin{ytableau}
*(clear) & & &\\
& & &\\
&\\
&
\end{ytableau}}
\caption{If $Y = (4^2,2^2)$, $A = \emptyset$, and $D = \{3\}$, then $(Y, A, D)$ is an AD-Young diagram. }
\label{fig:ADYoungDef}
\end{figure}

As in \cite{BW, BWX}, a \emph{transversal} of Young diagram $Y$ is a set of squares $T = \{(i,t_i)\}$
such that
every row and every column of $Y$ contains exactly one member of $T$. 
\begin{definition}[\cite{PaperI}, Definition 2.2]
Given a transversal $T = \{(i,t_i)\}$, let
$\asc(T) = \{i \in [k-1] \mid t_i < t_{i+1}\}$ and $
\des(T) = \{i \in [k-1] \mid t_i > t_{i+1}\}. $
We call $\asc(T)$ the \emph{ascent set} of $T$ and $\des(T)$ the \emph{descent set} of $T$. 
If $A \subseteq \asc(T)$ and $D \subseteq \des(T)$, then we say that $T$ a \emph{valid transversal} of $\mathcal{Y}$. 
\end{definition}
\begin{eg}[\cite{PaperI}, Example 2.3]
If $T$ is a transversal of a Young diagram $Y$, then $T$ is a valid transversal of
the AD-Young diagram $(Y, \emptyset, \emptyset)$. 
\end{eg}

In this paper, we restrict ourselves to the AD-Young
analogues of alternating and reverse alternating permutations, as defined below.

\begin{definition}[\cite{PaperI}, Definition 2.4]
Given positive integers $x,y$ and an AD-Young diagram $(Y, A, D)$ such
that $Y$ has $k$ rows, we say that $(Y, A, D)$ is $x,y$\emph{-alternating}
if $A,D$ satisfy the property that
if $x - 1 \le i \le k-y$, then $i \in A$ if and only if $i + 1 \in D$. 
\end{definition}

If $\mathcal{Y}$ is $x,y$-alternating, then $\mathcal{Y}$
is $a,b$-alternating for all $a,b$ with $a \ge x$ and $b \ge y$.

\begin{definition}[\cite{PaperI}, Definition 2.5]
If $\mathcal{Y}$ is $1,y$-alternating, then we say that $\mathcal{Y}$ is $y$-alternating,
while if $\mathcal{Y}$ is $2,y$-alternating, then we say that $\mathcal{Y}$ is $y$-semialternating. 
\end{definition}

In particular, if $\mathcal{Y}=(Y,A,D)$ is an AD-Young diagram with $k\ge y$ columns and $1 \in D$,
then $\mathcal{Y}$ cannot be $y$-alternating, but $\mathcal{Y}$ can be $y$-semialternating.
Alternating AD-Young diagrams are the counterpart of alternating permutations, while
semialternating AD-Young diagrams allow reverse alternating permutations. 

\begin{eg}[\cite{PaperI}, Example 2.6]
Let $Y = (4^4)$.  Then, $(Y, \{1\}, \{2\})$ is 1-alternating, while
$(Y, \{1,3\}, \{2\})$ is 2-alternating but not 1-alternating. 
Furthermore, $(Y, \{2,4\}, \{1, 3\})$ is 1-semialternating but not $y$-alternating
for $y \le 4$. 
\end{eg}

The notion of pattern avoidance is exactly as in \cite{BW, BWX}.  A transversal
$T = \{(i,t_i)\}$ of a
Young diagram $Y$ \emph{contains} a $r \times r$ permutation matrix $M$ if there are rows $a_1 < a_2 < \cdots < a_r$
and columns $b_1 < b_2 < \cdots < b_r$ of $Y$ such that $(a_r,b_r) \in Y$ and
the restriction of $T$ to the rows $a_i$ and the columns
$b_i$ has contains exactly the squares where $M$ has ones. 
If $T$ does not contain $M$, then $T$ \emph{avoids} $M$ (see Figure~\ref{fig:MatrixContainment}).

\begin{figure}[!h]
\center{
\begin{ytableau}
*(clear) & *(yellow) & \bullet & *(yellow) & *(yellow) & \\
*(pink) & *(orange) & *(pink) & *(orange) \bullet & *(orange) & *(pink) \\
 & *(yellow) & & *(yellow) & *(yellow) & \bullet \\
*(pink) & *(orange) & *(pink) & *(orange) & *(orange) \bullet & *(pink) \\
*(pink) & *(orange) \bullet & *(pink) & *(orange) & *(orange) X\\
 \bullet & *(yellow) & & *(yellow)
\end{ytableau}}
\caption{The transversal $T = \{(1,3),(2,4),(3,6),(4,5),(5,2),(6,1)\}$ of $Y = (6^4,5,4)$
contains $M(231)$ because the restriction of $T$ to the yellow columns and the pink rows
rows is a copy of $M(231)$ in $T$. We require that $X \in Y$.  However, $T$ does not
contain $M(4321)$: for example, the restriction of $T$ to rows $3,4,5,6$
and columns $1,2,5,6$ is not a copy of $M(4321)$ in $T$ because $(6,6) \notin Y$. }
\label{fig:MatrixContainment}
\end{figure}

Given an AD-Young diagram
$\mathcal{Y}$ and a permutation matrix $M$, let $S_{\mathcal{Y}}(M)$ denote the set of valid transversals
of $\mathcal{Y}$ that avoid $M$. 
\begin{definition}[\cite{PaperI}, Definition 2.7]
If $M$ and $N$ are permutation matrices such that $|S_{\mathcal{Y}}(M)| = |S_{\mathcal{Y}}(N)|$
for all $x$-alternating AD-Young diagrams $\mathcal{Y}$, we say that $M$ and $N$ are
\emph{shape-equivalent for $x$-alternating AD-Young diagrams} and write $M \sea{x} N$. 
If we have $|S_{\mathcal{Y}}(M)| = |S_{\mathcal{Y}}(N)|$ for all $x$-semialternating AD-Young diagrams
$\mathcal{Y}$, then we say that $M$ and $N$ are \emph{shape-equivalent for $x$-semialternating AD-Young diagrams} and write $M \sesa{x} N$. 
\end{definition}

\subsection{The main result of this paper}

For a positive integer $r$, let $F_r$ denote the permutation matrix $M((r-1)(r-2)\cdots 1r)$.  In this paper, we prove the following result.

\begin{thm}
\label{JF3Strong}
We have $F_3 \sesa{1} J_3$.
\end{thm}

Due to the following result of Gowravaram and the author, Theorem~\ref{JF3Strong} in fact yields an infinite family of shape-equivalences.

\begin{thm}[\cite{PaperI}, Extension Theorem 2.9]
\label{ShapeExtend}
If permutation matrices $M$ and $M'$ are shape-equivalent for $x$-alternating (resp. $x$-semialternating) AD-Young diagrams and $C$
is an $r \times r$ permutation matrix, then we have
$M \oplus C \sea{(x+r)} M' \oplus C$
(resp. $\sesa{(x+r)}$~).
\end{thm}

Theorem~\ref{JF3Strong} has consequences in the theory of pattern-avoiding alternating permutations.  We now recall the basic definitions.  Let $S_n$ denote the set of permutations of $[n]$.
We treat a permutation $w \in S_n$ as a sequence $w_1w_2w_3\cdots w_n$ that contains
every element of $[n]$ exactly once.  A permutation $w$ is said to \emph{contain}
a permutation $q$ if there is a subsequence of $w$ that is order-isomorphic to $q$.
For example, the subsequence $246$ of $214536$ shows that $214536$ contains $123$.
If $w$ does not contain $q$, we say that $w$ \emph{avoids} $q$.
A permutation $w \in S_n$ is called \emph{alternating} if
$w_1 < w_2 > w_3 < \cdots$
and \emph{reverse alternating} if
$w_1 > w_2 < w_3 > \cdots.$
Reverse alternating permutations can be transformed into alternating permutations
(and vice versa) by the \emph{complementation} map that sends
a permutation $w = w_1w_2\cdots w_n$ to $w^c = (n+1-w_1)(n+1-w_2)\cdots (n+1-w_n)$.
Given a pattern $q$, let $A_n(q)$ (resp. $A'_n(q)$) denote the set of alternating
(resp. reverse alternating)
permutations of length $n$ that avoid $q$.  If $p$ and $q$ are such that
$|A_n(p)| = |A_n(q)|$ (resp. $|A'_n(p)| = |A'_n(q)|$) for all even $n$, we say
that $p$ and $q$ are \emph{equivalent for even-length alternating} (resp. \emph{reverse alternating})
permutations and we write $p \eveneq q$ (resp. $p \evenreq q$).  We make similar definitions for
odd-length permutations.

Gowravaram and the author~\cite{PaperI} proved the following two results that link shape-equivalence for AD-Young diagrams to equivalence for alternating permutations.

\begin{prop}[\cite{PaperI}, Proposition 2.8]
\label{AltPermToDiag}
Let $p$ and $q$ be permutations.
\begin{enumerate}[label=(\alph*)]
\item If $M(p) \sea{1} M(q)$,
then $p \oddeq q$.
\item If $M(p) \sesa{1} M(q)$,
then $p \evenreq q$.
\item If $M(p) \sea{2} M(q)$,
then $p \eveneq q$.
\item If $M(p) \sesa{2} M(q)$,
then $p \oddreq q$.
\end{enumerate}
\end{prop}

The following corollaries of Theorem~\ref{JF3Strong} follow immediately from Propositions~\ref{AltPermToDiag} and~\ref{JF3Strong},
and the Extension Theorem~\ref{ShapeExtend}.

\begin{cor}
\label{213321AltRAlt}
For all $t > 3$ and all permutations $q$ of $[t]\setminus [3]$, the patterns $213q$,
and $321q$ are equivalent for even- and odd-length alternating and reverse-alternating permutations.
\end{cor}

%Taking complements in the statement of Corollary~\ref{213321AltRAlt} for reverse alternating permutations
%yields the following corollary.

\begin{cor}
\label{213321RAlt}
For all $t \ge 3$ and all permutations $q$ of $[t]$, the patterns $(t-1)t(t-2)q$
and $(t-2)(t-1)tq$ are equivalent for even- and odd-length alternating permutations.
\end{cor}

\subsection{Relationship to other work}

Babson and West~\cite{BW} proved that $F_3$ and $J_3$ are shape-Wilf equivalent, which is the analogue of Theorem~\ref{JF3Strong} for ordinary Young diagrams.  Backelin, West, and Xin~\cite{BWX} proved that $F_r$ and $J_r$ are
shape-Wilf equivalent.  We apply the ideas behind Backelin, West, and Xin's work in defining bijections to prove Theorem~\ref{JF3Strong}.

Gowravaram and the author~\cite{OldPaper,PaperI} proved the equivalence $F_2 \sea{1} J_2$
and conjectured that $F_r \sesa{1} J_r$ holds for $r \ge 3$.  This conjecture has recently been fully proven by Yan~\cite{YanAD}.
B\'{o}na~\cite{Bona1221} proved special cases of the consequences of Gowravaram and the author's result that $F_2 \sea{1} J_2$,
while Ouchterlony~\cite{Ouch} proved a variant of the shape-equivalence $F_2 \sea{1} J_2$ for doubly alternating permutations, which are alternating permutations whose inverses are alternating.  Several related conjectures were posed by Lewis~\cite{Lewis2012}.

Our bijection between the sets
$S_\mathcal{Y}\left(F_3\right)$ and $S_\mathcal{Y}\left(J_3\right)$ differs from Backelin, West, and Xin's and Yan's bijections in many cases when $\mathcal{Y}$ has non-empty sets of required ascents or descents.  On the other hand, the bijections of B\'{o}na~\cite{Bona1221}, Ouchterlony~\cite{Ouch}, and Gowravaram and the author~\cite{PaperI} are restrictions of Backelin, West, and Xin's bijections to alternating permutations.  The essential difficulty is that the bijection that Backelin, West, and Xin use to prove that $F_3$ and $J_3$ are shape-Wilf equivalent does not preserve ascents and descents, and therefore the induced bijection between $S_n(321q)$ and $S_n(213q)$ does not preserve the alternating property.

This paper is the second of a two-paper series presenting the work of \cite{OldPaper} (joint work with N. Gowravaram);
the first paper is \cite{PaperI}.

\subsection{Outline of the paper}

The remainder of this paper is devoted to the proof of Theorem~\ref{JF3Strong}.  The idea of the proof
is to establish a bijection between $S_\mathcal{Y}(F_3)$
and $S_\mathcal{Y}(J_3)$ for $\mathcal{Y}$ a 1-alternating AD-Young diagram. Similar to the first proof of \cite[Proposition 3.1]{BWX}, our bijection selects a copy of $J_3$ (resp. $F_3$) in a transversal
and removes it, but significant complications arise due to the required ascent
and descent sets.
We divide into cases based on the locations of required ascents and descents
near the rightmost entry of the copy of $J_3$ (resp. $F_3$) and convert the copy to an instance of $F_3$ (resp. $J_3$) in
a manner that maintains required ascents and descents.  The fact that
rows of $Y$ have equal size at required ascents and descents of $\mathcal{Y}$
plays a critical role in ensuring that the replacement algorithm returns
a valid transversal of $\mathcal{Y}$.
Similar to Backelin, West, and Xin~\cite{BWX}'s method, we restrict ourselves to so-called \emph{separable}
transversals (a class of transversals that contains any transversal
that avoids $F_3$ or $J_3$) because the two replacement procedures
are not inverse in general for non-separable transverals.  Due to the more elaborate process of removing
copies of $J_3$ and $F_3$, our notion of separability becomes slightly more technical than
the notion implicitly used by Backelin, West, and Xin~\cite{BWX}.

The organization of the paper is as follows.
In Section~\ref{sec:CyclicShifts}, we fix some useful notation that we use to describe our bijections.  In Section~\ref{sec:Bijection}, we state our bijection, and in Section~\ref{sec:ProofOfMain}, we prove Theorem~\ref{JF3Strong}.  In Section~\ref{sec:CompareBWX}, we explain a difference between our bijection and that of Backelin, West, and Xin.  The proofs of two technical results used in the proof of Theorem~\ref{JF3Strong} are deferred to Sections~\ref{sec:PropFullPhi} and~\ref{sec:PropFullPsi}.


\section{Cyclic Shifts}
\label{sec:CyclicShifts}
Fix a Young diagram $Y$ with $n$ columns for the entirety of this section and
let $T = \{(i,b_i)\}$ be a transversal of $Y$.  Let $\mathcal{T}$ denote the set of transversals of $Y$.
We define a function $\omega_{M}^{P}: \mathcal{T} \to \mathcal{T}$ for
sets $M, P \subseteq [1,n]$ with $m = \max M$ and $p = \max P$,
such that the $m$th row of $Y$ has at least $p$ squares.  Let
$i_1<i_2<\cdots<i_k$ denote the indices $i_j \in M$ with $b_{i_j} \in P$.
Take the index $j$ of $i_j$ modulo $k$, and let $\Gamma_{M}^{P}(T) = \{i_j \mid j \in [k]\}$.
Then, we define
\[\omega_{M}^{P}(T) = T \setminus \{(i_j,b_{i_j}) \mid i \in [k+1]\}
    \cup \{(i_j,b_{i_{j-1}}) \mid j \in [k]\}.\]
We now define the function $\theta_{M}^{P}: \mathcal{T} \to \mathcal{T}$, which takes the same arguments as $\omega_M^P$ and will be
proven to be the inverse of $\omega_M^P$.  Let
$\{i_1<i_2<\cdots<i_k\} = \Gamma_M^P(T)$, and
we define
\[\theta_{M}^{P}(T) = T \setminus \{(i_j,b_{i_j}) \mid i \in [k+1]\}
    \cup \{(i_j,b_{i_{j+1}}) \mid j \in [k]\}.\]

Because the $m$th row of $Y$ has at least $p$ boxes, $\omega_M^P$ and $\theta_M^P$
return transversals of $Y$.  Notice that
\[\Gamma_{M}^{P}(T) = \Gamma_{M}^{P} \left(\omega_{M}^{P}(T)\right),\]
and hence $\omega_{M}^{P}(\cdot)$ and $\theta_{M}^{P}(\cdot)$ are inverses of each other.
Furthermore, if $i \notin M$, the position of the element of $T$ in the $i$th column of $Y$
is the same as that of $\omega_{M}^{P}(T)$ and in $\theta_{M}^{P}(T)$.  If $M \times P$
and $M' \times P'$ are disjoint, then it is clear that $\omega_M^P(\cdot)$ and
$\theta_M^P(\cdot)$ each commute with $\omega_{M'}^{P'}(\cdot)$ and $\theta_{M'}^{P'}(\cdot)$.
The functions $\omega_M^P$ and $\theta_M^P$ cyclically alter certain entries $b_i$ of a transversal
$T = \{(i,b_i)\}$.
See Figure~\ref{fig:CyclicShifts} for an example of cyclic shifts.

\begin{figure}[!h]
\center{
\begin{ytableau}
*(clear) & & \bullet &  & & \\
& *(lightgray) & *(lightgray) & *(lightgray) & *(lightgray) & \bullet\\
& *(lightgray)\diamond & *(lightgray) & *(lightgray) \bullet & *(lightgray)\times \\
\bullet  & & & & \\
& *(lightgray) \bullet & *(lightgray) & *(lightgray)\times & *(lightgray)\diamond\\
& *(lightgray) \times & *(lightgray) & *(lightgray)\diamond & *(lightgray) \bullet\\
\end{ytableau}
}
\caption{Let $Y = (6^2,5^4)$ and let $T = \{(1,3),(2,6),(3,4),(4,1),(5,2),(6,5)\}$.
Then, $\Gamma_{[2,3] \cup [5,6]}^{[2,5]}(T) = \{3,5,6\},$ and thus $\omega_{[2,3] \cup [5,6]}^{[2,5]}(T)
= \{(1,3),(2,6),(3,5),(4,1),(5,4),(6,2)\}$ and $\theta_{[2,3] \cup [5,6]}^{[2,5]}(T)
= \{(1,3),(2,6),(3,2),(4,1),(5,5),(6,4)\}$.
Bullets mark elements of $T$ and crosses mark
elements of $\omega_{[2,3] \cup [5,6]}^{[2,5]}(T) \setminus T$, while diamonds
mark elements of $\theta_{[2,3] \cup [5,6]}^{[2,5]}(T) \setminus T$.}
\label{fig:CyclicShifts}
\end{figure}

\section{Statement of the Bijection}
\label{sec:Bijection}

We first prove that $F_3 \sea{1} J_3$.
To this end, suppose that $\mathcal{Y} = (Y,A,D)$ is a 1-alternating AD-Young diagram with $n$ rows.
We shall define a bijection $\Phi: S_\mathcal{Y}(F_3) \to S_\mathcal{Y}(J_3)$ and its inverse $\Psi: S_\mathcal{Y}(J_3) \to S_\mathcal{Y}(F_3)$.
To define $\Phi$ and $\Psi$, we first define functions $\phi$ and $\psi$, and then obtain $\Phi$ and $\Psi$ by iterating $\phi$ and $\psi$, respectively.
Let $T = \{(i,b_i)\}$ be a transversal of $\mathcal{Y}$.  If $a_1 < a_2 < a_3 \in [n]$,
then we say that $(a_1,a_2,a_3)$ is a copy of $J_3$ (resp. $F_3$) in $T$ if
$\{(a_i,b_{a_i}) \mid i \in [3]\}$ is a copy of $J_3$ (resp. $F_3$) in $T$.

Let $T = \{(i,b_i)\}$ be a transversal of $\mathcal{Y}$ that contains $J_3$.
Suppose that $(a_1,a_2,a_3)$ is a copy of $J_3$ in $T$.  We define auxiliary functions
$\phi_\ell^{(a_1,a_2,a_3)}(T)$ for $\ell \in [3]$ (the functions take arguments $(a_1,a_2,a_3)$ and $T$, and return
only transversals of the Young diagram $(n^n)$ \emph{\`{a} priori}).
We define
\begin{align*}
\phi_1^{(a_1,a_2,a_3)}(T) &= \theta_{\{a_1,a_2,a_3\}}^{[1,b_{a_1}]}(T)\\
\phi_2^{(a_1,a_2,a_3)}(T) &= \omega_{\{a_1,a_3-1\}}^{[1,b_{a_1}]}(T)\\
\phi_3^{(a_1,a_2,a_3)}(T) &= \omega_{[1,a_1] \cup \{a_3+1\}}^{[b_{a_3},b_{a_1}]}\left(\omega_{[a_2,a_3]}^{[b_{a_3},b_{a_1}]}(T)\right).
\end{align*}
The operation $\phi_1$ is the one used by Backelin, West, and Xin in their proof of
\cite[Proposition 3.1]{BWX}.

Let $U(T)$ denote the set of triples $a \in [n]^3$ that are copies of $J_3$ in $T$.
If $a = (a_1,a_2,a_3) \in U(T)$, then
define the $J$-type of $a$ in the following cases.
\begin{casework}
\item If ($a_3 - 1 \notin D$ or $b_{a_1} < b_{a_3-1}$) and $a_3 \notin A$,
    we say that $(a_1,a_2,a_3)$ is of $J$-type 1.
\item If $a_3 -1 \in D$ and $b_{a_3-1} < b_{a_1},$ we say that $(a_1,a_2,a_3)$ is of $J$-type 2.
\item If ($a_3 -1 \notin D$ or $b_{a_3-1} > b_{a_1}$) and $a_3 \in A$,
    we say that $(a_1,a_2,a_3)$ is of $J$-type 3.
\end{casework}

See Figures~\ref{fig:phi1},~\ref{fig:phi2}, and~\ref{fig:phi3} for geometric
descriptions of the functions $\phi_\ell$.
\begin{figure}[!h]
\ytableausetup{boxsize = 1.07em}
\center{
\begin{ytableau}
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots]\\
\none[a_1] & \none & \none[\cdots] & & \none[\cdots] &\times & \none[\cdots] &\blacksquare & \none[\cdots]\\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots]\\
\none[a_2] & \none & \none[\cdots] &\times & \none[\cdots] &\blacksquare & \none[\cdots] & & \none[\cdots]\\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots]\\
\none[a_3] & \none & \none[\cdots] &\blacksquare & \none[\cdots] & & \none[\cdots] &\times & \none[\cdots]\\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots]\\
\end{ytableau}}
\caption{We show the effect of $\phi_1^{(a_1,a_2,a_3)}$ on a transversal $T$. Black boxes mark the
 selected elements of $T$ while crosses mark elements of $\phi_1^{(a_1,a_2,a_3)}(T) \setminus T$.}
\label{fig:phi1}
\end{figure}
\begin{figure}[!h]
\center{
\begin{ytableau}
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] \\
\none[a_1] & \none & \none[\cdots] & & \none[\cdots] & & \none[\cdots] &\times & \none[\cdots] &\blacksquare & \none[\cdots]\\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] \\
\none[a_2] & \none & \none[\cdots] & & \none[\cdots] &\blacksquare & \none[\cdots] & & \none[\cdots] & & \none[\cdots]\\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] \\
\none[a_3-1] & \none & \none[\cdots] & & \none[\cdots] & & \none[\cdots] &\bullet& \none[\cdots] &\times& \none[\cdots]\\
\none[a_3] & \none & \none[\cdots] &\blacksquare & \none[\cdots] & & \none[\cdots] & & \none[\cdots]\\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] \\
\end{ytableau}}
\caption{We show the effect of $\phi_2^{(a_1,a_2,a_3)}$ on a transversal $T$. Black boxes mark the
 selected elements of $T$ and bullets mark other elements of $T$, while crosses mark elements of $\phi_1^{(a_1,a_2,a_3)}(T) \setminus T$.}
\label{fig:phi2}
\end{figure}
\begin{figure}[!h]
\center{
\begin{ytableau}
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[i_1] & \none & \none[\cdots] & & \none[\cdots] & \times & \none[\cdots] & \bullet & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[i_2] & \none & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \times & \none[\cdots] & \bullet & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[a_1] & \none & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \times & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \blacksquare & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[a_2] & \none & \none[\cdots] & \times & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \blacksquare & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[i'_1] & \none & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \times & \none[\cdots] & \bullet & \none[\cdots] & & \none[\cdots] & & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[i'_2] & \none & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \times & \none[\cdots] & \bullet & \none[\cdots] & & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[a_3] & \none & \none[\cdots] & \blacksquare & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \times & \none[\cdots] & & \none[\cdots] \\
\none[a_3+1] & \none & \none[\cdots] & & \none[\cdots] & \bullet & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \times & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\end{ytableau}}
\caption{We show the effect of $\phi_3^{(a_1,a_2,a_3)}(T)$ on a transversal $T$, supposing
that $\{i_1,i_2\} = \Gamma_{[1,a_1)}^{[b_{a_3},b_{a_1}]}(T)$ and
$\{i'_1,i'_2\} = \Gamma_{(a_2,a_3)}^{[b_{a_3},b_{a_1}]}(T)$.  Black boxes mark the
 selected elements of $T$ and bullets mark other elements of $T$, while crosses mark elements of $\phi_1^{(a_1,a_2,a_3)} \setminus T$.}
\label{fig:phi3}
\end{figure}

For $u = (u_1,u_2,u_3) \in \mathbb{N}^3$, let $\#(u) = (u_3,u_1,u_2)$.
Let $h_J(T)$ be the triple $a \in U(T)$ that minimizes
$\#(a)$ in the lexicographic order. This is exactly
the way in which a copy of $J_3$ is chosen to be removed in the proof
of \cite[Proposition 3.1]{BWX}.  If $h_J(T)$ is of $J$-type $t$,
let $\phi(T) = \phi_t^{h_J(T)}(T)$, and we say that $T$ is of $J$-type $t$.

We define the functions $\psi_\ell,$ which take the same arguments as the $\phi_\ell$
and return only transversals of $(n^n)$ \emph{\'{a} priori}.
For $\ell \in [3]$, let
\begin{align*}
\psi_1^{(a_1,a_2,a_3)} &= \omega_{\{a_1,a_2,a_3\}}^{[1,b_{a_3}]}(T)\\
\psi_2^{(a_1,a_2,a_3)} &= \theta_{\{a_1,a_3\}}^{[1,b_{a_3}]}(T)\\
\psi_3^{(a_1,a_2,a_3)} &= \theta_{[a_2,a_3-1]}^{[b_{a_2},b_{a_3}]}\left(\theta_{[1,a_1] \cup \{a_3\}}^{[b_{a_2},b_{a_3}]}(T)\right).
\end{align*}
The operation $\psi_1$ is the one used by Backelin, West, and Xin in their proof
of \cite[Proposition 3.1]{BWX}.

Let $V(T)$ denote the set of triples $a = (a_1,a_2,a_3) \in [n]^3$ that
are copies of $F_3$ in $T$ such that $a_3 \notin A$.
For each $a \in V(T)$, we define a triple $S(a)$ that will depend on the $F$-type of $a$.  The triple $S(a)$ will be independent of $T$, and $\psi$ will convert a copy of $F_3$ at $a$ to a copy of $J_3$ at $S(a)$.
For $a = (a_1,a_2,a_3) \in V(T)$, we define the $F$-type of $a$ in the
in the following cases.
\begin{casework}
\item If $a_3 - 1 \notin A$,
    let $S(a) = (a_3,a_1,a_2).$  We say that $a$ is of $F$-type 1.
\item If $a_3-1 \in A$ and $a_2 = a_3 - 1$,
    let $S(a) = (a_3+1, a_1, 0)$.
    We say that $a$ is of $F$-type 2.
\item If $a_3 - 1 \in A$ and $a_2 \not= a_3-1$, let $S(a) = (a_3-1,a_1,a_2)$.
We say that $a$ is of $F$-type 3.
\end{casework}

See Figures~\ref{fig:psi1},~\ref{fig:psi2}, and~\ref{fig:psi3} for geometric
descriptions of the functions $\psi_\ell$.
\begin{figure}[!h]
\center{
\begin{ytableau}
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots]\\
\none[a_1] & \none & \none[\cdots] & & \none[\cdots] &\blacksquare & \none[\cdots] &\times & \none[\cdots]\\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots]\\
\none[a_2] & \none & \none[\cdots] &\blacksquare & \none[\cdots] &\times & \none[\cdots] & & \none[\cdots]\\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots]\\
\none[a_3] & \none & \none[\cdots] &\times & \none[\cdots] & & \none[\cdots] &\blacksquare & \none[\cdots]\\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots]\\
\end{ytableau}}
\caption{We show the effect of $\psi_1^{(a_1,a_2,a_3)}$ on a transversal $T$. Black boxes mark the
 selected elements of $T$, while crosses mark elements of $\psi_1^{(a_1,a_2,a_3)}(T) \setminus T$.}
\label{fig:psi1}
\end{figure}

\begin{figure}[!h]
\center{
\begin{ytableau}
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots]\\
\none[a_1] & \none & \none[\cdots] & & \none[\cdots] &\blacksquare & \none[\cdots] &\times & \none[\cdots]\\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots]\\
\none[a_2] & \none & \none[\cdots] &\blacksquare & \none[\cdots] & & \none[\cdots] & & \none[\cdots]\\
\none[a_3] & \none & \none[\cdots] & & \none[\cdots] &\times & \none[\cdots] &\blacksquare & \none[\cdots]\\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots]\\
\end{ytableau}}
\caption{We show the effect of $\psi_2^{(a_1,a_2,a_3)}$ on a transversal $T$. Black boxes mark the
 selected elements of $T$, while crosses mark elements of $\psi_2^{(a_1,a_2,a_3)}(T) \setminus T$.}
\label{fig:psi2}
\end{figure}

\begin{figure}[!h]
\center{
\begin{ytableau}
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[i_1] & \none & \none[\cdots] & & \none[\cdots] & \bullet & \none[\cdots] & \times & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[i_2] & \none & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \bullet & \none[\cdots] & \times & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[a_1] & \none & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \blacksquare & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \times & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[a_2] & \none & \none[\cdots] & \blacksquare & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \times & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[i'_1] & \none & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \bullet & \none[\cdots] & \times & \none[\cdots] & & \none[\cdots] & & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[i'_2] & \none & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \bullet & \none[\cdots] & \times & \none[\cdots] & & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\none[a_3-1] & \none & \none[\cdots] & \times & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \bullet & \none[\cdots] & & \none[\cdots] \\
\none[a_3] & \none & \none[\cdots] & & \none[\cdots] & \times & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & & \none[\cdots] & \blacksquare & \none[\cdots] \\
\none & \none & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none \\
\end{ytableau}}
\caption{We show the effect of $\psi_3^{(a_1,a_2,a_3)}$ on a transversal $T$, supposing
that $\{i_1,i_2\} = \Gamma_{[1,a_1)}^{[b_{a_2},b_{a_3}]}(T)$ and
$\{i'_1,i'_2\} = \Gamma_{(a_2,a_3)}^{[b_{a_2},b_{a_3}]}(T)$.  Black boxes mark the
 selected elements of $T$ and bullets mark other elements of $T$, while crosses mark elements of $\psi_3^{(a_1,a_2,a_3)}(T) \setminus T$.}
\label{fig:psi3}
\end{figure}

For $u, u' \in V(T)$, we write $u \triangleright u'$ if $S(u) \ge S(u')$ in the
lexicographic order.  We will select a copy of $F_3$ to eliminate by
treating $\triangleright$ as a total order on $V(T)$. To do so, we require
the following lemma.
\begin{lemma}
$S$ is injective, and thus $\, \triangleright$ is a total order on $V(T)$.
\end{lemma}
\begin{proof}
Suppose that $S(u) = (d_3,d_1,d_2)$.  If $d_2 = 0$, then $u$ and $u'$ are of $F$-type
2, and thus $u = (d_1,d_3-2,d_3-1)$.  If $d_2 \not= 0$ and $d_3 \in A$, then $u$ and $u'$
are of $F$-type 3, and hence $u = (d_1,d_2,d_3+1)$.  Otherwise, we have $d_2 \not= 0$
and $d_3 \notin A$, which implies that $u$ is of $F$-type 1 and $u = (d_1,d_2,d_3)$.  It follows that
$S$ has a left inverse and is therefore injective.  The fact that $\, \triangleright$ is a total order
follows.
\end{proof}
Let $h_F(T)$ denote the maximum of $V(T)$ with respect to the restriction of $\, \triangleright$.
If $A = D = \emptyset$, then $h_F(T)$ agrees with Backelin, West, and Xin's selection of a copy of $F_3$ to remove
in their proof of \cite[Proposition 3.1]{BWX}, but in general, $h_F(T)$ differs
from Backelin, West, and Xin's selection.
If $h_F(T)$ is of $F$-type $t$,
let $\psi(T) = \psi_t^{h_F(T)}(T)$, and we say that $T$ is of $F$-type $t$.

\section{Proof of Theorem~\ref{JF3Strong}}
\label{sec:ProofOfMain}

The functions $\phi$ and $\psi$ are not inverses on general transversals of $\mathcal{Y}$,
but we are only interested in the transversals $\phi^m(T)$ and $\psi^m(T)$
for $T \in S_\mathcal{Y}(F_3) \cup S_\mathcal{Y}(J_3)$.  We now define the
class of transversals that we will consider.
A transversal $T$ is said to be \emph{separable}
if it satisfies the property that if $u \in U(T)$ and $u' = S\left(V(T)\right)$,
then $\#(u) \ge u'$ in the lexicographic order.  Any
element of $S_\mathcal{Y}(J_3)$ (resp. $S_{\mathcal{Y}}(F_3)$) is separable,
as $U(T)$ (resp. $V(T)$) is empty.  We restrict our attention
to separable transversals.

The critical properties of $\phi$ and $\psi$ are the following two propositions.

\begin{prop}
\label{FullPhi}
If $T$ is a separable valid transversal of $\mathcal{Y}$ that
contains $J_3$, then $\phi(T)$ is a separable valid transversal of $\mathcal{Y}$
and we have $\psi(\phi(T)) = T$.  Furthermore, if $T = \{(i,b_i)\}$ and $\phi(T) = \{(i, c_i)\}$,
then we have $(b_1,b_2,\ldots, b_n) > (c_1,c_2,\ldots,c_n)$ in the lexicographic order.
\end{prop}

\begin{prop}
\label{FullPsi}
If $T$ is a separable valid transversal of $\mathcal{Y}$ that
contains $F_3$, then $\psi(T)$ is a separable valid transversal of $\mathcal{Y}$
and we have $\phi(\psi(T)) = T$.  Furthermore, if $T = \{(i,b_i)\}$ and $\psi(T) = \{(i, c_i)\}$,
then we have $(b_1,b_2,\ldots, b_n) < (c_1,c_2,\ldots,c_n)$ in the lexicographic order.
\end{prop}

We defer the proofs of Propositions~\ref{FullPhi}
and~\ref{FullPsi} to Sections~\ref{sec:PropFullPhi} and~\ref{sec:PropFullPsi}, respectively.
To complete the proof of Theorem~\ref{JF3Strong},
we require a simple technical lemma to extend from alternating
to semialternating AD-Young diagrams.  The lemma follows immediately from the definitions
of $\phi$ and $\psi$, and so we omit its proof.

\begin{lemma}
\label{AddA1}
Let $T = \{(i,b_i)\}$ be a valid transversal of $\mathcal{Y}$ with $b_1 = 1$.
If $T$ contains $J_3$ and $\phi(T) = \{(i,c_i)\}$, then we have $c_1 = 1$.
If $T$ contains $F_3$ and $\psi(T) = \{(i,c_i)\}$, then we have $c_1 = 1$.
\end{lemma}

\begin{proof}[Proof of Theorem~\ref{JF3Strong} assuming Propositions~\ref{FullPhi} and~\ref{FullPsi}]
Let $\mathcal{Y}$ be a 1-alternating AD-Young diagram with $n$ rows and let $T \in S_\mathcal{Y}(F_3)$.  Because
$V(T) = \emptyset$, the transversal $T$ is separable.  We claim that there exists an integer $m$ such that
$\phi^m(T) \in S_\mathcal{Y}(J_3)$.  It follows from by Proposition~\ref{FullPhi} that for all $m \ge 1$, the iterate $\phi^m(T)$ exists and is a separable, valid transversal of $\mathcal{Y}$ provided that the iterate $\phi^{m-1}(T)$ exists, is a separable valid transversal of $\mathcal{Y}$, and contains $J_3$.  Assume for sake of deriving a contradiction that $\phi^m(T) \notin S_\mathcal{Y}(T)$ for all $m$.  In this case, $\phi^m(T)$ exists and is a separable, valid transversal of $\mathcal{Y}$ that contains $J_3$, for all $m \ge 0$.  The finiteness of the set of valid transversals of $\mathcal{Y}$ implies that there exist integers $p < q$ such that $\phi^p(T) = \phi^q(T)$.  Let $\phi^m(T) = \{(i,b^{(m)}_i) \mid i \in [n]\}$.  Proposition~\ref{FullPhi} implies that $\left(b^{(m)}_1,b^{(m)}_2,\ldots,b^{(m)}_n\right) > \left(b^{(m+1)}_1,b^{(m+2)}_2,\ldots,b^{(m+1)}_n\right)$ in the lexicographic order for all $m \ge 0$.  Therefore, we have $\left(b^{(p)}_1,b^{(p)}_2,\ldots,b^{(p)}_n\right) > \left(b^{(q)}_1,b^{(q)}_2,\ldots,b^{(q)}_n\right)$ in the lexicographic order, which contradicts the assumption that $\phi^p(T) = \phi^q(T)$.  Hence, we can conclude that there exists an integer $m$ such that $\phi^m(T) \in S_\mathcal{Y}(J_3)$.

Let $M$ be the smallest integer $m$ such that $\phi^m(T) \in S_\mathcal{Y}(J_3)$.  Then, let $\Phi(T) = \phi^m(T)$,
and $\Phi$ defines a function from $S_\mathcal{Y}(F_3)$ to $S_\mathcal{Y}(J_3)$.  Define $\Psi:S_\mathcal{Y}(J_3)
\rightarrow S_\mathcal{Y}(F_3)$ analogously, using Proposition~\ref{FullPsi}.  We claim that $\Phi$ and $\Psi$ are inverses of each other.  Let $T \in S_\mathcal{Y}(F_3)$, and suppose that $\Phi(T) = \phi^m(T)$.  By $m$ applications of Proposition~\ref{FullPhi},
we have $\psi^m(\Phi(T)) = T$, and because $\psi(W)$ is defined only for $W \notin S_\mathcal{Y}(F_3)$,
we have $\Psi(\Phi(T)) = \psi^m(\Phi(T)) = T$.  A similar argument using Proposition~\ref{FullPsi}
demonstrates that $\Phi(\Psi(T)) = T$ for all $T \in S_\mathcal{Y}(J_3)$, and therefore $\Phi$ and $\Psi$
define inverse bijections.

Suppose that $\mathcal{Y'} = (Y',A',D')$ is a 1-semialternating AD-Young diagram, and let
$Y' = (Y'_1,Y'_2,\ldots,Y'_n)$.  If $1 \notin D'$,
then it is clear that $\mathcal{Y'}$ is 1-alternating and $\left|S_\mathcal{Y}(F_3)\right| = \left|S_\mathcal{Y}(J_3)\right|.$  If
$1 \in D$, then let $Y = (Y'_1+1,Y'_1+1,Y'_2+1,Y'_3+1,\ldots,Y'_n+1)$, let $A = \{1\} \cup (A' + 1)$,
and let $D' = D + 1$.  The AD-Young diagram $\mathcal{Y} = (Y, A, D)$ is 1-alternating.
For $T' = \{(i,b'_i)\}$ a valid transversal of $\mathcal{Y'}$, let $\alpha(T) = \{(1,1)\} \cup \{(i+1,b'_i+1) \mid i \in [n]\}$.  It is clear that $\alpha(T)$ is a valid transversal of $\mathcal{Y}$, and that $\alpha$ is injective.
Furthermore, if $T' \in S_{\mathcal{Y}'}(F_3)$ (resp. $S_{\mathcal{Y}'}(J_3)$), then
$\alpha(T') \in S_\mathcal{Y}(F_3)$ (resp. $S_\mathcal{Y}(F_3)$) because $(1,1)$ cannot be an element
of any copy of $F_3$ (resp. $J_3$) in $\alpha(T')$.
Define $\Phi' = \alpha^{-1} \circ \Phi \circ \alpha$.  Lemma~\ref{AddA1}
implies that $\Phi$ sends the range of $\alpha$ to the range of $\alpha$.
Together with the fact that $\alpha$ is injective, it follows that $\Phi'(T)$ is defined (and well-defined) for all $T \in S_\mathcal{Y}(F_3)$.  It is clear that
$\Phi'$ sends $S_{\mathcal{Y}'}(F_3)$ to $S_{\mathcal{Y}'}(J_3)$.  We define $\Psi'$
analogously.  Because $\Phi$ and $\Psi$ are inverses of each other, so are $\Phi'$ and $\Psi'$. Hence, we have
that $\left|S_{\mathcal{Y}'}(F_3)\right| = \left|S_{\mathcal{Y}'}(J_3)\right|$, and the fact
that $F_3 \sesa{1} J_3$ follows.
\end{proof}

\section{Comparison with Backelin \emph{et al.}'s Bijection}
\label{sec:CompareBWX}
Let $Y = (5^5)$, $A = \{3\}$, and $D = \{4\}$, and let $T =\{(1,5),(2,4),(3,1),(4,3),(5,2)\}$
be a transversal of $\mathcal{Y} = (Y, A, D)$.  Then, $T$ avoids $F_3$ but contains $J_3$.
Indeed, we have $h_J(T) = (1,2,3)$, the transversal is of $J$-type 3, and $\phi(T) =
\{(1,3),(2,1),(3,4),(4,5),(5,2)\}$ avoids $J_3$.  Thus, we have
$\Phi(T) = \phi(T)$.  However, Backelin, West, and Xin~\cite{BWX}'s version of $\Phi$ would
send $T$ to $T' = \{(1,3),(2,1),(3,5),(4,2),(5,4)\}$ after two iterations of the corresponding version of $\phi$.  Because $\Phi(T) \not= T'$,
our bijections are not the restrictions of those of Backelin, West, and Xin~\cite{BWX}.  Indeed,
$T'$ is not a valid transversal of $\mathcal{Y}$.  In the case
when the ascent and descent sets of an AD-Young diagram are empty, then
all transversals are of $J$-type and $F$-type 1, and our bijections
agree with those of Backelin, West, and Xin~\cite{BWX}.

%\appendix

\section{Proof of Proposition~\ref{FullPhi}}
\label{sec:PropFullPhi}
Backelin, West, and Xin's proof of \cite[Proposition 3.1]{BWX} involves a subboard $E$.  We consider
a similar board, and it plays a substantial role in the following proofs.
Let $T$ be a separable valid transversal of $\mathcal{Y}$ that contains
$J_3$, and let $h_J(T) = (a_1,a_2,a_3)$.  We define a subset of $Y$ called
$E_\phi(T)$ that will be free of elements of $T$ by the definition of $h_J$.  Let
\[E_\phi(T) =
\left(
\begin{array}{l}
\left([1,a_1) \times [b_{a_2}, Y_{a_3}]\right) \cup \left((a_1,a_2) \times [b_{a_3},b_{a_1}]\right)\\
    \cup \left((a_2,a_3) \times [1,b_{a_2}]\right) \cup \left((a_3, \infty) \times (b_{a_2}, \infty)\right)
\end{array}
\right) \cap Y.\]
The critical property of $E_\phi(T)$ is the following lemma, which plays a critical role
in the proof of Proposition~\ref{FullPhi}.

\begin{lemma} \label{EPhi}
If $T$ is a separable valid transversal of $\mathcal{Y}$ that contains $J_3$, then
$E_\phi(T)$ does not contain any element of $T$.
\end{lemma}
\begin{proof}
If $(i,b_i) \in [1,a_1) \times [b_{a_2}, Y_{a_3}]$, then
$(i,a_2,a_3) \in U(T)$.  If $(i,b_i) \in (a_1,a_2) \times [b_{a_3},b_{a_1}]$,
then $(a_1,i,a_3) \in U(T)$.  If $(i,b_i) \in (a_2,a_3) \times [1,b_{a_2}]$,
then $(a_1,a_2,i) \in U(T)$.  All three contradict the definition of $h_J$.

If $(i,b_i) \in (a_3, \infty) \times (b_{a_2}, \infty)$, then
$v = (a_2,a_3,i)$ is a copy of $F_3$ in $T$.  If $i \in A$, replace
$v$ by $(a_2,a_3,i+1)$.  Then, we have $v \in V(T)$, and
$S(v) \ge (a_3,a_2,0) > (a_3,a_1,a_2) = \#(h_J(T))$ in the lexicographic order,
which contradicts the separability of $T$.
\end{proof}

The following lemma will be used in the proof of Proposition~\ref{FullPhi} for
the case in which $T$ is of $J$-type 2.

\begin{lemma}
\label{JType2L1}
Let $T$ be a separable, valid transversal of $\mathcal{Y}$ of $J$-type 2, and let
$h_J(T) = (a_1,a_2,a_3)$.
Then, $b_{a_2} \le b_{a_3-1}$ and $a_3 - a_1 \ge 3$.
\end{lemma}
\begin{proof}
If $b_{a_2} > b_{a_3-1}$, then $(a_1,a_2,a_3-1) \in U(T)$, which contradicts the definition of
$h_J$.

If $a_3 - a_1 \le 2$, then we have $a_3 = a_1 + 1$
and $a_2 = a_1 + 1$.  Because $\mathcal{Y}$ is 1-alternating and $a_3-1 \in D$, we have
$a_1 = a_3 - 2 \in A$.  Therefore, we have $b_{a_1} < b_{a_2}$, which contradicts the validity of $T$.
\end{proof}

The following lemma will be used repeatedly in the proof of Proposition~\ref{FullPhi}
for the case in which $T$ is of $J$-type 3.

\begin{lemma}
\label{JType3L1}
Let $T = \{(i,b_i)\}$ be a separable, valid transversal of $\mathcal{Y}$ of $J$-type 3,
and let $\phi(T) = \{(i,c_i)\}$.
\begin{enumerate}[label=(\alph*)]
\item If $i \in \Gamma_{[1,a_1)}^{[b_{a_3},b_{a_1}]}(T)$, then $b_{a_3+1} < b_i < b_{a_2}.$
Let $\Gamma_{[1,a_1]}^{[b_{a_3},b_{a_1}]}(T) = \{i_1 < i_2 < \cdots < i_k\}$.  Then $b_{i_1} < b_{i_2} < \cdots < b_{i_k}$ and $c_{i_1} < c_{i_2} < \cdots < c_{i_k}$.
\item Let $\Gamma_{[a_2,a_3)}^{[b_{a_3},b_{a_1}]}(T) = \{i_1 < i_2 < \cdots < i_k\}$, then $b_{i_1} < b_{i_2} < \cdots < b_{i_k}$ and $c_{i_1} < c_{i_2} < \cdots < c_{i_k} < c_{a_3}$.
In particular, if $i \in \Gamma_{[a_2,a_3)}^{[b_{a_3},b_{a_1}]}(T)$, then
$b_{a_2} \le b_i$.
\end{enumerate}
\end{lemma}
\begin{proof}
First, we prove part (a).  Let $i \in \Gamma_{[1,a_1)}^{[b_{a_3},b_{a_1}]}(T)$.
If $b_i \le b_{a_3+1}$, then $(i,a_3,a_3+1) \in V(T)$ and $S(i,a_3,a_3+1) = (a_3+2,i,0) > (a_3,a_1,a_2)$
in the lexicographic order, which contradicts the separability of $T$.  The fact
that $b_i \ge b_{a_2}$ follows from Lemma~\ref{EPhi}.  If $j < j'$ with $b_{i_j} > b_{i_{j'}}$, then $(i_j,i_{j'},a_3) \in U(T)$, which contradicts the definition of $h_J$.
Because $c_{i_j} = b_{i_{j+1}}$ for $j \in [k-1]$, it suffices to prove that $c_{i_1} < c_{i_2}$.  This follows
from $c_{i_1} = b_{a_3 + 1} < b_{i_1} = c_{i_2}$.

The proof of part (b) is similar.  If $j < j'$ with $b_{i_j} < b_{i_{j'}}$
then $(a_1,i_j,i_{j'}) \in U(T)$, which contradicts the definition of $h_J$.  Once again,
to finish it suffices to prove that $c_{i_1} < c_{i_2}$, but this follows from $c_{i_1} = b_{a_3} < b_{i_1} = c_{i_2}$.
\end{proof}

\begin{proof}[Proof of Proposition~\ref{FullPhi}]
We divide into cases based on the $J$-type of $T$.  Let $h_J(T) = a = (a_1,a_2,a_3)$.

\subsection{$T$ is of $J$-type 1}

See Figure~\ref{fig:JType1}.  First, we prove that $\phi(T)$ is a valid transversal of $\mathcal{Y}$.
To verify that if $i \in A$ (resp. $i \in D$) then $i \in \asc(\phi(T))$ (resp. $i \in \des(\phi(T))$), we divide into cases based on the value of $i$.

\begin{figure}[!h]
\center{
%\ytableausetup{boxsize = 1.133em}
\begin{ytableau}
\none[1] &\none & &&\none[\cdots]& &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[2] &\none & &&\none[\cdots]& &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots] &\none[\vdots]\\
\none[a_1-1] &\none & &&\none[\cdots]& &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[a_1] &\none &&& \none[\cdots] &&&&&\none[\cdots]&& \times & & & \none[\cdots] & & \blacksquare & \none[\cdots] && \none[\cdots]\\
\none[a_1+1] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_1+2] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[a_2-1] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_2] &\none &&& \none[\cdots] &&\times &&& \none[\cdots] && \blacksquare&&&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_2+1] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray) &&&&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_2+2] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray) &&&&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[a_3-1] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray) &&&&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_3] &\none &&& \none[\cdots] &&\blacksquare &&&\none[\cdots]&&&&&\none[\cdots] && \times & \none[\cdots] &\\
\none[a_3+1] &\none &&& \none[\cdots] &&&&&\none[\cdots]&& & *(gray) &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots] \\
\none[a_3+2] &\none &&& \none[\cdots] &&&&&\none[\cdots]&& & *(gray) &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots] \\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots]\\
\end{ytableau}}
\caption{The squares marked with a solid black box are the elements of the chosen copy of $J_3$ for a separable, valid transversal $T$ of $J$-type 1.  The crosses mark new elements of $\phi(T)$, i.e. elements of $\phi(T) \setminus T$, while the gray squares are free of elements of $T$ (and $\phi(T)$).}
\label{fig:JType1}
\end{figure}

\begin{casework}
\item $\{i,i+1\} \cap \{a_1,a_2,a_3\} = \emptyset$.
Because $(a_1,a_2,a_3)$ is a copy of $J_3$ in $T$, we have $(a_3,b_{a_1}) \in Y$,
which implies that $\phi(T)$ is a transversal of $Y$.  If $\{i,i+1\} \cap \{a_1,a_2,a_3\} = \emptyset$,
then we have $b_i = c_i$ and $b_{i+1} = c_{i+1}$, so $i$ is an ascent (resp. descent) of $T$
if and only if $i$ is an ascent (resp. descent) of $\phi(T)$.

\item $i = a_1-1$.
By Lemma~\ref{EPhi}, we have that $b_{a_1-1} \notin [b_{a_2}, b_{a_1}]$, which implies
that $a_1-1$ is an ascent (resp. descent) of $\phi(T)$ if and only if it is an ascent (resp. descent) of $T$.

\item $i = a_1$.
By Lemma~\ref{EPhi},
we have $b_{a_1+1} \notin [b_{a_3}, b_{a_1}]$.  Provided that
$a_2 \not= a_1 + 1,$ this implies
that $a_1$ is an ascent (resp. descent) of $\phi(T)$ if and only if it is an ascent (resp. descent) of $T$.  However,
if $a_2 = a_1 + 1$, then it is clear $a_1$ is a descent of both $T$ and $\phi(T)$.

\item $i = a_2-1 \not= a_1$.
Because $a_2 \not= a_1 + 1$, Lemma~\ref{EPhi} implies that
$b_{a_2-1} < b_{a_3} (= c_{a_2}) < b_{a_2}$.  Therefore, $a_2-1$
is an ascent of both $T$ and $\phi(T)$.

\item $i = a_2$.  If $a_3 \not= a_2 + 1$, then by Lemma~\ref{EPhi},
we have $b_{a_2+1} > b_{a_2} > b_{a_3} = c_{a_2}$,
which implies that $a_2+1$ is an ascent of both $T$ and $\phi(T)$.  If $a_3 = a_2 + 1$,
then we have $a_2 \notin D$ by definition, and because $b_{a_2} > b_{a_3}$, we have
$a_2 \notin A$.

\item $i = a_3-1$.
By Lemma~\ref{EPhi}, we have $b_{a_3-1} \ge b_{a_2} > b_{a_3}$, which implies that
$a_3 - 1 \notin A$.

\item $i = a_3$.
Because $\mathcal{Y}$ is 1-alternating, we have $a_3 \notin D$,
and we also have $a_3 \notin A$ by the definition of $J$-type. 
\end{casework}
It follows
that $\phi(T)$ is a valid transversal of $\mathcal{Y}$.

Next, we prove that $h_F(\phi(T)) = a$.  It is clear that $a \in V(\phi(T))$,
and because $a_3 - 1 \notin A$, we have $S(a) = (a_3, a_1, a_2)$.  Suppose that
$a' = (a'_1,a'_2,a'_3) \in U(T)$ with $S(a') > S(a)$ in the lexicographic order.
Because $a_3 - 1 \notin A$, we must have $a'_3 \ge a_3$.  If $a'_3 > a_3$,
then we have $c_{a'_3} = b_{a'_3} < b_{a_2}$ by Lemma~\ref{EPhi}.  For $i \in [2],$ let
\[d_i = \begin{cases}
a_3 & \text{ if } a'_i = a_2\\
a'_i  & \text{ otherwise.}\end{cases}\]
Because $b_{a'_2} < b_{a_2}$, we have $a'_2 \notin (a_2,a_3)$ by Lemma~\ref{EPhi},
from which it follows that $d_1 < d_2$.  We have $b_{d_i} = b_{a'_i}$ for $i \in [2]$,
which implies that $v = (d_1,d_2,a'_3) \in V(T)$.  Because $a_3 \notin A$, the first
component of $S(v)$ is greater than $a_3$, and this contradicts the definition of $h_F$.
Hence, we may assume that $a'_3 = a_3$, and because
$a_3-1 \notin A$, the first component of $S(a')$ is $a_3$.  If $a'_1 > a_1$, then $(a_1,a'_1,a'_2) \in U(T)$, which contradicts the definition of $h_J$.
If $a'_1 = a_1$, then Lemma~\ref{EPhi} implies that $a'_2 \le a_2$.  The fact
that $h_F(T) = a$ follows by the definition of $h_F$.  It is clear that $\phi(T)$
is of $F$-type 1 and that $\psi(\phi(T)) = T$.

We prove that if $e = (e_1,e_2,e_3) \in U(\phi(T))$, then we have $\#(e) > \#(a)$
in the lexicographic order.  Assume for sake
of contradiction that $\#(e) \le \#(a)$ in the
lexicographic order.  If $e_3 < a_3$, then we derive
contradictions by dividing into cases based on the relative
values of $c_{e_3}$ and $c_{a_1}$.
\begin{casework}
\item $c_{e_3} > c_{a_1}$.  We have
$c_{e_i} = b_{e_i}$ for all $i$.  Therefore, $(e_1,e_2,e_3) \in U(T)$, which contradicts
the definition of $h_J$.

\item $c_{e_3} = c_{a_1}$.  We have
$e_3 = a_1$ and $b_{e_2} = c_{e_2} > Y_{a_3} \ge b_{a_1}$ by Lemma~\ref{EPhi}.  Hence, $e \in U(T)$, which contradicts
the choice of $a$.

\item $c_{e_3} < c_{a_1}$. We have $e_3 \le a_2$ by Lemma~\ref{EPhi}.  Therefore, we can include this case in the following cases.

\item $e_3 < a_2$.  Assume for sake of deriving a contradiction that $b_{e_3} \not= c_{e_3}$.  Then, we have $e_3 = a_1$ and
$c_{e_3} = c_{a_1}$, which we have shown to be impossible in a prior case.  It follows that $b_{e_3} = c_{e_3}$.

Assume for sake of deriving a contradiction that $e_2 = a_1$.  Then,
we have \[b_{e_1} = c_{e_1} > Y_{a_3} \ge b_{a_1} > b_{e_3} = c_{e_3}\]
by Lemma~\ref{EPhi}.  Because $e_2 = a_1$, we have $e \in U(T)$, which contradicts the choice of $a$. Hence,
we may assume that $e_2 \not= a_1$.

Because $Y_{e_3} \ge Y_{a_3} \ge b_{a_1} > c_{a_1}$ holds, we have $(e_1,e_2,e_3) \in U(T)$ regardless of whether $a_1$ equals $e_1$.  This contradicts the choice of $a$.

\item $e_3 = a_2$ and $c_{e_1} < c_{a_1}$.  We have $(e_1,e_2,a_3) \in U(T)$,
which contradicts the choice of $a$.

\item $e_3 = a_2$ and $c_{e_1} = c_{a_1}$.  By
Lemma~\ref{EPhi} and because $e_1<e_2<e_3$, we have
$c_{e_2} \le c_{a_2} = c_{a_3}$, which contradicts
the assumption that $e \in U(\phi(T))$.

\item $e_3 = a_2$ and $c_{e_1} > c_{a_1}$. then we have $c_{e_1} = b_{e_1}
> Y_{a_3} \ge b_{a_1}$ by Lemma~\ref{EPhi}, which implies that $(e_1,a_1,a_2) \in U(T)$,
contradiction.
\end{casework}
Hence, we may assume that $e_3 = a_3$.  If $e_1 \le a_1$,
we have $c_{e_1} \le c_{a_1} < c_{a_3}$ by Lemma~\ref{EPhi}, which contradicts the assumption that $e \in U(\phi(T))$.  Because
$c_{a_1} < c_{a_3}$, it is impossible
for $e_1$ to equal $a_1$.  Therefore, we have $e_1 > a_1$, and the separability of $\phi(T)$ follows.

We have $b_i = c_i$ for all $i < a_1$, and $b_{a_1} > b_{a_2} = c_{a_1}$.  Therefore,
$(b_1,b_2,\ldots,b_n) > (c_1,c_2,\ldots,c_n)$ in the lexicographic order.

\subsection{$T$ is of $J$-type 2}

See Figure~\ref{fig:JType2}.  First, we prove that $\phi(T)$ is a valid transversal of $\mathcal{Y}$.
Because $Y_{a_3-1} \ge Y_{a_3} \ge b_{a_1},$ the set $\phi(T)$ is a transversal of $Y$.
To verify that if $i \in A$ (resp. $i \in D$) then $i \in \asc(\phi(T))$ (resp. $i \in \des(\phi(T))$), we divide into cases based on the value of $i$.

\begin{figure}[!h]
\center{
\begin{ytableau}
\none[1] &\none & &&\none[\cdots]& &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[2] &\none & &&\none[\cdots]& &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots] &\none[\vdots]\\
\none[a_1-1] &\none & &&\none[\cdots]& &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[a_1] &\none &&& \none[\cdots] &&&&&\none[\cdots]&&&&& \none[\cdots] &&\none[\cdots] &\times &\none[\cdots] &&\blacksquare & \none[\cdots] && \none[\cdots]\\
\none[a_1+1] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_1+2] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[a_2-1] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_2] &\none &&& \none[\cdots] &&&&& \none[\cdots] && \blacksquare&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_2+1] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray) &&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_2+2] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray) &&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[a_3-2] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray) &&&&\none[\cdots] &\bullet &\none[\cdots] &&\none[\cdots] &&& \none[\cdots] &\\
\none[a_3-1] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray) &&&&\none[\cdots] &&\none[\cdots] &\bullet &\none[\cdots] &&\times & \none[\cdots] &\\
\none[a_3] &\none &&& \none[\cdots] &&\blacksquare &&&\none[\cdots]&&&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] &\\
\none[a_3+1] &\none &&& \none[\cdots] &&&&&\none[\cdots]&& & *(gray) &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots] \\
\none[a_3+2] &\none &&& \none[\cdots] &&&&&\none[\cdots]&& & *(gray) &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots] \\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots]\\
\end{ytableau}}
\caption{The squares marked with a solid black box are the elements of the chosen copy of $J_3$ for a separable, valid transversal $T$ of $J$-type 2. The bullets mark other elements of $T$, and the crosses mark new elements of $\phi(T)$, i.e. elements of $\phi(T) \setminus T$.  The gray squares are free of elements of $T$ (and $\phi(T)$).}
\label{fig:JType2}
\end{figure}

\begin{casework}
\item $\{i,i+1\} \cap \{a_1,a_3-1\} = \emptyset$.  We have $b_i = c_i$ and $b_{i+1} = c_{i+1}$,
and thus $i$ is an ascent (resp. descent) of $T$ if and only if it is an ascent (resp. descent)
of $\phi(T)$.

\item $i = a_1-1, a_1$.  By Lemma~\ref{EPhi}, we have $b_{a_1-1}, b_{a_1+1} \notin [b_{a_2}, b_{a_1}] \subseteq [b_{a_3-1}, b_{a_1}] = [c_{a_1},b_{a_1}]$, where the subset relation holds by Lemma~\ref{JType2L1}.  By Lemma~\ref{JType2L1}
again, we have $a_3 - 1 > a_1 + 1$, and it follows that $b_{a_1+1} = c_{a_1+1}$
and $b_{a_1-1} = c_{a_1-1}$.  Therefore, $i$ is an ascent (resp. descent) of $\phi(T)$
if and only if it is an ascent (resp. descent) of $T$, for $i = a_1-1,a_1$.

\item $i = a_3-2, a_3-1$. We have $c_{a_3-1} = b_{a_1} > b_{a_3-1} > b_{a_3-2},b_{a_3}$.  By Lemma~\ref{JType2L1}, we have that $a_3-2 > a_1$,
which yields that $b_{a_3-2} = c_{a_3-2}$ and $b_{a_3} = c_{a_3}$.  Therefore,
$a_3 - 2$ is an ascent of $\phi(T)$ and $a_3-1$ a descent. 
\end{casework}
It follows that $\phi(T)$
is a valid transversal of $\mathcal{Y}$, as desired.

Next, we prove that $h_F(\phi(T)) = (a_1, a_3-2, a_3-1)$.  It is clear that $(a_1,a_3-2,a_3-1) \in V(\phi(T))$,
and we have $S(a_1,a_3-2,a_3-1) = (a_3,a_1,0)$.  Suppose for sake of deriving a contradiction
that $d = (d_1,d_2,d_3) \in V(T)$ with $S(d) > (a_3,a_1,0)$ in the lexicographic order.
If $d_3 > a_3$, then by Lemma~\ref{EPhi}, we have $c_{d_3} = b_{d_3} < b_{a_2}$.  This implies
that $b_{d_i} = c_{d_i}$ for $i = 1, 2$ and it follows that $(d_1,d_2,d_3) \in V(T)$.
If $d_1 < a_1$, then the second component of $S(d)$ is less than $a_1$, which implies that
first component of $S(d)$ is greater than $a_3$.  It follows that $S(d) > (a_3,a_1,a_2)$ in
the lexicographic order, which contradicts the separability of $T$.  It is clear that
$d_1 \not= a_1$.  If $d_1 > a_1$, then $(a_1,e_1,e_2) \in U(T)$, which contradicts the
definition of $h_J$.  Thus, we have $h_F(\phi(T)) = (a_1,a_3-2,a_3-1)$.  It follows
that $\phi(T)$ is of $F$-type 2, and it is clear that $\psi(\phi(T)) = T$.

We prove that if $e = (e_1,e_2,e_3) \in U(\phi(T))$, then $\#(e) \ge (a_3,a_1,0)$
in the lexicographic order.  Let $e \in U(\phi(T))$.  First, we claim
that $e_2 \not= a_1$.  Assume
for sake of deriving a contradiction that $e_2 = a_1$.  The fact that $c_{a_1} < c_{a_3-1}$ implies that $e_3 \not= a_3-1$.
By Lemma~\ref{EPhi} we have $b_{e_1} > b_{a_1}$, which implies
that $(e_1,e_2,e_3) \in U(T)$.  This contradicts the choice of $a$.  Hence, we have $e_2 \not= a_1$.  Assume
for sake of deriving a contradiction that $e_3 < a_3$.
We divide into cases based on the values
of $e_1,e_2,e_3$ to derive contradictions.
\begin{casework}
\item $e_3 < a_3-1$.
We have $(e_1,e_2,e_3) \in U(T)$ because $b_{e_i} = c_{e_i}$ for $i =2, 3$ and $b_{e_1} \ge c_{e_1}$, which contradicts the choice of $a$.
\item $e_3 = a_3-1$. The fact
that $c_{a_1} < c_{a_3}$ implies that $e_1,e_2 \not= a_1$ and $b_{e_i} = c_{e_i}$ for $i = 1, 2$.
Because $b_{a_3-1} < c_{a_3-1}$, we have $(e_1,e_2,e_3) \in U(T)$, which contradicts the choice of $a$.
\end{casework}
Hence, we may assume that $e_3 = a_3$.  If $\{e_1,e_2\}$ and $\{a_1,a_3-1\}$ are disjoint,
then clearly we have $(e_1,e_2,e_3) \in U(T)$,
which implies that $\#(e) \ge \#(a)$ by the choice of $a$.  It is impossible for $e_1$ to equal $a_3-1$,
and if $e_2 = a_3-1$, then we have $e_1 \not= a_1$ and hence $(e_1,e_2,e_3) \in U(T)$,
which contradicts the choice of $a$.  If $e_1 = a_1$, then the fact that $b_{a_1} > c_{a_1}$ implies that
$(e_1,e_2,e_3) \in U(T)$, which contradicts the choice of $a$.  We have already dealt with the case of $e_2 = a_1$.
Hence, the separability of $T$ follows.

We have $b_i = c_i$ for all $i < a_1$, and $b_{a_1} > b_{a_3-1} = c_{a_1}$.  Therefore,
$(b_1,b_2,\ldots,b_n) > (c_1,c_2,\ldots,c_n)$ in the lexicographic order.

\subsection{$T$ is of $J$-type 3}

See Figure~\ref{fig:JType3}.  We first prove that $\phi(T)$ is a valid transversal of $\mathcal{Y}$.  Because
$Y_{a_3+1} = Y_{a_3} \ge b_{a_1}$, the set $\phi(T)$ is a transversal of $Y$.
To verify that if $i \in A$ (resp. $i \in D$) then $i \in \asc(\phi(T))$ (resp. $i \in \des(\phi(T))$), we divide into cases based on the value of $i$.

\begin{figure}[H]
\center{
\begin{ytableau}
\none[1] &\none & &&\none[\cdots]& &&*(gray)&*(gray)&\none[\cdots] &*(gray)&*(gray)&\none[\cdots]&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray)&*(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[2] &\none & &&\none[\cdots]& &&*(gray)&*(gray)&\none[\cdots] &*(gray)&*(gray)&\none[\cdots]&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray)&*(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots] &\none[\vdots]\\
\none[i_1] &\none & &&\none[\cdots]& &&*(gray)&*(gray)&\none[\cdots] &*(gray)&\times &\none[\cdots]&\bullet&&\none[\cdots]&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots] &\none[\vdots]\\
\none[i_2] &\none & &&\none[\cdots]& &&*(gray)&*(gray)&\none[\cdots] &*(gray)&& \none[\cdots]&\times&&\none[\cdots]&\bullet&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots] &\none[\vdots]\\
\none[a_1-1] &\none & &&\none[\cdots]& &&*(gray)&*(gray)&\none[\cdots] &*(gray)&&\none[\cdots]&&&\none[\cdots] &&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[a_1] &\none &&& \none[\cdots] &&&&&\none[\cdots] &&&\none[\cdots]&&&\none[\cdots]&\times&\none[\cdots]&&&&& \none[\cdots] &&\none[\cdots] &&\none[\cdots] &&\blacksquare & \none[\cdots] && \none[\cdots]\\
\none[a_1+1] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] &*(gray)&*(gray)&\none[\cdots]&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_1+2] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] &*(gray)&*(gray)&\none[\cdots]&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[a_2-1] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] &*(gray)&*(gray)&\none[\cdots]&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_2] &\none &&& \none[\cdots] &&\times&&& \none[\cdots] &&&\none[\cdots]&&&\none[\cdots]&&\none[\cdots] && \blacksquare&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_2+1] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray)&*(gray)&\none[\cdots]&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray) &&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_2+2] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray)&*(gray)&\none[\cdots]&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray) &&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[i'_1] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray)&*(gray)&\none[\cdots]&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray) &\times&&&\none[\cdots] &\bullet&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[i'_2] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray)&*(gray)&\none[\cdots]&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray) &&&&\none[\cdots] &\times&\none[\cdots] &\bullet&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[a_3-1] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray)&*(gray)&\none[\cdots]&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray) &&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_3] &\none &&& \none[\cdots] &&\blacksquare &&&\none[\cdots]&&&\none[\cdots]&&&\none[\cdots]&&\none[\cdots] &&&&&\none[\cdots]  &&\none[\cdots] &\times&\none[\cdots] &&& \none[\cdots] &\\
\none[a_3+1] &\none &&& \none[\cdots] &&&&&\none[\cdots]&&\bullet&\none[\cdots]&&&\none[\cdots]&&\none[\cdots] &&&&&\none[\cdots]  &&\none[\cdots] &&\none[\cdots] &&\times& \none[\cdots] &\\
\none[a_3+2] &\none &&& \none[\cdots] &&&&&\none[\cdots]&&&\none[\cdots]&&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]
&*(gray)&*(gray) & *(gray) &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots] \\
\none[a_3+3] &\none &&& \none[\cdots] &&&&&\none[\cdots]&&&\none[\cdots]&&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]
&*(gray)&*(gray) & *(gray) &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots] \\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots]\\
\end{ytableau}}
\caption{The squares marked with a solid black box are the elements of the chosen copy of $J_3$ for a separable, valid transversal $T$ of $J$-type 3.  The bullets mark some other elements of $T$, while the crosses mark new elements of $\phi(T)$, i.e. elements of $\phi(T) \setminus T$.  The gray squares are free of elements of $T$ (and $\phi(T)$).
We suppose that $\Gamma_{[1,a_1)}^{[b_{a_3},b_{a_1}]}(T) = \{i_1,i_2\}$ and $\Gamma_{(a_2,a_3)}^{[b_{a_3},b_{a_1}]}(T) = \{i'_1,i'_2\}$.}
\label{fig:JType3}
\end{figure}

\begin{casework}
\item $\{i,i+1\}$ and $\Gamma_{[1,a_1] \cup [a_2,a_3+1]}^{[b_{a_3},b_{a_1}]}(T)$ are disjoint.
We have $b_i = c_i$ and $b_{i+1} = c_{i+1},$ and thus
$i$ is an ascent (resp. descent) of $\phi(T)$ if and only if it is an ascent (resp. descent) of $T$.

\item $i, i+1 \in \Gamma_{[1,a_1] \cup [a_2,a_3]}^{[b_{a_3},b_{a_1}]}(T)$ with $i \not= a_1,a_3-1$.
By Lemma~\ref{JType3L1}, we have $b_i < b_{i+1}$ and $c_i < c_{i+1}$.

\item $i \in K = \Gamma_{[1,a_1] \cup [a_2,a_3]}^{[b_{a_3},b_{a_1}]}(T)$, $i+1 \notin K$, and $i \not= a_1,a_3$. We have $b_{a_3} < b_i,c_i < b_{a_1}$.  Furthermore, we have $b_{i+1} \notin [b_{a_3},b_{a_1}],$ and therefore
$c_i \notin [b_{a_3},b_{a_1}]$.  It follows that $i$ is an ascent (resp. descent) of $\phi(T)$ if and only if
it is (resp. descent) of $T$.

\item $i \notin K = \Gamma_{[1,a_1] \cup [a_2,a_3]}^{[b_{a_3},b_{a_1}]}(T)$, $i+1 \in K$, and $i \not= a_1,a_2-1,a_3$.  The argument is similar to the preceding case.

\item $i = a_1,a_2-1$.  Because $b_{a_1+1}, b_{a_2-1} \notin [b_{a_3},b_{a_1}]$ by Lemma~\ref{EPhi},
we have $b_{a_1+1} < b_{a_1}$ if and only if $b_{a_1+1} < c_{a_1}$, and $b_{a_2-1} < b_{a_2}$
if and only if $b_{a_2-1} < c_{a_2}$.  If $a_2 \not= a_1+1$, then
we have $c_{a_1+1} = b_{a_1+1}$ and $c_{a_2-1} = b_{a_2-1}$, which implies that
that $a_1$ is an ascent (resp. descent) of $\phi(T)$ if and only if it is an ascent (resp. descent)
of $T$, and similarly for $a_2-1$.  If $a_2 = a_1 + 1$, then $a_1 = a_2-1$ is a descent of both $T$ and $\phi(T)$.

\item $i = a_3,a_3+1$.
We have $a_3 \in A$, and because $\mathcal{Y}$ is 1-alternating, we have $a_3 + 1 \in D$ and $a_3-1 \notin A$.
By the definition of $F$-type we have $a_3-1 \notin D$ or ($b_{a_3-1} > b_{a_1} > c_{a_3})$.
Furthermore, we have $c_{a_3} < b_{a_1} = c_{a_3+1}$ and $c_{a_3+1} = b_{a_1} > b_{a_3+1} > b_{a_3+2} = c_{a_3+2}$
by the definition of $J$-type and Lemma~\ref{EPhi}.
\end{casework}
It follows that $\phi(T)$ is a valid transversal of $\mathcal{Y}$.

Next, we prove that $h_F(\phi(T)) = (a_1,a_2,a_3+1)$.  It is clear
that $(a_1,a_2,a_3+1) \in V(\phi(T))$ and $S(a_1,a_2,a_3+1) = (a_3,a_1,a_2) = \#(a)$.
Let $(d_1,d_2,d_3) \in V(\phi(T))$
and suppose for sake of deriving a contradiction that $S(d) > \#(a)$ in the lexicographic order.  We divide into cases based
on the values of $d_2,d_3,b_{d_3}$ to prove that
$d_3 \le a_3+1$.
\begin{casework}
\item $d_3 > a_3+1$ and $b_{d_3} > b_{a_3+1}$. We have $(a_3+1,a_3+2,d_3) \in V(T)$ because
$a_3 +1 \in D$.  This contradicts
the separability of $T$ because $S(a_3+1,a_3+2,d_3) \ge (a_3+2,a_1,0)$ in the lexicographic order.

\item $d_3 > a_3 + 1$, $b_{d_3} < b_{a_3+1}$, and $d_1,d_2 \not= a_2$.  We have $b_{d_i} = c_{d_i}$ for all $i$.  It follows that $(d_1,d_2,d_3) \in V(T)$, which contradicts the separability of $T$.

\item $d_3 > a_3 + 1$, $b_{d_3} < b_{a_3+1}$, and $d_1 = a_2$.  Lemma~\ref{EPhi}
implies that $d_2 > a_3$.  Therefore, we have $(a_3,d_2,d_3) \in V(T)$,which contradicts the separability of $T$.

\item $d_3 > a_3 + 1$, $b_{d_3} < b_{a_3+1}$, and $d_2 = a_2$.  We have $(d_1,a_3,d_2) \in V(T)$,
contradiction, which contradicts the separability of $T$.
\end{casework}
Hence, we may assume that $d_3 \le a_3 + 1$.  Because $S(d) > \#(a)$
in the lexicographic order, we have ($d$ is of $F$-type 2, $a_3 - 1 \in D$, $d_2 = a_3 - 2$, and $d_3 = a_3 - 1$) or
$d_3 = a_3 + 1$.
\begin{casework}
\item $d_3 < a_3 + 1$ (the former case). Lemma~\ref{JType3L1} implies that
$b_{d_3} \notin [b_{a_3}, b_{a_1}]$, and the fact that $a_3-1 > a_2$ then yields that $b_{d_3} > b_{a_1}$ by Lemma~\ref{EPhi}.  Because $d_2 = a_3 - 2 > a_2$, we have $b_{d_2} \ge b_{a_2}$ by Lemma~\ref{EPhi}.
Regardless, if $b_{d_1} < b_{a_1}$, then we have $d_1 > a_2$, and it follows that
$c_{d_1} < c_{d_2}$ by Lemma~\ref{JType3L1}, which contradicts the assumption that $d \in V(\phi(T))$.  Hence, we have $b_{d_1} > b_{a_1}$,
which implies that $b_{d_1} = c_{d_1}$.
It is clear that $b_{d_2} \le \max\{c_{d_2}, b_{a_1}\}$, and therefore, we have $(d_1,d_2,d_3) \in V(T)$,
which contradicts the separability of $T$.

\item $d_3 = a_3 + 1$.  If $d_2 = a_3$, then by Lemma~\ref{EPhi} we have $d_1 \ge a_2$, but this implies that $d_1 \in \Gamma_{[a_2,a_3)}^{[b_{a_3},b_{a_1}]}(T)$,
which contradicts Lemma~\ref{JType3L1}.  We may assume that $d_2 \not= a_3$,
which implies that $d$ is of $J$-type 3 and $S(d) = (a_3,d_1,d_2)$.  The fact that
$S(d) > \#(a)$ in the lexicographic order implies that $d_1 \ge a_1$.  We divide into subcases based
on the relative values of $c_{d_1}$ and $b_{a_3}$.
\begin{subcasework}
\item $c_{d_1} > b_{a_3}$.  By Lemma~\ref{EPhi}, we have that $d_1 < a_1$, which contradicts the assumption
that $S(d) > \#(a)$ in the lexicographic order.
\item $c_{d_1} = b_{a_3}$.  We have $b_{d_2} = c_{d_2} < b_{a_3}$ and $a_2 < d_2 < a_3$, but the existence of such a $d_2$
contradicts Lemma~\ref{EPhi}.
\item $c_{d_1} < b_{a_3}$.  We have $c_{d_i} = b_{d_i}$ for $i = 1,2$.  Hence, we have $(d_1,d_2,a_3+1) \in V(T)$, which contradicts the separability of $T$.
\end{subcasework}
\end{casework}
Thus, we can conclude that $h_F(\phi(T)) = (a_1,a_2,a_3+1)$.
It is clear that $\phi(T)$ is of $F$-type 3.  We have $c_{a_2} = b_{a_3}$ and $c_{a_3+1} = b_{a_1}$,
which implies that
\[\psi(\phi(T)) = \theta_{[a_2,a_3]}^{[b_{a_3},b_{a_1}]}\left(\theta_{[1,a_1] \cup \{a_3+1\}}^{[b_{a_3},b_{a_1}]}\left( \omega_{[1,a_1] \cup \{a_3+1\}}^{[b_{a_3},b_{a_1}]}\left(\omega_{[a_2,a_3]}^{[b_{a_3},b_{a_1}]}(T)\right)\right)\right) = T,\]
as desired.

We prove that if $e = (e_1,e_2,e_3) \in U(\phi(T))$, then $e_3 > a_3$.  Let $e \in U(\phi(T))$.  Suppose for sake
of contradiction that $e_3 \le a_3$.
We divide into cases based on the value of $c_{e_3}$
to derive a contradiction.
\begin{casework}
\item $c_{e_3} > b_{a_1}$.  We have $(e_1,e_2,e_3) \in U(T)$, which contradicts the choice of $a$.

\item $b_{a_2} \le c_{e_3} < b_{a_1}.$  By Lemma~\ref{EPhi},
we have $a_2 < e_3 < a_3$.  By Lemma~\ref{JType3L1} and because $e_2 > e_3$ with $c_{e_2} > c_{e_3}$,
we have $b_{e_2} > b_{a_1}$ or $e_2 < a_2$. However, the latter case implies that $b_{e_2} > b_{a_1}$
by Lemma~\ref{EPhi} again.  Then, $(e_1,e_2,e_3) \in U(T)$, which contradicts the choice of $a$.

\item $b_{a_3} < c_{e_3} < b_{a_2}$.  By Lemma~\ref{EPhi} we have $e_3 \le a_1$.
By Lemma~\ref{JType3L1}, we have $b_{e_2} > b_{a_1}$.  It follows that
$(e_1,e_2,e_3) \in U(T)$, which contradicts the choice of $a$.

\item $c_{e_3} = b_{a_3}$. By Lemma~\ref{JType3L1}, we have $b_{e_1} > b_{a_1}$ (because if $b_{e_1} < b_{a_1},$
then $c_{e_1} < c_{e_2}$ by Lemma~\ref{JType3L1}, which contradicts the assumption that $e \in U(\phi(T))$).  This implies
that $(e_1,a_1,a_2) \in U(T)$, which contradicts the choice of $a$.

\item $c_{e_3} < b_{a_3}$. By Lemma~\ref{EPhi}, we have $e_3 < a_2$.
By Lemma~\ref{JType3L1} and because $e_1,e_2 < a_2$, at most one of $c_{e_1},c_{e_2}$ can be an element
of $[b_{a_3},b_{a_1}]$.  It follows that $(e_1,e_2,e_3) \in U(T)$, which contradicts the choice of $a$.
\end{casework}
The separability of $\phi(T)$ follows.

Let $m = \min \Gamma_{[1,a_1]}^{[b_{a_3},b_{a_1}]}(T)$.
We have $b_i = c_i$ for all $i < m$.  Because $b_{a_1} > b_{a_2} > b_{a_3+1}$ by Lemma~\ref{EPhi}, Lemma~\ref{JType3L1} implies that $b_m > b_{a_3+1} = c_{i_1}$.
Therefore, $(b_1,b_2,\ldots,b_n)$ is greater than $(c_1,c_2,\ldots,c_n)$ in the lexicographic order, as desired.
\end{proof}

\section{Proof of Proposition~\ref{FullPsi}}
\label{sec:PropFullPsi}

The proof of Proposition~\ref{FullPsi} is similar to the proof of Proposition~\ref{FullPhi}.  First, we define
$E_\psi(T) \subseteq Y$, which is the analogue $E_\phi(T)$.  Let $T = \{(i,b_i)\}$
be a separable, valid transversal of $\mathcal{Y}$ that contains $F_3$, and let
$h_F(T) = (a_1,a_2,a_3).$  Then, let
\[E_\psi(T) = \left(
\begin{array}{l}
\left([1,a_1) \times [b_{a_1}, Y_{a_3}]\right) \cup \left((a_1,a_2) \times [b_{a_2},b_{a_3}]\right)\\
\cup \left((a_2,a_3) \times [1,b_{a_1}]\right) \cup \left((a_3, \infty) \times (b_{a_1}, \infty)\right)
\end{array}\right) \cap Y.\]
Once again, the critical property of $E_\psi(T)$ is the following lemma.

\begin{lemma} \label{EPsi}
If $T$ is a separable valid transversal of $\mathcal{Y}$ that contains $F_3$, then
$E_\psi(T)$ does not contain any element of $T$.
\end{lemma}
\begin{proof}
If $(i,b_i) \in [1,a_1) \times [b_{a_1}, Y_{a_3}]$, then
$(i,a_1,a_2) \in U(T)$, which contradicts the separability of $T$.
If $(i,b_i) \in (a_1,a_2) \times [b_{a_2},b_{a_3}]$,
then $(i,a_2,a_3) \in V(T)$ and $S(i,a_2,a_3) > S(a_1,a_2,a_3)$ in the lexicographic order.
If $(i,b_i) \in (a_2,a_3) \times [1,b_{a_1}]$,
then $(a_1,i,a_3) \in V(T)$ and $S(a_1,i,a_3) > S(a_1,a_2,a_3)$ in the lexicographic order.
Both contradict the definition of $h_F$.

If $(i,b_i) \in (a_3, \infty) \times (b_{a_1}, \infty)$, then
$v = (a_2,a_3,i)$ is a copy of $F_3$ in $T$.  If $i \in A$, replace
$v$ by $(a_2,a_3,i+1)$.  Then, we have $v \in V(T)$, and
$S(v) > S(h_F(T))$ in the lexicographic order,
which contradicts the definition of $h_F$.
\end{proof}

The analogue of Lemma~\ref{JType3L1} is the following lemma, which will be used repeatedly
in the proof of Proposition~\ref{FullPsi} for the case in which $T$ has $F$-type 3.

\begin{lemma}
\label{FType3L1}
Let $T = \{(i,b_i)\}$ be a separable, valid transversal of $\mathcal{Y}$ of $F$-type 3,
and let $\psi(T) = \{(i,c_i)\}$.
\begin{enumerate}[label=(\alph*)]
\item
Let $\Gamma_{[1,a_1]}^{[b_{a_3},b_{a_1}]}(T) = \{i_1 < i_2 < \cdots < i_k\}$.  Then, $b_{i_1} < b_{i_2} < \cdots < b_{i_k}$ and $c_{i_1} < c_{i_2} < \cdots < c_{i_k}$.  In particular, if $i \in \Gamma_{[1,a_1]}^{[b_{a_2},b_{a_3}]}(T)$, then $b_i \le b_{a_1}.$
\item Let $\Gamma_{[a_2,a_3)}^{[b_{a_2},b_{a_3})}(T) = \{i_1 < i_2 < \cdots < i_k\}$, then $b_{a_1} < b_{i_1} < b_{i_2} < \cdots < b_{i_k}$ and $c_{i_1} < c_{i_2} < \cdots < c_{i_k}$.  Furthermore, we have
    $b_{a_1} < c_{i_2} < \cdots < c_{i_k} < c_{a_3}$.
\end{enumerate}
\end{lemma}
\begin{proof}
First, we prove part (a).  If $j < j'$ with $b_{i_j} > b_{i_j'}$, then $(i_j,i_{j'},a_3-1) \in U(T)$,
which contradicts the separability of $T$.
Because $c_{i_j} = b_{i_{j-1}}$, to prove that $c_{i_1} < c_{i_2} < \cdots < c_{i_k}$
it suffices to prove that $c_{i_1} < c_{i_2}$.  But, if $c_{i_1} > c_{i_2}$, we have
$b_{a_3} = c_{i_1} > c_{i_2} = b_{i_1}$, and therefore $(i_1,a_3-1,a_3) \in V(T)$.  However, then we have
$S(i_1,a_3-1,a_3) = (a_3+1,i_1+1,0)$, which contradicts the definition of $h_F$.
The last sentence follows because $b_{i_k} = b_{a_1}$.

The proof of part (b) is similar.  Let $i_0 = a_1$.  If $j < j'$ with $b_{i_j} > b_{i_{j'}}$, then
$(i_j,i_{j'},a_3-1) \in U(T)$, which contradicts the separability of $T$.  To prove that $c_{i_1} < c_{i_2} < \cdots < c_{i_k}$, it suffices to prove that $c_{i_1} < c_{i_2}$, but this is clear because $c_{i_1} = b_{a_3} < b_{i_1} = c_{i_2}$.  Let $i_{k+1} = a_3$.  The last sentence follows because $c_{i_{j+1}} = b_{i_j}$ for $j \in [k]$.
\end{proof}

The following additional lemma will be also used in proof of Proposition~\ref{FullPsi}
for $T$ of $F$-type 3.

\begin{lemma}
\label{FType3L2}
Let $T$ be a separable, valid transversal of $\mathcal{Y}$ of $F$-type 3,
let $h_F(T) = (a_1,a_2,a_3)$,
and let $m = \min \Gamma_{[1,a_1]}^{[b_{a_2},b_{a_3}]}(T)$.  Then,
the set $(a_3,\infty) \times (b_m,\infty) \cap Y$ does not contain any element of $T$.
\end{lemma}
\begin{proof}
Suppose for sake of deriving a contradiction that $(i, b_i) \in (a_3,\infty) \times (b_m,\infty) \cap Y$.
Then, $(m,a_2,i) \in V(T)$ and $S(m,a_2,i) \ge (a_3,m,0) > (a_3-1,a_1,a_2) = S(h_F(T))$ in the lexicographic
order, which contradicts the definition of $h_F$.
\end{proof}

\begin{proof}[Proof of Proposition~\ref{FullPsi}]
If $x = (x_1,x_2,x_3)$ is a copy of $F_3$ in $T$, then either $x_3 \notin A$
and $x \in V(T)$ or $x_3 \in A$ and $(x_1,x_2,x_3+1) \in V(T)$.  Thus, if $T$
contains $F_3$, then $\psi(T)$ is defined.
We divide into cases based on the $F$-type of $T$.  Let $h_F(T) = a = (a_1,a_2,a_3)$.

\subsection{$T$ is of $F$-type 1}

See Figure~\ref{fig:FType1}.
First, we prove that $\psi(T)$ is a valid transversal of $\mathcal{Y}$.
Because $Y_{a_3} \ge b_{a_1}$, the set $\psi(T)$ is a transversal of $Y$.
To verify that if $i \in A$ (resp. $i \in D$) then $i \in \asc(\psi(T))$ (resp. $i \in \des(\psi(T))$), we divide into cases on the value of $i$.

\begin{figure}[!h]
\center{
\begin{ytableau}
\none[1] &\none & &&\none[\cdots]& &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[2] &\none & &&\none[\cdots]& &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots] &\none[\vdots]\\
\none[a_1-1] &\none & &&\none[\cdots]& &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[a_1] &\none &&& \none[\cdots] &&&&&\none[\cdots]&& \blacksquare & & & \none[\cdots] & & \times & \none[\cdots] && \none[\cdots]\\
\none[a_1+1] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_1+2] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[a_2-1] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_2] &\none &&& \none[\cdots] &&\blacksquare &&& \none[\cdots] && \times&&&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_2+1] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) &&&&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_2+2] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) &&&&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[a_3-1] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) &&&&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_3] &\none &&& \none[\cdots] &&\times &&&\none[\cdots]&&&&&\none[\cdots] && \blacksquare & \none[\cdots] &\\
\none[a_3+1] &\none &&& \none[\cdots] &&&&&\none[\cdots]&& & *(gray) &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots] \\
\none[a_3+2] &\none &&& \none[\cdots] &&&&&\none[\cdots]&& & *(gray) &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots] \\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots]\\
\end{ytableau}}
\caption{The squares marked with a solid black box are the elements of the chosen copy of $F_3$ for a separable, valid transversal $T$ of $F$-type 1.  The crosses mark new elements of $\psi(T)$, i.e. elements of $\psi(T) \setminus T$, and the gray squares are free of elements of $T$ (and $\psi(T)$).}
\label{fig:FType1}
\end{figure}

\begin{casework}
\item $\{i,i+1\} \cap \{a_1,a_2,a_3\} = \emptyset.$ Then, $b_i = c_i$ and $b_{i+1} = c_{i+1}$,
which implies that $i$ is an ascent (resp. descent) of $\psi(T)$ if and only if
it is an ascent (resp. descent) of $T$.

\item $i=a_1-1,a_1,a_2-1$.  By Lemma~\ref{EPsi}, we have
$b_{a_1-1},b_{a_1+1}\notin (b_{a_1},b_{a_3}) = (b_{a_1},c_{a_1}))$, and
$b_{a_2-1},b_{a_2+1} \notin (b_{a_2},c_{a_2})$.  Thus, $t = a_1-1$ is an ascent
(resp. descent) of $\psi(T)$ if and only if it is an ascent (resp. descent) of $T$.
If $a_2 \not= a_1 + 1$, then the same holds for $t = a_1$ and $t = a_2 - 1$,
and if $a_2 = a_1 + 1$, then $a_1 = a_2 - 1$ is a descent of both $T$ and $\psi(T)$.

\item $i=a_2 \not= a_3-1$.
If $a_2 \not= a_3 - 1$, then $a_2$ is an ascent (resp. descent) of $\psi(T)$ if and only if
it is an ascent (resp. descent) of $T$.

\item $i=a_3-1,a_3$.  By the definition of $F$-type and $V(T)$, we have $a_3-1, a_3 \notin A$,
and the fact that $\mathcal{Y}$ is 1-alternating implies that $a_3-1,a_3 \notin D$.  Furthermore,
if $a_2 = a_3 - 1$, then $a_2 \notin A, D$.
\end{casework}
It follows that $\psi(T)$ is a valid transversal of $\mathcal{Y}$.

Next, we prove that $h_J(\psi(T)) = (a_1,a_2,a_3)$.  It is clear that $(a_1,a_2,a_3) \in U(\psi(T))$.  Suppose for sake of deriving a contradiction that $d \in U(\psi(T))$ with $\#(d) < \#(a)$ in the lexicographic
order.  We divide into cases based on the values of $d_3$ and $b_{d_3}$.
\begin{casework}
\item $d_3 < a_1$ or $b_{d_3} > b_{a_3}$. Then, $b_{d_i} = c_{d_i}$ for all $i \in [3]$
and $d \in U(T)$, which contradicts the separability of $T$.
\item  $d_3 = a_1$.  We have $c_{d_3} > b_{d_3}$ and
$b_{d_i} = c_{d_i}$ for all $i\in [2]$.  Therefore, $d \in U(T)$, which contradicts the separability of $T$.
\item $d_3 = a_2$.  We divide into subcases based
on the value of $d_1$.
\begin{subcasework}
\item $d_1 = a_1$.  We have $b_{a_1} < b_{d_2} = c_{d_2} < b_{a_3}$ with $a_1 < d_2  < a_2$,
which contradicts Lemma~\ref{EPsi}.
\item $d_1 \not= a_1$.   We have $b_{d_1} = c_{d_1}$,
as well as $c_{d_2} \ge b_{d_2} > b_{a_2}$.  Therefore, $d \in U(T)$, which contradicts the separability of $T$.
\end{subcasework}
\item $a_1 < d_3 < a_2$ and $b_{d_3} < b_{a_3}$.  Lemma~\ref{EPsi} yields that $b_{d_3} < b_{a_2}$.  We now
divide into subcases based on the value of $d_1$.
\begin{subcasework}
\item $d_1 = a_1$.  Lemma~\ref{EPsi} yields that $b_{d_2} < b_{a_2}$.  Therefore
$d \in U(T)$, which contradicts the separability of $T$.
\item $d_1 \not= a_1$.  We have $b_{d_1} = c_{d_1}$ and \[c_{b_2} \ge b_{d_2} \ge \min\{b_{a_1},c_{d_2}\} > c_{d_3} = b_{d_3}.\] It follows that $d \in U(T)$, which contradicts the separability of $T$.
\end{subcasework}
\item $a_2 < d_3 < a_3$ and $b_{d_3} < b_{a_3}$.  We divide into subcases based on $\{a_1\} \cap \{d_1,d_2\}$.
\begin{subcasework}
\item $d_1 = a_1$. By Lemma~\ref{EPsi}
we have $c_{d_3} = b_{d_3} > b_{a_1} = c_{d_2}$, which yields that $d_2 \not= a_2$.  Furthermore,
by Lemma~\ref{EPsi} again and because $b_{a_1} < b_{d_2} < c_{a_1} = b_{a_3}$, we have $d_2 > a_2$,
but the fact that $(a_1,d_2,a_3) \in V(T)$ contradicts the definition of $h_F$.
\item $d_2 = a_1$.  We have $(d_1,a_1,a_2) \in U(T)$, which contradicts the separability of $T$.
\item $a_1 \notin \{d_1,d_2\}$. We have $d \in U(T)$, which
contradicts the separability of $T$.
\end{subcasework}
\end{casework}

It follows that
$h_J(T) = (a_1,a_2,a_3)$, and it is clear that $\psi(T)$ is of $J$-type 1.  Therefore, we have $\phi(\psi(T)) = T$, as desired.

We prove that if $e = (e_1,e_2,e_3) \in V(\psi(T))$, then $S(e) \le S(a)$ in the lexicographic order.
Suppose for sake of deriving a contradiction that $S(e) > S(a)$ in the lexicographic order.
First, suppose that $e_3 > a_3$, hence that $b_{e_3} = c_{e_3}$.  Furthermore, because $a_3 \notin A$, the first
component of $S(e)$ must be greater than $a_3$.
By Lemma~\ref{EPsi}, we have $b_{e_3} < b_{a_1}$.  We
divide into cases based on the value of $\{e_1,e_2\} \cap \{a_3\}$.
\begin{casework}
\item $e_1 = a_3$.  We have $(a_2,e_2,e_3) \in V(T)$, but the first component of $S(a_2,e_2,e_3)$
is greater than $a_3$, which contradicts the definition of $h_F$.
\item $e_2 = a_3$.  We have $b_{a_2} < c_{e_1} < b_{a_1}$, which yields that $b_{e_1} = c_{e_1}$.
By Lemma~\ref{EPsi}, we have $e_1 < a_1$, and hence $(e_1,a_2,e_3) \in V(T)$, but
the first component of $S(e_1,e_2,e_3)$ is greater than $a_3$, which contradicts the definition of $h_F$.
\item $a_3 \notin \{e_1,e_2\}$.  It follows from Lemma~\ref{EPsi} that $b_{e_i} = c_{e_i}$ for all $i$ and thus $e \in V(T)$, which contradicts the definition of $h_F$. 
\end{casework}
Hence, we may assume
that $e_3 \le a_3$.  Because $S(e) > S(a)$ in the lexicographic order, either
($e$ is of $F$-type 2, $a_3 - 2 \in A$, $e_3 = a_3 - 1$ and $e_2 = a_3 - 2$) or ($e$ is of
$F$-type 1 and $e_3 = a_3$).
\begin{casework}
\item $e$ is of $F$-type 2. Because $a_3 - 2 \ge a_2$, we have $a_3 - 1 \in D$, we have $b_{a_3} < b_{a_3-1}$, which implies that $b_{a_3-1} = c_{a_3-1}$.
Additionally, by Lemma~\ref{EPsi} and because $c_{a_2} = b_{a_1}$, we have
$c_{a_3 - 2} \ge b_{a_1}$, and because $S(e) > S(a)$ in the lexicographic order, we have
$e_1 > a_1$.  Therefore, we have $c_{e_1} > b_{a_1}$ and thus $c_{e_1} = b_{e_1}$.  It is also
clear that $b_{e_2} \le c_{e_2}$.  It follows that $e \in U(T)$, which contradicts the separability of $T$.
\item $e$ is of $F$-type 1.  Because $b_{e_i} < c_{e_3} = b_{a_2}$
for $i \in [2]$, we have $b_{e_i} = c_{e_i}$ for $i \in [2]$.  Therefore, we have $e \in U(T)$, which contradicts the separability of $T$.
\end{casework}
The separability of $\psi(T)$ follows.

For $i < a_1$, we have $b_i = c_i$ and $c_{a_1} = b_{a_3} > b_{a_1}$.  Thus, $(b_1,b_2,\ldots,b_n)$ is less than $(c_1,c_2,\ldots,c_n)$ in the lexicographic order, as desired.

\subsection{$T$ is of $F$-type 2}

See Figure~\ref{fig:FType2}.
First, we prove that $\psi(T)$ is a valid transversal of $\mathcal{Y}$.
It is clear that $\psi(T)$ is a transversal of $Y$.  To verify that if $i \in A$ (resp. $i \in D$) then $i \in \asc(\psi(T))$ (resp. $i \in \des(\psi(T))$), we divide into cases based on the value of $i$.

\begin{figure}[!h]
\center{
\begin{ytableau}
\none[1] &\none & \none[\cdots] &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[2] &\none & \none[\cdots] &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none &\none & \none &\none[\vdots] &\none[\vdots] &\none[\vdots] &\none &\none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none\\
\none[a_1-1] &\none & \none[\cdots] &&&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[a_1] &\none & \none[\cdots] &&&&\none[\cdots]&& \blacksquare & & & \none[\cdots] & & \times & \none[\cdots] && \none[\cdots]\\
\none[a_1+1] &\none & \none[\cdots] && *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_1+2] &\none & \none[\cdots] && *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none &\none & \none &\none[\vdots] &\none[\vdots] &\none[\vdots] &\none &\none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] & \none & \none[\vdots]\\
\none[a_2-1] &\none & \none[\cdots] && *(gray) & *(gray) &\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) & \none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_2] &\none & \none[\cdots] &\blacksquare &&& \none[\cdots] &&&&&\none[\cdots] &&& \none[\cdots] &\\
\none[a_3] &\none & \none[\cdots] &&&&\none[\cdots]&& \times &&&\none[\cdots] && \blacksquare & \none[\cdots] &\\
\none[a_3+1] &\none & \none[\cdots] &&&&\none[\cdots]&& & *(gray) &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots]\\
\none[a_3+2] &\none & \none[\cdots] &&&&\none[\cdots]&& & *(gray) &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots]\\
\none &\none & \none &\none[\vdots] &\none[\vdots] &\none[\vdots] &\none &\none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] \\
\end{ytableau}}
\caption{The squares marked with a solid black box are the elements of the chosen copy of $F_3$ for a separable, valid transversal $T$ of $F$-type 2, and the crosses mark new elements of $\psi(T)$, i.e. elements of $\psi(T) \setminus T$.  The gray squares are free of elements of $T$ (and $\psi(T)$).}
\label{fig:FType2}
\end{figure}

\begin{casework}
\item $\{i,i+1\} \cap \{a_1,a_3\} = \emptyset$.  Then, $b_i = c_i$ and $b_{i+1} = c_{i+1}$,
which implies that $i$ is an ascent (resp. descent) of $\psi(T)$ if and only if
it is an ascent (resp. descent) of $T$.

\item $i = a_1-1,a_1$.  By Lemma~\ref{EPsi}, we have $b_{a_1-1}, b_{a_1+1}
\notin (b_{a_2},b_{a_3}) \supseteq (b_{a_1},c_{a_1})$.  It follows that $a_1-1$
is an ascent (resp. descent) of $\phi(T)$ if and only if it is an ascent (resp. descent)
of $T$, and the same for $a_1$.

\item $i = a_3-1$.  We have $a_3 - 1 \in A$, but we also have
$c_{a_3-1} = b_{a_2} < b_{a_1} = c_{a_3}$ and thus $a_3-1$ is an ascent of $\psi(T)$.

\item $i = a_3$.  Because $\mathcal{Y}$ is 1-alternating,
we have $a_3 \in D$.  However, by Lemma~\ref{EPsi}, we have $c_{a_3+1} = b_{a_3+1} < b_{a_1} = c_{a_3}$,
and thus $a_3$ is a descent of $\psi(T)$.
\end{casework}
It follows that $\psi(T)$ is a valid transversal of $\mathcal{Y}$, as desired.

Next, we prove that there is an integer $y$ such that $h_J(T) = (a_1,y,a_3+1)$.
First, because $Y_{a_3+1} = Y_{a_3} \ge b_{a_3} = c_{a_1}$ and $c_{a_3} = b_{a_1} > c_{a_3+1}$
(which follows from Lemma~\ref{EPsi}),
we have $(a_1,a_3,a_3+1) \in U(\psi(T))$.
Suppose for sake of deriving a contradiction that $d = (d_1,d_2,d_3) \in U(\psi(T))$ with $\#(d) < (a_3+1,a_1,0)$
in the lexicographic order. We divide into
cases based on the values of $d_1,d_2,d_3$ to derive contradictions.
\begin{casework}
\item $d_3 < a_1$ or ($a_1 < d_3 < a_3-1$ and $a_1 \notin\{d_1,d_2\}$).  We
have $b_{d_i} = c_{d_i}$ for all $i \in [3]$, and thus $d \in U(T)$, which contradicts the separability
of $T$.

\item $d_3 = a_1$.  Because $b_{a_1} < b_{a_3} = c_{a_1}$, we have $d \in U(T)$,
contradiction.

\item $d_i = a_1$ for some $i \in [2]$ and $a_3 \notin \{d_1,d_2,d_3\}$.  By Lemma~\ref{EPsi}, we have $b_{d_{i+1}} \notin (b_{a_3},b_{a_1})$.  Therefore, we have $(d_1,d_2,d_3) \in U(T)$, which contradicts the separability of $T$.

\item $d_3 = a_3$ and $a_1 \notin \{d_1,d_2\}$.  It is clear that
$d_2 \not= a_3 - 1$.  Thus, we have $(d_1,d_2,a_3-1) \in U(T)$ because
$b_{d_i} = c_{d_i}$ for $i \in [2]$ and $c_{a_3} > c_{a_3-1} = b_{a_3-1}$.  This contradicts the separability of $T$.

\item $d_3 = a_3$ and $d_1 = a_1$.
We have $a_1 < d_2 < a_3$ with $b_{d_2} \in (b_{a_2},b_{a_3})$, which contradicts Lemma~\ref{EPsi}.

\item $d_3 = a_3$ and $d_2 = a_1$, then we have \[b_{d_1} = c_{d_1} > c_{a_1} = b_{a_3} > b_{a_1} = c_{a_3} > c_{a_3-1} = b_{a_3-1},\] where the last inequality follows from Lemma~\ref{EPsi}.  Hence, we have $(d_1,d_2,a_3-1) \in U(T)$, which contradicts the separability of $T$.
\end{casework}
Hence, we may assume
that $d_3 = a_3 + 1$.  Because $\#(d) < (a_3+1,a_1,0)$, we may also assume that $d_1 < a_1$,
which implies that $b_{d_1} = c_{d_1}$.  Lemma~\ref{EPsi} yields that $b_{d_1} < b_{a_1}$,
and thus $b_{d_i} = c_{d_i}$ for all $i \in [3]$.  It follows that $d \in U(T)$, which contradicts the separability of $T$.  The fact that $h_J(T) = (a_1,y,a_3+1)$ for some $y$ follows.
It is clear that $\psi(T)$ is of $J$-type 2 and that $\phi(\psi(T)) = T$.

We prove that if $e = (e_1,e_2,e_3) \in V(\psi(T))$, then $S(e) \ge S(h_F(T))$ in the lexicographic
order.  If $e_3 = a_3$, then $b_{e_i} = c_{e_i}$ for all $i \in [2]$, and $b_{e_3} > c_{e_3}$.
It follows that $e \in V(T)$, which contradicts the definition of $h_F$.  Hence, we may
assume that $e_3 > a_3$, and it follows that $b_{e_3} = c_{e_3}$.  Lemma~\ref{EPsi} yields
that $b_{e_3} < b_{a_1}$, and thus $c_{e_i} < b_{a_1}$ for all $i$, which yields that
$b_{e_i} = c_{e_i}$ for all $i$. This implies that $e \in V(T)$, which contradicts the definition of $h_F$.  The separability
of $\psi(T)$ follows.

For $i < a_1$, we have $b_i = c_i$.  Because $b_{a_1} < b_{a_3} = c_{a_1}$, we have
$(b_1,b_2,\ldots,b_n) < (c_1,c_2,\ldots,c_n)$ in the lexicographic order, as desired.

\subsection{$T$ is of $F$-type 3}

See Figure~\ref{fig:FType3}.
First, we prove that $\psi(T)$ is a valid transversal of $\mathcal{Y}$.
This paragraph is similar to the first paragraph of the proof of Proposition~\ref{FullPhi}
for the case in which $T$ is of $J$-type 3.
If $b_i > b_{a_3}$ or $i > a_3$, it is clear that $b_i = c_i$, and therefore $T$ is a transversal of $Y$.
To verify that if $i \in A$ (resp. $i \in D$) then $i \in \asc(\psi(T))$ (resp. $i \in \des(\psi(T))$), we divide into cases based on the value of $i$.

\begin{figure}[!h]
\center{
%\ytableausetup{boxsize = 1.175em}
\begin{ytableau}
\none[1] &\none & &&\none[\cdots]& &&*(gray)&*(gray)&\none[\cdots] &*(gray)&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray)&*(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[2] &\none & &&\none[\cdots]& &&*(gray)&*(gray)&\none[\cdots] &*(gray)&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray)&*(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots] &\none[\vdots]\\
\none[i_1] &\none & &&\none[\cdots]& &&*(gray)&*(gray)&\none[\cdots] &*(gray)&\bullet& &\none[\cdots]&\times&\none[\cdots]&&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots] &\none[\vdots]\\
\none[i_2] &\none & &&\none[\cdots]& &&*(gray)&*(gray)&\none[\cdots] &*(gray)&&& \none[\cdots]&\bullet&\none[\cdots]&\times&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots] &\none[\vdots]\\
\none[a_1-1] &\none & &&\none[\cdots]& &&*(gray)&*(gray)&\none[\cdots] &*(gray)&&&\none[\cdots]&&\none[\cdots] &&\none[\cdots] && & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & *(gray)  & \none[\cdots] & *(gray) & & \none[\cdots]\\
\none[a_1] &\none &&& \none[\cdots] &&&&&\none[\cdots] &&&&\none[\cdots]&&\none[\cdots]&\blacksquare&\none[\cdots]&&&&& \none[\cdots] &&\none[\cdots] &&\none[\cdots] &&\times & \none[\cdots] && \none[\cdots]\\
\none[a_1+1] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] &*(gray)&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_1+2] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] &*(gray)&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[a_2-1] &\none &&& \none[\cdots] &&& *(gray) & *(gray) &\none[\cdots] &*(gray)&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] & *(gray) & *(gray) & *(gray) & *(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] & *(gray) & & \none[\cdots] && \none[\cdots]\\
\none[a_2] &\none &&& \none[\cdots] &&\blacksquare&&& \none[\cdots] &&&&\none[\cdots]&&\none[\cdots]&&\none[\cdots] && \times&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_2+1] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray)&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray) &&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_2+2] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray)&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray) &&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[i'_1] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray)&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray) &\bullet&&&\none[\cdots] &\times&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[i'_2] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray)&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray) &&&&\none[\cdots] &\bullet&\none[\cdots] &\times&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots] &\none &\none[\vdots]\\
\none[a_3-2] &\none &*(gray) &*(gray) & \none[\cdots] &*(gray) &*(gray) &*(gray) &*(gray) & \none[\cdots] &*(gray)&*(gray)&*(gray)&\none[\cdots]&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray) &&&&\none[\cdots] &&\none[\cdots] &&\none[\cdots] &&& \none[\cdots] && \none[\cdots]\\
\none[a_3-1] &\none &&& \none[\cdots] &&\times &&&\none[\cdots]&&&&\none[\cdots]&&\none[\cdots]&&\none[\cdots] &&&&&\none[\cdots]  &&\none[\cdots] &\bullet&\none[\cdots] &&& \none[\cdots] &\\
\none[a_3] &\none &&& \none[\cdots] &&&&&\none[\cdots]&&\times&&\none[\cdots]&&\none[\cdots]&&\none[\cdots] &&&&&\none[\cdots]  &&\none[\cdots] &&\none[\cdots] &&\blacksquare& \none[\cdots] &\\
\none[a_3+1] &\none &&& \none[\cdots] &&&&&\none[\cdots]&&&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray)&\none[\cdots]&*(gray)&*(gray)& *(gray) &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots] \\
\none[a_3+2] &\none &&& \none[\cdots] &&&&&\none[\cdots]&&&*(gray)&\none[\cdots]&*(gray)&\none[\cdots] &*(gray)&\none[\cdots]&*(gray)&*(gray)& *(gray) &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &\none[\cdots] &*(gray) &*(gray) & \none[\cdots] \\
\none &\none & \none[\vdots] &\none[\vdots] &\none &\none[\vdots] &\none[\vdots] &\none[\vdots] & \none[\vdots] & \none & \none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none[\vdots]&\none&\none[\vdots]&\none& \none[\vdots] & \none[\vdots] & \none[\vdots] & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none & \none[\vdots] & \none[\vdots]\\
\end{ytableau}}
\caption{The squares marked with a solid black box are the elements of the chosen copy of $F_3$ for a separable, valid transversal $T = \{(i,b_i)\}$ of $F$-type 3.  The bullets mark some other elements of $T$, while the crosses mark new elements of $\psi(T)$, i.e. elements of $\phi(T) \setminus T$.  The gray squares are free of elements of $T$ (and $\psi(T)$). We suppose that $\Gamma_{[1,a_1)}^{[b_{a_2},b_{a_3}]}(T) = \{i_1,i_2\}$ and $\Gamma_{(a_2,a_3-1)}^{[b_{a_2},b_{a_3}]}(T) = \{i'_1,i'_2\}$.}
\label{fig:FType3}
\end{figure}

\begin{casework}
\item $\{i,i+1\}$ and $\Gamma_{[1,a_1] \cup [a_2,a_3]}^{[b_{a_2},b_{a_3}]}(T)$ are disjoint.
Then, $b_i = c_i$ and $b_{i+1} = c_{i+1},$ and thus
$i$ is an ascent (resp. descent) of $\phi(T)$ if and only if it is an ascent (resp. descent) of $T$.
\item $i, i+1 \in \Gamma_{[1,a_1] \cup [a_2,a_3-1]}^{[b_{a_2},b_{a_3}]}(T)$ with $i \not= a_1,a_3-2$.
By Lemma~\ref{FType3L1}, we have $b_i < b_{i+1}$ and $c_i < c_{i+1}$.
\item $i \in K = \Gamma_{[1,a_1] \cup [a_2,a_3-1]}^{[b_{a_2},b_{a_3}]}(T)$, $i+1 \notin K$, and $i \not= a_1,a_3-1$. We have $b_{a_2} < b_i,c_i < b_{a_1}$ and $b_{i+1} \notin [b_{a_2},b_{a_3}],$ which implies that $i$ is an ascent (resp. descent) of $\phi(T)$ if and only if
it is (resp. descent) of $T$.
\item $i \notin K = \Gamma_{[1,a_1] \cup [a_2,a_3-1]}^{[b_{a_2},b_{a_3}]}(T)$, $i+1 \in K$, and $i \not= a_1,a_2-1,a_3-1$.  The argument is similar to that of
the preceding case.
\item $i = a_1,a_2-1$.
Because $b_{a_1+1}, b_{a_2-1} \notin [b_{a_2},b_{a_3}]$ by Lemma~\ref{EPsi},
we have $b_{a_1+1} < b_{a_1}$ if and only if $b_{a_1+1} < c_{a_1}$, and $b_{a_2-1} < b_{a_2}$
if and only if $b_{a_2-1} < c_{a_2}$.
If $a_2 \not= a_1+1$, then
we have $c_{a_1+1} = b_{a_1+1}$ and $c_{a_2-1} = b_{a_2-1}$, which implies that
that $a_1$ is an ascent (resp. descent) of $\psi(T)$ if and only if it is an ascent (resp. descent)
of $T$, and similarly for $a_2-1$.
If $a_2 = a_1 + 1$, then $a_1 = a_2-1$ is a descent of both $T$ and $\psi(T)$.

\item $i = a_3-2,a_3-1,a_3$.
We have $a_3-1 \in A$, and
because $\mathcal{Y}$ is 1-alternating, we have $a_3 \in D$ and $a_3-2 \notin A$.
If $a_3-2 \in D$, we have $b_{a_3-2} > b_{a_3-1}$, and Lemma~\ref{FType3L1} implies that $a_3-2 \notin \Gamma_{[a_2,a_3-1]}^{[b_{a_2},b_{a_3}]}$.  Therefore, we have $c_{a_3-2} = b_{a_3-2} > b_{a_3-1} > c_{a_3-1}$.
Regardless, we have $c_{a_3-1} = b_{a_2}< c_{a_3}$ by the definition of $\psi$.  By Lemma~\ref{FType3L2} and the definition of $\psi$,
we have $c_{a_3+1} = b_{a_3+1} < c_{a_3}$.
\end{casework}
It follows that $\phi(T)$ is a valid transversal of $\mathcal{Y}$.

Next, we prove that $h_J(\psi(T)) = (a_1,a_2,a_3-1)$.  It is clear that
$(a_1,a_2,a_3-1) \in U(\psi(T))$.  Suppose for sake of deriving a contradiction that $(d_1,d_2,d_3) \in U(\psi(T))$
with $\#(d) < (a_3-1,a_1,a_2)$ in the lexicographic order.
We divide into cases based on the values
of $d_3$ and $b_{d_3}$ to prove that $d_3 = a_3-1$.
\begin{casework}
\item $b_{d_3} > b_{a_3}$. We have $b_{d_i} = c_{d_i}$ for all $i \in [3]$,
and thus $d \in U(T)$, which contradicts the separability of $T$.  
\item ($d_3 < a_3 - 1$ and $b_{a_1} < b_{d_3} < b_{a_3}$) or $d_3 = a_2$.  By Lemma~\ref{EPsi},
we have $d_3 \ge a_2$, and Lemma~\ref{FType3L1} yields that that $c_{d_3} > b_{a_1}$.
Then, by Lemma~\ref{FType3L1}, we have $d_2 < a_2$ or  $b_{d_2} > b_{a_3}$.  We treat the two subcases separately.
\begin{subcasework}
\item $d_2 < a_2$.  Because $c_{d_2} > c_{d_3} > b_{a_1}$, we have $d_2 = a_1$ or $b_{d_2} > b_{a_3}$.  If $d_2 = a_1$, then we have $(d_1,a_1,a_2) \in U(T)$, which contradicts the separability of $T$.  If $b_{d_2} > b_{a_3}$, then we can apply the following subcase.
\item $b_{d_2} > b_{a_3}.$ We have $(d_1,d_2,d_3) \in U(T)$, which contradicts the separability of $T$.
\end{subcasework}
\item $d_3 < a_3 - 1$ and $b_{a_2} < b_{d_3} \le b_{a_1}$. By Lemma~\ref{EPsi} we have
$d_3 \le a_1$.  Lemma~\ref{FType3L1} implies that $b_{d_2} > b_{a_3}$, from which
it follows that $c_{d_2} = b_{d_2} > b_{a_3} > b_{d_3}$.  Therefore, we have $(d_1,d_2,d_3) \in U(T)$,
which contradicts the separability of $T$.
\item $d_3 < a_3 - 1$ and $b_{d_3} < b_{a_2}$. By Lemma~\ref{EPsi} we have $d_3 < a_2$.
By Lemma~\ref{FType3L1}, at most one of $d_1,d_2$ can be in $\Gamma_{[1,a_1]}^{[b_{a_2},b_{a_3}]}(T)$,
while by Lemma~\ref{EPsi}, any $d_i \notin \Gamma_{[1,a_1]}^{[b_{a_2},b_{a_3}]}(T)$ must satisfy
$b_{d_i} \notin [b_{a_2},b_{a_3}]$.  It follows that $(d_1,d_2,d_3) \in U(T)$, which contradicts the separability of $T$.
\end{casework}
Hence, we may assume that $d_3 = a_3 - 1$.  If $d_1 < a_1$, then it follows from Lemma~\ref{FType3L1}
that $c_{d_1} \notin (b_{a_1},b_{a_3})$.  Lemma~\ref{EPsi} yields that
$c_{d_1} \notin (b_{a_1},Y_{a_3})$.  Therefore, we have $c_{d_1} \le b_{a_1}$, which implies
that $c_{d_2} \in (b_{a_2},b_{a_1})$.  By Lemma~\ref{FType3L1}, we have $b_{d_2} \in (b_{a_2},b_{a_1})$,
and Lemma~\ref{EPsi} yields that $d_2 < a_1$.  Applying Lemma~\ref{FType3L1} again yields that
$c_{d_2} > c_{d_1}$, which contradicts the assumption
that $d \in U(\phi(T))$.  Hence, we may assume that $d_1 = a_1$, in which case Lemma~\ref{EPsi} implies that $d_2 \ge a_2$.
It follows that $h_J(\psi(T)) = (a_1,a_2,a_3-1)$, and therefore $\psi(T)$ is of $J$-type 3.
Because $c_{a_1} = b_{a_3+1}$ and $c_{a_3} = b_{a_2}$, we have
\[\phi(\psi(T)) = \omega_{[1,a_1] \cup \{a_3\}}^{[b_{a_2},b_{a_3}]}\left(\omega_{[a_2,a_3-1]}^{[b_{a_2},b_{a_3}]}\left(\theta_{[a_2,a_3-1]}^{[b_{a_2},b_{a_3}]}\left(\theta_{[1,a_1] \cup \{a_3\}}^{[b_{a_2},b_{a_3}]}(T)\right)\right)\right) = T,\]
as desired.

We prove that if $e = (e_1,e_2,e_3) \in V(\psi(T))$, then $S(e) \ge S(h_F(T))$ in the lexicographic
order.  Let $e \in V(\psi(T))$.  Suppose for sake
of deriving a contradiction that $S(e) < S(h_F(T))$ in the lexicographic order.  First, we prove that $e_3 \le a_3$.  Suppose for sake of deriving a contradiction
that $e_3 > a_3$.  Let $m = \min \Gamma_{[1,a_1]}^{[b_{a_2},b_{a_3}]}(T)$. By Lemma~\ref{FType3L2}, we have $c_{e_3} = b_{e_3} < b_m = c_{a_3+1}$.
If $e_1 > a_3$, then $e \in V(T)$, which contradicts the definition of $h_F$, and thus we may assume
that $e_1 \le a_3$. Lemmata~\ref{EPsi} and~\ref{FType3L1} imply
that $e_1 = a_3$ or $e_1 < a_2$, and we treat
the two cases separately.
\begin{casework}
\item $e_1 = a_3$.  Then, we have $(a_2,e_2,e_3) \in V(T)$, which contradicts the definition of $h_F$.
\item $e_1 < a_2$.  By Lemma~\ref{EPsi} and because $b_m < c_x$ for all $x \in \Gamma_{[1,a_1]}^{[b_{a_2},b_{a_1}]}$,
we have $b_{e_1} < b_{a_2}$ and hence $b_{e_i} = c_{e_i}$ for all $i$.  Thus, $(e_1,e_2,e_3) \in U(T)$,
which contradicts the definition of $h_F$.
\end{casework}
Hence, we may assume that $e_3 \le a_3$.  Because $e_3 \not= a_3-1$ and
the first component of $S(e)$ is at least $a_3-1$, either ($e$ is of $F$-type 2, $a_3 - 2 \in D$, $e_2 = a_3 - 3$ and $e_3 = a_3 - 2$)
or $e_3 = a_3$, and we treat the cases separately.
\begin{casework}
\item $e$ is of $F$-type 2. Because $b_{a_3-2} > b_{a_3-1}$,
Lemma~\ref{FType3L1} implies that $b_{a_3-2} > b_{a_3}$ and therefore $b_{a_3-2} = c_{a_3-2}$. By Lemma~\ref{EPsi}, we have $b_{a_3-3} \ge b_{a_1}$,
and it follows that $b_{a_3-3} \le \max\{b_{a_3},c_{a_3-3} < c_{a_3-2} = b_{a_3-2}$.  Lemma~\ref{EPsi}
implies that $b_{e_1} > b_{a_3}$ or $e_1 > d_2$.  In the latter case, the fact that $c_{e_1} > c_{e_2}$
implies that $b_{e_1} > b_{a_3}$ as well.  Thus, $b_{e_1} = c_{e_1}$ and $(e_1,e_2,e_3) \in V(T)$,
which contradicts the definition of $h_F$.
\item $e_3 = a_3$.  By Lemma~\ref{EPsi} and by the definition of $\psi$, there does not exist an index $i < a_3  - 1$ such that $c_{a_3-1} < c_i < c_{a_3}$.  Therefore, we have $e_2 \not= a_3 - 1$.  Because $a_3 - 1 \notin A$, it follows that $e$ is of $F$-type 3.  If $e_2 = a_3 - 1$,
then we have $b_m = c_{a_3} > c_{e_1} > c_{e_2} = b_{a_2}$, and by Lemma~\ref{EPsi} and the definition
of $\psi$, we have $e_1 < a_1$.  Thus, $e_1 \in \Gamma_{[1,a_1]}^{[b_{a_2},b_{a_3}]}$ with
$c_{e_1} < b_m < c_m$, which contradicts Lemma~\ref{FType3L1}.  Therefore, we may assume
that $e_2 < a_3 - 1$ and $e$ is of $F$-type 3.  The fact that $S(e) > S(h_F(T))$ in the lexicographic
order implies that $e_1 \ge a_1$, but $c_{a_1} > c_{a_3}$ and thus we may in fact assume that
$e_1 > a_1$.  By Lemma~\ref{EPsi} and the definition of $\psi$, we have $c_{e_1} < b_{a_2}$,
which implies that $b_{e_i} = c_{e_i}$ for $i \in [2]$.  Therefore,$(e_1,e_2,e_3) \in V(T)$, which contradicts the definition of $h_F$.
\end{casework}
The separability of $\psi(T)$ follows.

For all $i < m$, we have $b_i = c_i$.
If $m < a_1$, then let $m' = \min \Gamma_{(m,a_1]}^{[b_{a_3},b_{a_1}]}(T)$.  By Lemma~\ref{FType3L1},
we have $c_m = b_{m'} > b_m$.  If $m = a_1$, then we have $c_m = b_{a_3} > b_m$.  It follows
that $(b_1, b_2, \ldots, b_n) > (c_1,c_2,\ldots, c_n)$ in the lexicographic order, as desired.
\end{proof}

\subsection*{Acknowledgements}
The author would like to thank the
PRIMES program of the MIT Math Department, where this research was done
and Nihal Gowravaram of Acton-Boxborough Regional High School,
with whom much of this research was done.  In addition, the author would like to thank Dr. Joel Lewis of the University
of Minnesota for his incredibly helpful guidance and insight, and for introducing him to the topic of pattern-avoiding alternating permutations.  Lastly, the author would like to thank the anonymous referee for several helpful suggestions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain} 
% \bibliography{myBibFile} 
% If you use BibTeX to create a bibliography
% then copy and past the contents of your .bbl file into your .tex file

%\bibliography{finalpaper}
%\bibliographystyle{plain}

\begin{thebibliography}{10}
\bibitem{BW}
Eric Babson and Julian West.
\newblock The permutations $123p_4\ldots p_m$ and $321p_4\ldots p_m$ are
  {W}ilf-equivalent.
\newblock {\em Graphs and Combinatorics}, 16(4):373--380, 2000.

\bibitem{BWX}
J\"{o}rgen Backelin, Julian West, and Guoce Xin.
\newblock Wilf-equivalence for singleton classes.
\newblock {\em Advances in Applied Mathematics}, 38(2):133--148, 2007.

\bibitem{BonaBook}
Mikl\'{o}s B\'{o}na.
\newblock {\em Combinatorics of Permutations, Second Edition}.
\newblock Discrete Mathematics and its Applications. CRC Press, 2012.

\bibitem{Bona1221}
Mikl{\'o}s B{\'o}na.
\newblock On a family of conjectures of {J}oel {L}ewis on alternating
  permutations.
\newblock {\em Graphs and Combinatorics}, 30(3):521--526, 2014.

\bibitem{OldPaper}
Nihal Gowravaram and Ravi Jagadeesan.
\newblock Beyond alternating permutations: {P}attern avoidance in {Y}oung
  diagrams and tableaux.
\newblock {\arxiv{1301.6796v1}}.

\bibitem{PaperI}
Nihal Gowravaram and Ravi Jagadeesan.
\newblock Beyond alternating permutations: {P}attern avoidance in {Y}oung
  diagrams and tableaux.
\newblock {\em Electronic J. Combinatorics}, 20(4):\#P17, 2013.

\bibitem{Lewis2012}
Joel~Brewster Lewis.
\newblock Generating trees and pattern avoidance in alternating permutations.
\newblock {\em Electronic J. Combinatorics}, 19(1):\#P21, 2012.

\bibitem{Ouch}
Eric Ouchterlony.
\newblock Pattern avoiding doubly alternating permutations.
\newblock In {\em Proc. FPSAC}, 2006.
\newblock {\arxiv{0908.0255v1}}.

\bibitem{YanAD}
Sherry H.~F. Yan.
\newblock On {W}ilf equivalence for alternating permutations.
\newblock {\em Electronic J. Combinatorics}, 20(3):\#P58, 2013.
\end{thebibliography}

\end{document}
