\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.15}{21(3)}{2014}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
%\bibliographystyle{plain} \bibliography{thebibliography}


\title{\bf The Weak Order on \\Pattern-Avoiding Permutations}

\author{Brian Drake\\
\small Department of Mathematics\\[-0.8ex]
\small Grand Valley State University\\[-0.8ex]
\small Allendale, MI, U.S.A.\\
\small \tt drakebr@gvsu.edu\\
}

\date{\dateline{Jan 1, 2014}{Jul 18, 2014}{Jul 25, 2014}\\
\small Mathematics Subject Classifications: 05A05; 06A12; 06B99}

%\email{drakebr@gvsu.edu}

\begin{document}
\maketitle

\begin{abstract}
The weak order on the symmetric group is a well-known partial order which is also a lattice.  We consider subposets of the weak order consisting of permutations avoiding a single pattern, characterizing the patterns for which the subposet is a lattice.  These patterns have only a single small ascent or descent.  We prove that all patterns for which the subposet is a sublattice have length at most three.
\end{abstract}

%We consider the partial order on permutations avoiding sets of
%patterns induced from the weak order of the symmetric group.
%Some sets of patterns are shown to give well-known
%posets, including $J(2 \times n)$, the integer interval lattice, and
%the lattice of shifted shapes.  In the case of a single pattern, we
%characterize those patterns which give a lattice.

%\bigskip
%\bigskip

%\noindent \textsc{R\'{e}sum\'{e}.} Nous consid\'{e}rons un ordre
%partiel sur des permutations \'{e}vitant un ensemble des motifs.
%L'ordre partiel est induit de l'ordre faible du groupe
%sym\'{e}trique. Quelques ensembles des motifs sont montres \`{a}
%donner les posets bien connus. Dans le cas d'un motif simple, nous
%caract\'{e}risons ces motifs qui donnent un trellis.

%, y compris le trellis de Tamari, le trellis de Boole, $J(2 \times
%n),$ et quelques autres trellis.

%\end{abstract}


\section{Introduction}
For any positive integer $n$, the weak order on the symmetric group $S_n$ is well known to be a lattice \cite{Guilbaud}, \cite{YO}.  There are also some interesting subposets of the weak order which are lattices, some of which can be described using pattern avoidance.  In particular, the Tamari lattice is isomorphic to the weak order on $312$ avoiding
permutations (\cite{BW}, $9.6.$ Theorem), \cite{Reading}.  Additionally, the Boolean
lattice is isomorphic to the weak order on $312$ and $231$ avoiding permutations (\cite{PB}, Lemme 4). Both the
Tamari lattice and Boolean lattice are actually sublattices of the
weak order.  The Bruhat order on pattern avoiding permutations has also been studied \cite{BBFP}.

\begin{figure} [ht]
\centering
\includegraphics[scale = .75] {weak_order_subs.eps}
\caption{The weak order on $S_3$, $S_3(312)$, and $S_3(\{312,231\})$.}\label{s3figure}
\end{figure}

In this article we consider the case of avoiding a single pattern. Our main result is the following.
\begin{theorem}\label{maintheorem}
$S_{n}(\tau)$ is a lattice for all $n$ if and only if
\smallskip
\begin{enumerate}
\item $\tau$ has exactly one descent, and its magnitude is at most
two, or
\item $\tau$ has exactly one ascent, and its magnitude is at most two.
\end{enumerate}
\end{theorem}
If we insist that the join and meet operations in our subposet agree
with those in $S_n$, then it turns out that both $(1)$ and $(2)$
must be satisfied. These conditions are sufficient, and the result
simplifies to the following.
\begin{theorem}\label{mainsubtheorem}
$S_{n}(\tau)$ is a sublattice of $S_n$ for all $n$ if and only if $\tau$ is one of
1, 12, 21, 213, 132, 231, or 312.
\end{theorem} The weak order on permutations avoiding any one of 213, 132, 231, or 312 is
isomorphic to the Tamari lattice.  The others are either empty or a single vertex.

In the course of proving these theorems, we find a somewhat
surprising result.
\begin{theorem}\label{testtheorem}
If $\tau$ is a pattern of length $k \geq 2$, the following are
equivalent:
\begin{enumerate}
\item  $S_n(\tau)$ is a lattice for all $n$.
\item  $S_{k+1}(\tau)$ is a lattice.
\end{enumerate}
\end{theorem}

%To address our second question, we find some new subposets of the
%weak order which are lattices: the lattice of shifted shapes, the
%integer interval lattice, $J(2 \times n)\cup$ \^{1}, and two unnamed
%lattices which may be of independent interest.  Of these examples,
%only the lattice of shifted shapes is a sublattice of the weak
%order.

This paper is organized as follows.  Section 2 contains some
preliminaries about pattern avoidance, lattices, and the weak order.
Section 3 contains the proofs of the main theorems. In Section 4, we give some
results about $S_n(T)$, where $T$ contains multiple
patterns.  

%-------------------------------------------------------------------


\section{Preliminaries}
\subsection{Permutations}
A \emph{permutation of n letters} is a bijection
$\pi\colon[n]\to[n]$, where $[n]$ denotes $\{1, 2, \ldots, n\}$. The
set of all permutations of $n$ letters is denoted $S_n$. We write
our permutations in one line notation as $\pi = \pi(1)\pi(2) \cdots
\pi(n)$.  Note that $\pi^{-1}(i)$ gives the position of the letter
$i$ in the word $\pi(1)\pi(2) \cdots \pi(n)$.

A \emph{descent} in a permutation $\pi$ occurs in position $i$ if
$\pi(i) > \pi(i+1)$.  The \emph{magnitude} of a descent in position
$i$ is $\pi(i) - \pi(i+1)$.  %An \emph{ascent} occurs in position $i$ if $\pi(i) < \pi(i+1)$.  The magnitude of an ascent in position $i$is $\pi(i+1) - \pi(i)$.
Ascents and their magnitudes are defined analogously.
An \emph{inversion} is a pair $(i, j)$ with
$i < j$ and $\pi^{-1}(i) > \pi^{-1}(j)$. That is, in the one line
notation for $\pi$, $i$ appears to the right of $j$. We define the
\emph{inversion set} $I(\pi)$ of $\pi$ to be the set of all
inversions in $\pi$. For example, $\pi = 24513$ has an ascent of
magnitude 1 in position 2, ascents of magnitude 2 in positions 1 and
4, and a descent of magnitude 4 in position 3. Its inversion set is
$I(24513) = \{(1,2), (1,4), (1,5), (3,4), (3,5)\}$.

If $\pi \in S_m$ and
$\sigma \in S_n$, then $\pi \oplus \sigma$ denotes the permutation
in $S_{m+n}$, where $\pi$ acts on $\{1,2,\ldots,m\}$, and
$\sigma$ acts on $\{m+1,m+2,\ldots,m+n\}$.  Similarly, $\pi \ominus
\sigma$ denotes the permutation in $S_{m+n}$, where $\pi$ acts on
$\{n+1,n+2,\ldots,n+m\}$, and $\sigma$ acts on $\{1,2,\ldots,n\}$.  For example, $132\oplus 21 = 13254$ and $132\ominus 21 = 35421$.

%In one line notation,
%\begin{align*}
%\pi \oplus \sigma &=
%\pi(1)\pi(2)\cdots\pi(m)(\sigma(1)+m)(\sigma(2)+m)\cdots(\sigma(n)+m)\\
%\pi \ominus \sigma &=
%(\pi(1)+n)(\pi(2)+n)\cdots(\pi(m)+n)\sigma(1)\sigma(2)\cdots\sigma(n).
%\end{align*}


\subsection{Pattern Avoidance}
Let $w$ be a word consisting of $k$ distinct integers.  The
\emph{standardization} of $w$, denoted $st(w)$, is obtained by
replacing the smallest entry of $w$ with a 1, the second smallest
with a 2, and so on.  A permutation $\pi \in S_{n}$ is said to
\emph{contain} a pattern $\tau \in S_{k}$ if there is a subsequence
$\pi^{\prime}$ of $\pi$ such that $st(\pi^{\prime}) = \tau$.
Otherwise, $\pi$ is said to \emph{avoid} $\tau$. For example, the
permutation $\pi =$ 1423 contains the pattern 132 twice, since
$st(142) = 132$ and $st(143)=132$. The permutation 2134 avoids 132.
For a set of patterns $T$, we will use $S_{n}(T)$ to denote the
permutations of length $n$ which avoid all of the patterns in $T$.
We will also use $S_n(T)$ to denote the set $S_n(T)$ together with
its order relation induced from the weak order.  For simplicity of
notation, we omit the set brackets for a single pattern. % There has been much recent interest in enumerative problems in patternavoidance \cite{KM, Wilf}.


\subsection{Lattices}
We assume that the reader is familiar with the definitions of
partially ordered sets (posets), covering relations, Hasse diagrams,
and dual posets (\cite{Stanley}, Chapter 3), or
\cite{Birkhoff}.

A \emph{lattice} $L$ is a poset with the following property.
For all $x, y \in L$, the set of upper bounds $\{z \in L\ |\ z \geq x, z \geq y\}$ has a unique minimal element, called the \emph{join}
of $x$ and $y$ and denoted $x \vee y$, and the set of lower bounds
$\{z \in L\ |\ z \leq x, z \leq y\}$ has a unique maximal element,
called the \emph{meet} of $x$ and $y$ and denoted $x \wedge y$.

One useful lemma which follows directly from the definition of a lattice is the following.
\begin{lemma}\label{middleset}
Let $L$ be a lattice, with $u, v, x, y, z \in L$.  Then
$u \vee v = z = x \wedge y$ if and only if  $\{t \in L\ |\ u\leq t, v\leq t, t\leq
x, t\leq y\} = \{z\}.$
\end{lemma}

A \emph{join semi-lattice} $L$ is a poset where every pair of
elements $x, y \in L$ has a join $x \vee y$.  A \emph{meet
semi-lattice} $L$ is a poset where every pair of elements $x, y \in
L$ has a meet $x \wedge y$.  $L$ is a lattice if and only if it is
both a join semi-lattice and a meet semi-lattice. We will make use
of the following lemma.
\begin{lemma}\label{Stanleylemma} {\rm (}\cite{Stanley}, Proposition 3.3.1.{\rm )}
Let $P$ be a finite meet semi-lattice with a unique maximal element.
Then $P$ is a lattice.
\end{lemma}

Given posets $Q$ and $P$, where the elements of $Q$ are a subset of
the elements of $P$, we say that $Q$ is an \emph{induced subposet}
of $P$ if $x \leq y$ in $Q$ if and only if $x \leq y$ in $P$.

In this paper we will be interested in showing that certain induced
subposets are lattices.  We are not assuming that the join and meet
operations are the same in the induced subposet as in the larger
lattice.  When these operations do coincide, we use a stronger term.
An induced subposet $P$ of a lattice $L$ is a \emph{join sublattice}
if $x, y \in P$ implies $x \wedge y \in P$, where $\wedge$ is taken
in $L$.  An induced subposet $P$ of a lattice $L$ is a \emph{meet
sublattice} if $x, y \in P$ implies $x \vee y \in P$.  $P$ is a
\emph{sublattice} of $L$ if $P$ is both a join sublattice and a meet
sublattice.

Our main tool for investigating induced subposets is the following
technical result.
\begin{lemma}\label{inducedplem}
Let $L$ be a join semi-lattice and $P$ an induced subposet. Suppose
that for all $v \in L$, the set $\{v^{\prime} \in P \ | \ v^{\prime}
\leq v \}$ has a unique maximal element or is the empty set.  Then
$P$ is a join sublattice of $L$.
\end{lemma}

\begin{proof}
Let $x, y \in P$, and suppose $z = x \vee y$ in $L$.  We want to
show that $z \in P$.  The set $\{ z^{\prime} \in P\ |\ z^{\prime}
\leq z\}$ is nonempty since it contains both $x$ and $y$, so by
assumption it has a unique maximal element $z^*$.  The element $z^*$ is in $\{ z^{\prime} \in P\ |\ z^{\prime}
\leq z\}$, so we have $z^* \leq z$.  By the maximality of $z^*$, we have $x \leq z^*$ and
$y \leq z^*$.  But since $z = x \vee y$, we also
have $z \leq z^*$ by the definition of join. Hence $z = z^*$ so $z \in P$.
\end{proof}

%\begin{proof} Let $\wedge_L$ denote the meet operation in $L$.  We
%want to find the meet operation $\wedge_P$ in $P$.  Suppose $x, y
%\in P$, $x \wedge_L y = v$ in $L$, and $v \in P$.  By definition, $z
%\leq x$ and $z \leq y$ implies $z \leq v$ for all $z \in L$.  In
%particular this holds for all $z \in P$, so we have $x \wedge_P y =
%v$.

%Now suppose $x, y \in P$, $x \wedge_L y = v$ in $L$, but $v \notin
%P$.  We cannot have $x = v$ or $y = v$, so $x$ and $y$ are
%incomparable.  Since $P$ has a unique minimal element, $x$ and $y$
%cannot be minimal elements, and there must be some $v' \in P$ less
%than both $x$ and $y$.  This $v'$ must be less than $v$ in $L$ by
%the definition of the meet operation.  Hence $\{v' \in P \ | \ v' <
%v \}$ is nonempty. By condition $(2)$, it has a unique maximal
%element $v_0$. If $z \in P$ satisfies $z \leq x$ and $z \leq y$,
%then $z \leq v$ in $L$, and by construction of $v_0$ we have $z \leq
%v_0$. Hence $x \wedge_P y = v_0$.
%\end{proof}

\subsection{Weak Order}
For permutations $\sigma, \pi \in S_n$, we define $\sigma \leq \pi$
if and only if $I(\sigma) \subseteq
I(\pi)$. It follows from the definition that $\pi$ covers $\sigma$ if
and only if $\pi$ is obtained from $\sigma$ by an
adjacent transposition which changes an ascent to a descent. 
Figure \ref{s3figure} includes the Hasse diagram of the weak order on $S_3$.
The weak order on $S_n$ is well known to be a lattice
\cite{Guilbaud}, \cite{YO}.  Throughout this paper, we will abuse notation and let $S_n$ denote
the set of permutations of length $n$ together with the order relation given by
the weak order.
%See (\cite{BB}, Theorem 3.2.1) for a
%proof that the weak order on an arbitrary Coxeter group $W$ is a
%meet semi-lattice.



%This definition is only one of many possibilities. More typically,
%one defines $\sigma \leq \pi$ if and only if $\pi = \sigma s_1s_2
%\cdots s_m$ for some adjacent transpositions $s_i$, such that
%$|I(\pi)| = |I(\sigma)| + m$. A proof of the equivalence of our
%definition in terms of inversions and the more typical definition is
%(\cite{BB}, Proposition 3.1.3).  %Since the adjacent transpositions
%are multiplied on the right, the weak order is sometimes called the
%right weak order.  %There is also a left weak order, although these
%are isomorphic via $\pi \mapsto \pi^{-1}$.  We will work exclusively
%with the right weak order in this paper, except for a short
%discussion in Section $\ref{leftsection}$.

 %Any order relation between permutations in this paper will refer to the weak order.

There are some standard bijections of the weak order which will be
useful. Let $w_0 \in S_n$ be the strictly decreasing permutation
$n(n-1)\cdots21$.
\begin{lemma}\label{basicsymmetrylemma} {\rm (}\cite{BB}, Proposition 3.1.5.{\rm )}
Let $\pi \in S_n$.
\begin{enumerate}
\item[$(i)$]$\pi \mapsto \pi w_0$ and $\pi \mapsto w_0 \pi$ are order reversing bijections of the weak
order on $S_n$.
\item[$(ii)$]$\pi \mapsto w_0\pi w_0$ is an order preserving
bijection of the weak order on $S_n$.
\end{enumerate}
\end{lemma}
The permutation $\pi w_0$ reverses the positions in the word $\pi$ and $w_0
\pi$ reverses the values of the entries, switching $i$ and
$(n+1-i)$, while $w_0 \pi w_0$ does both commuting operations.  For example, if $\pi=14235$, then $\pi w_0 = 53241$, $w_0\pi = 52431$, and $w_0\pi w_0 = 13425$. 

It follows immediately that $\pi$ avoids $\tau$ if and only if $\pi w_0$ avoids $\tau
w_0$. The same is true for the other two bijections. Combined with
Lemma \ref{basicsymmetrylemma}, we get the following.
\begin{lemma}\label{symmetrylemma}
Let $\pi \in S_n(T)$.
\begin{enumerate}
\item[$(i)$]$\pi \mapsto \pi w_0$ and $\pi \mapsto w_0 \pi$ are order reversing bijections of the weak
order on $S_n(T)$.
\item[$(ii)$]$\pi \mapsto w_0\pi w_0$ is an order preserving
bijection of the weak order on $S_n(T)$.
\end{enumerate}
\end{lemma}


%--------------------------------------------------------------------------



%Alternatively, we can derive Proposition \ref{shiftedsublattice}
%from Theorem ??, since $S_n(\{132, 312\})$ is the intersection of a
%meet sublattice [[which?]] and a join sublattice [[?]].

%\begin{prop} The lattice of shifted shapes with at most $n-1$
%columns is isomorphic to the weak order on $S_n(\{132, 312\})$.
%\end{prop}

%\begin{proof}
%We want to show that the permutations which avoid $132$ and $312$
%are exactly those whose inversion sets are shifted shapes, and that
%every shifted shape is the inversion set of a permutation.

%Suppose $\pi$ avoids $132$ and $312$.  To avoid an occurrence of
%$312$, if we have $(i, j) \in I(\pi)$, then for every $k < i$, $k$
%appears to the left of $j$ or to the right of $i$.  Since $\pi$ also
%avoids $132$, such a $k$ cannot appear to the left of $j$.  Hence
%$(k, j) \in I(\pi)$ for all $k < i$.  To avoid an occurrence of
%$312$, if $(i, j) \in I(\pi)$, then we must also have that every $l$
%with $i < l < j$ appears to the left of $i$.  That is, $(i, l) \in
%I(\pi)$ for all $i < l < j$.  Therefore the inversion set of a
%permutation in $S_n(\{132, 312\})$ is a shifted shape.

%We also have $|S_n(\{132, 312\})| = 2^{n-1}$ (\cite{SS}, Proposition
%10), the number of shifted shapes.  Since a permutation is uniquely
%recoverable from its inversion set, the map from permutations in
%$S_n(\{132, 312\})$ to their inversion sets gives a set bijection
%between $S_n(\{132, 312\})$ and shifted shapes with at most $n-1$
%columns. By definition the partial orders agree, so this is a poset
%isomorphism.
%\end{proof}

%\noindent {\bf Remark 3.1.} For any permutations $\pi, \sigma \in
%S_n$, we must have $I(\pi \wedge \sigma) \subseteq I(\pi) \cap
%I(\sigma)$ and $I(\pi \vee \sigma) \supseteq I(\pi) \cup I(\sigma)$
%by definition. In $S_n(\{132, 312\})$, we actually have $I(\pi
%\wedge \sigma) = I(\pi) \cap I(\sigma)$ and $I(\pi \vee \sigma) =
%I(\pi) \cup I(\sigma)$. Therefore the meet and join operations in
%$S_n(\{132, 312\})$ are the same as in $S_n$, so $S_n(\{132, 312\})$
%is actually a sublattice of $S_n$.

%-----------------------------------------------------------------------------


%-------------------------------------------------------------------------


\section{Proof of Theorems 1, 2 and 3}\label{proofsection}
\subsection{Terminology}
Let us introduce some terminology to be used in this section. Given
a poset $P$ and elements $\sigma, \sigma^{\prime}, \mu, \mu^{\prime}
\in P$ such that $\mu$ covers both $\sigma$ and $\sigma^{\prime}$
and $\mu^{\prime}$ covers both $\sigma$ and $\sigma^{\prime}$, we
say that $\sigma, \sigma^{\prime}, \mu$, and $\mu^{\prime}$
\emph{form a butterfly in the Hasse diagram of $P$}, and that
\emph{$P$ contains a butterfly in its Hasse diagram}. We call $\mu$
and $\mu^{\prime}$ the \emph{top} elements of the butterfly and
$\sigma$ and $\sigma^{\prime}$ the \emph{bottom} elements of the
butterfly. See Figure \ref{butterfly}.
\begin{figure} [ht]
\centering
\includegraphics[scale = .5] {butterfly.eps}
\caption{A butterfly in a Hasse diagram.} \label{butterfly}
\end{figure}

Note that any poset $P$ which contains a butterfly in its Hasse
diagram cannot be a lattice or semi-lattice, since the meet of the
top elements and the join of the bottom elements of the butterfly do
not exist.

\begin{lemma}\label{butterflylemma}
If the Hasse diagram of $S_n(\tau)$ contains a butterfly, then so
does the Hasse diagram of $S_m(\tau)$ for $m \geq n$.
\end{lemma}

\begin{proof}
Suppose $\sigma, \sigma^{\prime}, \mu$, and $\mu^{\prime}$ form a
butterfly in the Hasse diagram of $S_n(\tau)$.  Suppose also that
$\tau$ ends with a descent in position $k-1$. In this case, define
\begin{align*}
\sigma_m &= \sigma\oplus12\cdots(m-n)\\
\sigma^{\prime}_m &= \sigma^{\prime}\oplus12\cdots(m-n)\\
\mu_m &= \mu\oplus12\cdots(m-n)\\
\mu^{\prime}_m &= \mu^{\prime}\oplus12\cdots(m-n).
\end{align*}
Let us show that $\sigma_m, \sigma^{\prime}_m, \mu_m$, and
$\mu^{\prime}_m$ avoid $\tau$.  We know that $\tau$ ends with a
descent and $\sigma_m, \sigma^{\prime}_m, \mu_m$, and
$\mu^{\prime}_m$ each end with an increasing sequence of their
greatest $(m-n)$ letters.  So if any of these contains $\tau$, the
occurrence of $\tau$ would have to be in the first $n$ letters.  But
these letters are one of $\sigma, \sigma^{\prime}, \mu$, or $\mu^{\prime}$,
each of which avoids $\tau$.  Hence $\sigma_m, \sigma^{\prime}_m,
\mu_m, \mu^{\prime}_m \in S_m(\tau)$.

Notice that the inversion sets are unchanged: $I(\sigma_m) =
I(\sigma)$, $I(\sigma^{\prime}_m) = I(\sigma^{\prime})$, $I(\mu_m) =
I(\mu)$, and $I(\mu^{\prime}_m) = I(\mu^{\prime})$. Therefore we
have $\sigma_m \leq \mu_m, \sigma_m \leq \mu_m^{\prime},
\sigma_m^{\prime} \leq \mu_m, \sigma_m^{\prime} \leq
\mu_m^{\prime}$, and these relations are covering relations.
%We want
%to show that these are covering relations. If $\xi_m$ satisfies
%$\sigma_m \leq \xi_m, \sigma^{\prime}_m \leq \xi_m, \xi_m \leq
%\mu_m$, and $\xi_m \leq \mu^{\prime}_m$ in $S_m$, then we must have
%that $\xi_m = \xi\oplus12\cdots(m-n)$, where $\xi \in S_n$ and
%satisfies $\sigma \leq \xi, \sigma^{\prime} \leq \xi, \xi \leq \mu$,
%and $\xi \leq \mu^{\prime}$.  This follows by considering the
%inversion sets. Then since $\mu$ and $\mu^{\prime}$ cover $\sigma$
%and $\sigma^{\prime}$, $\xi$ must contain $\tau$ so that $\xi \notin
%S_n(\tau)$.  Therefore $\xi_m$ contains the same occurrence of
%$\tau$ and $\xi_m \notin S_m(\tau)$. We conclude that $\mu_m$ and
%$\mu^{\prime}_m$ cover $\sigma_m$ and $\sigma^{\prime}_m$.
That is, $\sigma_m, \sigma^{\prime}_m, \mu_m$, and $\mu^{\prime}_m$
form a butterfly in the Hasse diagram of $S_m(\tau)$.

%$$\mu_1^{(n)}\wedge\mu_2^{(n)}=\tau\oplus12\cdots(n-k)=\sigma_1^{(n)}\vee\sigma_2^{(n)}$$
%with the meet and join operations taken in $S_n$.  To complete the
%proof in this case, we need to show that $\mu_1^{(n)}, \mu_2^{(n)},
%\sigma_1^{(n)}, \sigma_2^{(n)} \in S_n(\tau)$ and
%$\tau\oplus12\cdots(n-k) \notin S_n(\tau)$.  Then $\mu_1^{(n)},
%\mu_2^{(n)}, \sigma_1^{(n)}$ and $\sigma_2^{(n)}$ form a butterfly
%in the Hasse diagram of $S_n(\tau)$.

%By assumption $\tau$ ends with a descent, and by construction
%$\mu_i^{(n)}$ and $\sigma_i^{(n)}$ each end with an increasing
%subsequence of their largest $(n-k)$ letters. Therefore if
%$\mu_i^{(n)}$ or $\sigma_i^{(n)}$ could contain an occurrence of
%$\tau$, then the occurrence must be in the first $k$ letters.  But
%this is $\mu_i^{(k)}$ or $\sigma_i^{(k)}$, which do not contain
%$\tau$. So we conclude that $\mu_1^{(n)}, \mu_2^{(n)},
%\sigma_1^{(n)}, \sigma_2^{(n)} \in S_n(\tau)$. Also,
%$\tau\oplus12\cdots(n-k)$ contains $\tau$ by definition, so
%$\tau\oplus12\cdots(n-k) \notin S_n(\tau)$.  This completes the
%first case.

For the remaining case, suppose that $\tau$ ends with an ascent.
Define
\begin{align*}
\sigma_m &= \sigma\ominus(m-n)\cdots 21\\
\sigma^{\prime}_m &= \sigma^{\prime}\ominus(m-n)\cdots 21\\
\mu_m &= \mu\ominus(m-n)\cdots 21\\
\mu^{\prime}_m &= \mu^{\prime}\ominus(m-n)\cdots 21.
\end{align*}
An analogous argument shows that $\mu_m, \mu_m^{\prime}, \sigma_m$
and $\sigma_m^{\prime}$ form a butterfly in the Hasse diagram of
$S_m(\tau)$.
\end{proof}

\subsection{Proofs}
For the rest of this section, let $\tau$ be a pattern of length $k$,
with $k \geq 2$.  We prove our main results using three intermediate propositions.

\begin{proposition}\label{claim1}
Suppose $\tau$ has at least two ascents and at least two descents.
Then $S_n(\tau)$ is not a meet semi-lattice or a join semi-lattice
for $n \geq k$.
\end{proposition}

\begin{proof}
Choose integers $a_1$, $a_2$, $d_1$, $d_2$ such that ascents of
$\tau$ occur in positions $a_1$ and $a_2$ and descents of $\tau$
occur in positions $d_1$ and $d_2$.  That is, we have
$\tau(a_1)<\tau(a_1+1), \tau(a_2)<\tau(a_2+1),
\tau(d_1)>\tau(d_1+1)$, and $\tau(d_2)>\tau(d_2+1)$.
%For example, if
%$\tau = 4265137$, we could choose $a_1 = 2, a_2 = 5, d_1 = 1, d_2 =
%4$ so that $\tau(d_2) = 5 > 1 = \tau(d_2+1)$, and so on.

%To prove the claim, we want to find $\mu_1^{(n)}, \mu_2^{(n)},
%\sigma_1^{(n)}, \sigma_2^{(n)} \in S_n(\tau)$ such that
%$\mu_1^{(n)}$ covers both $\sigma_1^{(n)}$ and $\sigma_2^{(n)}$ and
%$\mu_2^{(n)}$ covers both $\sigma_1^{(n)}$ and $\sigma_2^{(n)}$.  In
%this situation, these elements make the following figure in the
%Hasse diagram of $S_n(\tau)$.  [[Insert figure]].  When we have such
%covering relations among four elements in a poset $P$, we say that
%the four elements \emph{form a butterfly in the Hasse diagram of P}.
%If a poset $P$ has a butterfly in its Hasse diagram, then $P$ is not
%a meet semi-lattice since the meet of the top two elements of the
%butterfly does not exist.

By Lemma \ref{butterflylemma}, it suffices to find a butterfly in
the Hasse diagram of $S_k(\tau)$. Define permutations
\begin{align*}
\mu_1 &=
\tau(1)\tau(2)\cdots\tau(a_1-1)\tau(a_1+1)\tau(a_1)\tau(a_1+2)\cdots\tau(k)\\
\mu_2 &= \tau(1)\tau(2)\cdots\tau(a_2-1)\tau(a_2+1)\tau(a_2)\tau(a_2+2)\cdots\tau(k)\\
\sigma_1 &= \tau(1)\tau(2)\cdots\tau(d_1-1)\tau(d_1+1)\tau(d_1)\tau(d_1+2)\cdots\tau(k)\\
\sigma_2 &=
\tau(1)\tau(2)\cdots\tau(d_2-1)\tau(d_2+1)\tau(d_2)\tau(d_2+2)\cdots\tau(k).
\end{align*}
Notice that $\mu_i$ is obtained from $\tau$ by changing the ascent
in position $a_i$ to an descent, and that $\sigma_i$ is obtained
from $\tau$ by changing the descent in position $d_i$ to an ascent.
We have
\begin{align*}
I(\mu_1) &= I(\tau) \cup \{(\tau(a_1), \tau(a_1+1))\}\\
I(\mu_2) &= I(\tau) \cup \{(\tau(a_2), \tau(a_2+1))\}\\
I(\sigma_1) &= I(\tau) \setminus \{(\tau(d_1+1), \tau(d_1))\}\\
I(\sigma_2) &= I(\tau) \setminus \{(\tau(d_2+1), \tau(d_2))\}.
\end{align*}
By our definition of the weak order on $S_k$ in terms of inversion
sets, we have $\mu_1 \wedge \mu_2 = \tau = \sigma_1 \vee \sigma_2$,
where the meet and join are taken in $S_k$.  By Lemma
\ref{middleset}, $\tau$ is the only permutation in $S_k$ between
$\mu_1, \mu_2, \sigma_1$ and $\sigma_2$. Recall that $\tau$ has
length $k$.  A permutation $\pi$ of length $k$ contains a pattern
$\tau$ of length $k$ if and only if $\pi = \tau$, so $S_k(\tau) =
S_k \setminus \{\tau\}$ as sets.  Then by the definition of an
induced subposet, $\mu_1, \mu_2, \sigma_1$ and $\sigma_2$ form a
butterfly in the Hasse diagram of $S_k(\tau)$.
\end{proof}

\begin{proposition}\label{claim2}
Suppose $\tau$ has exactly one descent, and its magnitude is at
least 3.  Then $S_n(\tau)$ is not a meet semi-lattice or a join
semi-lattice for $n \geq k+1$.
\end{proposition}
\begin{proof}
Given such a pattern $\tau$, we have a set of letters $\{a, b, c,
d\}$ which appear in $\tau$, with $a < b < c < d$ in the usual
integer ordering, and $a$ appearing immediately to the right of $d$
in $\tau$.  That is, $\tau$ has a descent in position $\pi^{-1}(d)$
of magnitude $d-a \geq 3$.  Since $\tau$ has exactly one descent, it
can be decomposed into two increasing subwords of consecutive
letters. One is $\tau(1) < \tau(2) < \cdots d$ and the other is $a <
\cdots < \tau(k)$.  Therefore we can assume that $a, b, c$, and $d$
appear consecutively in $\tau$.  There are four possibilities for
$\tau$:
\begin{enumerate}
\item[$(i)$]  $\tau = \tau_{\rm init}\ bcda\ \tau_{\rm end}$
\item[$(ii)$] $\tau = \tau_{\rm init}\ bdac\ \tau_{\rm end}$
\item[$(iii)$] $\tau = \tau_{\rm init}\ cdab\ \tau_{\rm end}$
\item[$(iv)$] $\tau = \tau_{\rm init}\ dabc\ \tau_{\rm end}$
\end{enumerate}
where $\tau_{\rm init}$ and $\tau_{\rm end}$ are the appropriate
increasing subwords.  In each case we want to find a butterfly in
the Hasse diagram of $S_{k+1}(\tau)$, which completes the proof by
Lemma \ref{butterflylemma}.

\noindent \emph{Case $(i)$}. Choose $\tau^{\prime} \in S_{k+1}$ such
that
$$\tau^{\prime} = \tau_{\rm init}^{\prime} \ b(c+1)(d+1)sa\ \tau_{\rm end}^{\prime}$$
with $a < b < s < (c+1) < (d+1)$.  Define
%For example, if $\tau = 13472568$, we have $\tau_{\rm init} = 1,
%a=2, b=3, c=4, d=7, \tau_{\rm end} = 568$.  We can take
%$\tau^{\prime} = 135842679$, and we have $\tau_{\rm init}^{\prime} =
%1, a=2, b=3, s=4, (c+1)=5, (d+1)=7, \tau_{\rm end}^{\prime} = 679$.
%Notice that $st(13582679) = 13472568$.
\begin{align*}
\mu_1 &= \tau_{\rm init}^{\prime}(c+1)b(d+1)sa \tau_{\rm end}^{\prime}\\
\mu_2 &= \tau_{\rm init}^{\prime}b(d+1)(c+1)sa \tau_{\rm end}^{\prime}\\
\sigma_1 &= \tau_{\rm init}^{\prime}b(c+1)a(d+1)s \tau_{\rm end}^{\prime}\\
\sigma_2 &= \tau_{\rm init}^{\prime}b(c+1)sa(d+1) \tau_{\rm
end}^{\prime}.
\end{align*}
First, we want to show that $\mu_1, \mu_2, \sigma_1$, and $\sigma_2$
avoid $\tau$.  Since $\tau$ has length $k$, an occurrence of $\tau$
in one of these permutations would use all letters but one.  Such an
occurrence would start with an increasing sequence of $|\tau_{\rm
init}|+3$ letters, followed by a descent. This is impossible in
$\mu_1$, $\mu_2$ and $\sigma_2$. The letter after the descent in an
occurrence of $\tau$ must be smaller than the previous three. This
is impossible in $\sigma_1$.  Hence $\mu_1, \mu_2, \sigma_1,
\sigma_2 \in S_{k+1}(\tau)$.

Next we want to verify that $\sigma_1 \leq \mu_1$, $\sigma_1 \leq
\mu_2$, $\sigma_2 \leq \mu_1$, and $\sigma_2 \leq \mu_2$. This is
immediate from the inversion sets
\begin{align*}
I(\mu_1) &= I(\tau^{\prime}) \cup \{(b, (c+1))\}\\
I(\mu_2) &= I(\tau^{\prime}) \cup \{((c+1), (d+1))\}\\
I(\sigma_1) &= I(\tau^{\prime}) \setminus \{(a, s), (a, (d+1))\}\\
I(\sigma_2) &= I(\tau^{\prime}) \setminus \{(a, (d+1)), (s,
(d+1))\}.
\end{align*}

We want to show that all permutations in the set $\{ \xi \in
S_{k+1}\ |\ \xi \leq \mu_1, \xi \leq \mu_2, \sigma_1\leq \xi,
\sigma_2\leq \xi\}$ contain the pattern $\tau$.  Since $\mu_1$ and
$\mu_2$ cover $\tau^{\prime}$, any such permutation $\xi$ must
satisfy $\xi \leq \tau^{\prime}$.  The possible inversion sets are
$I(\tau^{\prime})$, $I(\tau^{\prime}) \setminus \{(a, s)\}$,
$I(\tau^{\prime}) \setminus \{(s, (d+1))\}$, and $I(\tau^{\prime})
\setminus \{(a, (d+1))\}$. The first is the inversion set for
$\tau^{\prime}$, which contains $\tau$.  The second is the inversion
set for $\xi_1 = \tau_{\rm init}^{\prime}\ b(c+1)(d+1)as\ \tau_{\rm
end}$, which contains $\tau$ by removing $s$.  The third is the
inversion set for $\xi_2 = \tau_{\rm init}^{\prime}\ b(c+1)s(d+1)a\
\tau_{\rm end}$, which contains $\tau$ by removing $s$.  The fourth
is not the inversion set of a permutation, since to move $a$ left of
$(d+1)$, either $a$ must move left of $s$ or $s$ must move left of
$(d+1)$, removing another inversion.  By the definition of an
induced subposet, we have shown that $\mu_1, \mu_2,$ $\sigma_1$, and
$\sigma_2$ form a butterfly in the Hasse diagram of $S_{k+1}(\tau)$.

\noindent \emph{Case $(ii)$}. In this case we have $\tau = \tau_{\rm
init}\ bdac\ \tau_{\rm end}$ with $a<b<c<d$.  Choose $\tau^{\prime}
\in S_{k+1}$ by
$$\tau = \tau_{\rm init}^{\prime}\ b(d+1)sa(c+1)\ \tau_{\rm end}^{\prime}$$
with $a < b < s < (c+1) < (d+1)$.  Define the following
permutations:
\begin{align*}
\mu_1 &= \tau_{\rm init}^{\prime}(d+1)bsa(c+1) \tau_{\rm end}^{\prime}\\
\mu_2 &= \tau_{\rm init}^{\prime} b(d+1)s(c+1)a \tau_{\rm end}^{\prime}\\
\sigma_1 &= \tau_{\rm init}^{\prime} ba(d+1)s(c+1) \tau_{\rm end}^{\prime}\\
\sigma_2 &= \tau_{\rm init}^{\prime} bsa(d+1)(c+1) \tau_{\rm
end}^{\prime}.
\end{align*}
We leave to the reader the argument that $\mu_1, \mu_2, \sigma_1$,
and $\sigma_2$ form a butterfly in the Hasse diagram of
$S_{k+1}(\tau)$.  It is entirely analogous to Case $(i)$.

\noindent \emph{Case $(iii)$}.  We have $\tau = \tau_{\rm init}\
cdab\ \tau_{\rm end}$ with $a<b<c<d$.  This is the same as in Case
$(ii)$, except $b$ and $c$ are switched.  In Case $(ii)$ we did not
need to use the relation $b < c$, so the same argument works in this
case.

\noindent \emph{Case $(iv)$}.  This case is equivalent to Case $(i)$
by using the symmetry operation $\pi \mapsto w_0\pi w_0$ described
in Lemma \ref{symmetrylemma}.
\end{proof}

%----------------------------------------------------------------------------------------
\begin{proposition}\label{claim3}
Suppose $\tau$ has exactly one descent, and its magnitude is at most
two. Then $S_n(\tau)$ is a join sublattice of $S_n$.
\end{proposition}
\begin{proof}
Let $\pi$ be a permutation which contains $\tau$.  Choose an
occurrence of $\tau$ in positions $i_1, i_2, \ldots, i_k$ with the
descent in position $i_h$, such that $i_{h+1}-i_h$ is minimal.

First, we want to show that $\pi(i_h+1), \pi(i_h+2), \ldots,
\pi(i_{h+1}-1)$ are each less than $\pi(i_{h+1})$ or greater than
$\pi(i_h)$.  Suppose there is such a $\pi(j)$ with $\pi(i_{h+1}) <
\pi(j) < \pi(i_h)$ and $i_h < j < i_{h+1}$.  Then either
\begin{align*}
st\left(\pi(i_1)\pi(i_2)\cdots \pi(i_{h-1})\pi(j)\pi(i_{h+1}) \cdots \pi(i_k)\right)&=\tau, {\rm or}\\
st\left(\pi(i_1)\pi(i_2)\cdots \pi(i_h)\pi(j)\pi(i_{h+2}) \cdots
\pi(i_k)\right)&=\tau
\end{align*}
depending on the relative sizes of $\pi(i_{h-1}), \pi(i_h), \pi(j),
\pi(i_{h+1})$, and $\pi(i_{h+2})$. Here we are using the fact that
$\tau$ has exactly one descent, which is of magnitude at most 2.  So
we have another occurrence of $\tau$ with the letters forming the
descent appearing closer together in $\pi$, contradicting the
minimality of $i_{h+1}-i_{h}$.  Hence $\pi(i_h+1), \pi(i_h+2),
\ldots, \pi(i_{h+1}-1)$ are each less than $\pi(i_{h+1})$ or greater
than $\pi(i_h)$.

In other words, $\{\pi(j)\ |\ i_h < j < i_{h+1} \} = X \cup Y$,
where
\begin{align*}
X &= \{\pi(j)\ |\ i_h<j<i_{h+1}, \pi(j) < \pi(i_{h+1}) \} \\
Y &= \{\pi(j)\ |\ i_h<j<i_{h+1}, \pi(i_h) < \pi(j) \}.
\end{align*}
Let $x_1, x_2, \ldots, x_r$ be the elements of $X$, ordered such that
if $p < q$, then $x_p$ appears to the left of $x_q$ in $\pi$. Let
$y_1, y_2, \ldots, y_t$ be the elements of $Y$ ordered in the same
fashion.

Now let $\pi^{\prime} \in S_{n}(\tau)$ with $\pi^{\prime} < \pi$. We
want to show that $\pi^{\prime} \leq \pi_0$, where
$$\pi_0 = \pi(1)\pi(2)\cdots\pi(i_h-1)x_1 x_2 \cdots
x_r\pi(i_{h+1})\pi(i_h) y_1 y_2 \cdots y_t \pi(i_{h+1}+1)\cdots
\pi(n).$$

Since $\pi(i_1), \pi(i_2), \ldots, \pi(i_h)$ form an increasing
subsequence in $\pi$, these letters must also appear in increasing
order from left to right in $\pi^{\prime}$, else $I(\pi^{\prime})
\not \subseteq I(\pi)$.  Similarly, $\pi(i_{h+1}), \pi(i_{h+2}),
\ldots, \pi(i_k)$ appear in increasing order from left to right in
$\pi^{\prime}$.  The subsequence $\pi(i_1), \pi(i_2), \ldots,
\pi(i_k)$ does not form an occurrence of $\tau$ in $\pi^{\prime}$,
so by the above $\pi(i_{h+1})$ appears to the left of $\pi(i_h)$ in
$\pi^{\prime}$.  But $\pi_0$ is maximal among permutations less than
$\pi$ with $\pi(i_{h+1})$ appearing to the left of $\pi(i_h)$.
Therefore $\pi^{\prime} \leq \pi_0$.

%First note that $I(\pi_0) = I(\pi) \setminus R$, where $R =  \{
%(\pi(i_h), \pi(i_{h+1}))\} \cup \{(x_j, \pi(i_h))\ |\ j \in [r] \}
%\cup \{(\pi(i_{h+1}, y_j)\ |\ j \in [t]\} \cup \{(x_j, y_l)\ |\
%\pi^{-1}(x_j) > \pi^{-1}(y_l), j \in [r], l \in [t]\}$.  That is,
%$\pi_0$ is obtained from $\pi$ by removing some inversions involving
%the letters making up the descent in this occurrence of $\tau$ and
%the letters between them.  So we have $\pi_0 < \pi$.

%Now let $\pi^{\prime}$ be an arbitrary permutation of $n$ which
%avoids $\tau$ and is less than $\pi$ in the weak order on $S_n$.
%Since $S_n$ is generated by adjacent transpositions, we can obtain
%$\pi^{\prime}$ by starting with $\pi$ and making a sequence of
%adjacent transpositions.  Since $\pi^{\prime} < \pi$, we can choose
%this sequence such that each transposition does not add any new
%inversions.

%We are assuming that $\pi^{\prime}$ avoids $\tau$, so we need to
%remove the occurrence of $\tau$ that we were considering above.
%There are five ways to do this, but only one does not add any new
%inversions.  First, we could change the order of $\pi(1), \pi(2),
%\ldots, \pi(i_h-1)$ so that $\tau(1), \tau(2), \ldots, \tau(h)$
%cannot be chosen.  But $\pi(i_1), \pi(i_2), \ldots, \pi(i_{h-1}$ was
%an increasing subsequence forming $\tau(1), \tau(2), \ldots,
%\tau(h)$.  Changing the order of this subsequence would create
%inversions.  Second, we could move enough of $\pi(1), \pi(2),
%\ldots, \pi(i_h-1)$ to the right of $\pi(i_h)$ so that $\tau(1),
%\tau(2), \ldots, \tau(h)$ cannot be chosen, but this also creates
%inversions since $\pi(i_j) < \pi(i_h)$ for $j < h$.  The third
%possibility, changing the order of $\pi(i_{h+1}+1), \ldots, \pi(n)$,
%or the fourth possibility, moving enough of $\pi(i_{h+1}+1), \ldots,
%\pi(n)$ to the left of $\pi(i_{h+1}+1)$ so that $\tau(h+2), \ldots,
%\tau(n)$ cannot be chosen, both create inversions.  The fifth
%possibility, the only one that could give a permutation less than
%$\pi$, is to move $\pi(i_{h+1})$ to the left of $\pi(i_h)$.  To do
%this without creating any inversions, all the $x_j$ must be kept to
%the left of $\pi(i_{h+1})$ and all the $y_j$ must be kept to the
%right of $\pi(i_h)$.  To keep as many inversions as possible, the
%$x_j$ and the $y_j$ must each stay in their original order.  But
%this is exactly the permutation $\pi_0$.  So we have shown that if
%$\pi^{\prime}$ avoids $\tau$ and is less than $\pi$, then it is also
%less than $\pi_0$.

It is possible that $\pi_0$ contains $\tau$, but $\pi_0$ does not
have an occurrence of $\tau$ with $\pi(i_{h+1})$ and $\pi(i_h)$
forming the descent. Since $\pi$ has only finitely many letters, we
can repeat this process and eventually end at a permutation $\pi^*$
such that $\pi^*$ avoids $\tau$, and every permutation
$\pi^{\prime}$ which avoids $\tau$ and satisfies $\pi^{\prime} <
\pi$ also satisfies $\pi^{\prime} \leq \pi^*$.

Now we can apply Lemma \ref{inducedplem} to complete the proof.
\end{proof}

%-----------------------------------------------------------------------

We are now in a position to prove our main results.  In fact, we
have results about semi-lattices as well.
\begin{theorem}\label{joinsublatticetheorem}
$S_{n}(\tau)$ is a join sublattice of $S_n$ for all $n$ if and only
if
\smallskip
\begin{enumerate}
\item $\tau$ has exactly one descent, and its magnitude is at most
two, or
\item $\tau$ has no descents.
\end{enumerate}
\end{theorem}
\begin{proof}
%\begin{proof}[Proof of Theorem \ref{maintheorem}]
Let $\tau$ be a pattern of length $k$.  Proposition \ref{claim3}
shows that if $\tau$ satisfies condition $(1)$, then $S_n(\tau)$ is
a join sublattice of $S_n$.  Suppose that $\tau$ satisfies condition
$(2)$, so that $\tau=12\cdots k$. In this case $\pi$ avoids $\tau$
if and only if $\pi$ does not contain an increasing subsequence of
$k$ letters.  If $\pi$ does not contain an increasing subsequence of
$k$ letters and $\pi^{\prime} \geq \pi$, then $\pi^{\prime}$ does
not contain an increasing subsequence of $k$ letters since $I(\pi)
\subseteq I(\pi^{\prime})$. Therefore $\pi, \sigma \in S_n(\tau)$
implies $\pi \vee \sigma \in S_n(\tau)$. That is, $S_n(\tau)$ is a
join sublattice.

Now we want to show conditions $(1)$ and $(2)$ are necessary for
$S_n(\tau)$ to be a join sublattice of $S_n$. Propositions
\ref{claim1} and \ref{claim2} rule out all cases, except when $\tau$
has exactly one ascent, that ascent has magnitude at most 2, and
$\tau$ has at least two descents.  Suppose $\tau$ is of this type.
Then $\tau$ is the join of two permutations, each obtained by
changing one of the descents to an ascent.  But these two
permutations are in $S_k(\tau)$, so it cannot be a join sublattice.
\end{proof}

\begin{theorem}\label{jointheorem}
$S_{n}(\tau)$ is a join semi-lattice for all $n$ if and only if
\smallskip
\begin{enumerate}
\item $\tau$ has exactly one descent, and its magnitude is at most
two, or
\item $\tau$ has exactly one ascent, and its magnitude is at most
two, or
\item $\tau$ has no descents.
\end{enumerate}
\end{theorem}

\begin{proof}
Propositions \ref{claim1} and \ref{claim2} show that conditions
$(1), (2)$, and $(3)$ are necessary. By Theorem
\ref{joinsublatticetheorem}, conditions $(1)$ and $(3)$ are
sufficient.  We want to show that condition $(2)$ is as well.

Suppose $\tau$ has exactly one ascent, which is of magnitude at most
two. Then by using $\pi \mapsto \pi w_0$ of Lemma
\ref{symmetrylemma} and Proposition \ref{claim3}, the dual poset to
$S_n(\tau)$ is a join semi-lattice. That is, $S_n(\tau)$ is a meet
semi-lattice. Since $n(n-1)\cdots 21$ avoids $\tau$, $S_n(\tau)$ has
a maximal element. By the dual to Lemma \ref{Stanleylemma},
$S_n(\tau)$ is a lattice, and hence a join semi-lattice.
\end{proof}

Using the map $\pi \mapsto \pi w_0$ of Lemma \ref{symmetrylemma}, we
have dual results.
\begin{theorem}\label{meetsublatticetheorem}
$S_{n}(\tau)$ is a meet sublattice of $S_n$ for all $n$ if and only
if
\smallskip
\begin{enumerate}
\item $\tau$ has exactly one ascent, and its magnitude is at most
two, or
\item $\tau$ has no ascents.
\end{enumerate}
\end{theorem}

\begin{theorem}\label{meettheorem}
$S_{n}(\tau)$ is a meet semi-lattice for all $n$ if and only if
\smallskip
\begin{enumerate}
\item $\tau$ has exactly one ascent, and its magnitude is at most
two, or
\item $\tau$ has exactly one descent, and its magnitude is at most
two, or
\item $\tau$ has no ascents.
\end{enumerate}
\end{theorem}

Since $S_n(\tau)$ is a lattice if and only if it is both a meet
semi-lattice and a join semi-lattice, we have proven Theorem
\ref{maintheorem}.  We have also shown that the only $\tau$ for which
$S_n(\tau)$ is a semi-lattice but not a lattice are the strictly
increasing and strictly decreasing patterns.

We can apply the same reasoning to sublattices, and get Theorem
\ref{mainsubtheorem}. Propositions \ref{claim1}, \ref{claim2}, and
\ref{claim3} also immediately imply Theorem \ref{testtheorem}.



%-----------------------------------------------------------------------------------

\section{Multiple patterns}
%\subsection{Multiple Pattern Restriction}
Theorem \ref{maintheorem} does not generalize immediately to larger sets
of patterns. In particular, even if both $S_n(\tau_1)$ and
$S_n(\tau_2)$ are lattices, $S_n(\{\tau_1, \tau_2\})$ is not
necessarily a lattice.

\begin{proposition}
$S_5({2431, 3124})$ is not a meet or join semi-lattice.
\end{proposition}

\begin{proof}
In $S_5$, define $\mu = 43215, \mu^{\prime} = 45231, \sigma =
23415$, and $\sigma^{\prime} = 21435$.  By considering the inversion
sets, we see that $\mu \wedge \mu^{\prime} = 42315$ and $\sigma \vee
\sigma^{\prime} = 24315$.  Since 42315 covers 24315, we have that
$\{ \xi \in S_5\ |\ \xi \leq \mu, \xi \leq \mu^{\prime}, \sigma \leq
\xi, \sigma^{\prime} \leq \xi\} = \{24315, 42315\}$.  Observe that
$\mu, \mu^{\prime}, \sigma$, and $\sigma^{\prime}$ all avoid 2431
and 3124, but 24315 contains 2431 and 42315 contains 3124.
Therefore, in the terminology of Section $\ref{proofsection}$, $\mu,
\mu^{\prime}, \sigma$, and $\sigma^{\prime}$ form a butterfly in the
Hasse diagram of $S_5({2431, 3124})$.
\end{proof}

Moreover, it is not necessary for both $S_n(\tau_1)$ and
$S_n(\tau_2)$ to be lattices in order for $S_n(\{\tau_1, \tau_2\})$
to be a lattice. For example, consider $S_n(\{2134, 2143\})$, which
is one case of the following result.

\begin{proposition}
Let $T = \{ 21 \oplus \tau \ |\  \tau \in S_{k-2} \}$. Then $S_n(T)$
is a lattice for all $n$.
\end{proposition}

\begin{proof} Observe that $S_n(T)$ is the set of permutations such that for
each descent $\pi(i) > \pi(i+1)$, we have $\vert \{ j \ | \ j > i,
\pi(j) > \pi(i)\} \vert < k-2$.  So if $\pi \in S_n \setminus
S_n(T)$, then there is a unique maximal element $\pi^{\prime} \in
S_n(T)$ less than $\pi$.  The element $\pi^{\prime}$ is obtained by changing all
descents which violate the condition above to ascents. Therefore
$S_n(T)$ is a join semi-lattice by Lemma \ref{inducedplem}. We also
have $12\cdots n \in S_n(T)$, so $S_n(T)$ is a lattice by the dual
statement of Lemma \ref{Stanleylemma}.
\end{proof}

%Characterizing all sets of patterns $T$ such that $S_n(T)$ is a
%lattice for all sufficiently large $n$ would be difficult, but it
%may be possible to generalize Theorem \ref{testtheorem}.

%\begin{conj}
%There exists an $M$ depending only on the length of the patterns
%$\tau_i$ such that the following are equivalent:
%\begin{enumerate}
%\item  $S_n(\tau_1, \tau_2, \ldots, \tau_r)$ is a lattice for all $n
%\geq M$.
%\item  $S_M(\tau_1, \tau_2, \ldots, \tau_r)$ is a lattice.
%\end{enumerate}
%\end{conj}

%\subsection{Left Weak Order}\label{leftsection}
%In this paper we have worked exclusively with the right weak order,
%although we can use the poset isomorphism $\pi \mapsto \pi^{-1}$
%between the right and left weak orders to obtain results for the
%left weak order.
%\begin{prop}
%Theorems 1--7 are true for the left weak order as well as for the
%right weak order.
%\end{prop}
%\begin{proof}
%A standard fact \cite{SS} used in pattern avoidance is that $\pi$
%avoids $\tau$ if and only if $\pi^{-1}$ avoids $\tau^{-1}$.
%Therefore $\pi \mapsto \pi^{-1}$ is a poset isomorphism of between
%the right and left weak orders on $S_n(T)$, not just $S_n$.  To see
%that the statements of the theorems are the same for the left weak
%order, we only need to check the image of some specific patterns.

%If $\tau = 12\cdots k$ is the strictly increasing pattern, then
%$\tau$ is the identity in $S_k$, so it is fixed by $\tau \mapsto
%\tau^{-1}$.  If $\tau$ has exactly one descent, which is of
%magnitude 1, then $\tau$ is one of the adjacent transpositions.
%Hence $\tau$ is an involution, and is also fixed by this map.

%Now suppose $\tau$ has exactly one descent, which is of magnitude 2.
%Then $\tau$ either of the form $12\cdots j \oplus 231 \oplus
%12\cdots(n-j-3)$ or of the form $12\cdots j \oplus 312 \oplus
%12\cdots(n-j-3)$ for some $0 \leq j \leq n-3$.  But $[12\cdots j
%\oplus 231 \oplus 12\cdots(n-j-3)]^{-1} = 12\cdots j \oplus 312
%\oplus 12\cdots(n-j-3)$, so $\tau^{-1}$ also has exactly one
%descent, which is of magnitude 2.
%\end{proof}

%\subsection{Bruhat Order}
%There is another partial order on permutations which is of
%fundamental importance, called the Bruhat order.  We will use
%$\leq_B$ to denote the Bruhat order on permutations.  We say that
%$\pi$ covers $\sigma$ in the \emph{Bruhat order} if and only if
%$\sigma$ can be obtained from $\pi$ by an arbitrary transposition,
%which increases the number of inversions.
%Then $\sigma \leq_B \pi$ if
%there is a sequence $\sigma = \sigma_0, \sigma_1, \sigma_2, \ldots,
%\sigma_s = \pi$ such $\sigma_i$ covers $\sigma_{i-1}$ for each
%$i=1,2,\ldots, s$.

%The Bruhat order is strictly stronger than the weak order.  That is,
%$\sigma \leq \pi$ implies $\sigma \leq_B \pi$, and there are more
%relations.  For example, $213 \leq_B 312$ and $132 \leq_B 231$,
%although these pairs are incomparable in the weak order. The Bruhat
%order on $S_n$ is not a lattice for $n \geq 3$, so one would not
%expect that the Bruhat order $S_n(T)$ is a lattice. However,
%Barcucci et al$.$ \cite{BBFP} showed that $S_n(\tau)$ is a lattice
%if $\tau$ is 213, 132, 231, or 312, each of which gives the same
%lattice.  Here we show that this lattice is the only example.

%\begin{prop}\label{Bruhatprop}
%Let $\tau$ be a pattern of length at least 3.  Then the Bruhat order
%on $S_n(\tau)$ is a lattice for all $n$ if and only if $\tau$ is
%213, 132, 231, or 312.
%\end{prop}

%\begin{proof}
%We will show that if $\tau$ is not 213, 132, 231, or 312, then the
%Bruhat order on $S_n(\tau)$ is not a lattice by finding a butterfly
%in its Hasse diagram for some $n$. The remainder of the claim is
%found in \cite{BBFP}.

%Clearly $S_n(k(k-1)\cdots 21)$ is not a lattice, since
%$213\oplus12\cdots(n-3), 132\oplus12\cdots(n-3),
%231\oplus12\cdots(n-3)$, and $312\oplus12\cdots(n-3)$ form a
%butterfly in its Hasse diagram.  Reversing the positions of the
%words gives a butterfly in the Hasse diagram of $S_n(12\cdots k)$.

%Suppose $\tau$ has length $k \geq 4$, and has both an ascent and a
%descent. Since the Bruhat order is stronger than the weak order,
%Propositions \ref{claim1} and \ref{claim2} apply.  In particular, if
%$\tau$ has at least two ascents and two descents, then for $n\geq k$
%there is a butterfly in the Hasse diagram of the weak order on
%$S_n(\tau)$, and hence in the Bruhat order on $S_n(\tau)$.
%Similarly, if $\tau$ has exactly one descent, and that descent has
%magnitude at least 3, or dually exactly one ascent, and that ascent
%has magnitude at least 3, then for $n \geq k+1$ there is a butterfly
%in the Hasse diagram of the Bruhat order on $S_n(\tau)$.

%Suppose $\tau$ has exactly one descent, and that descent has
%magnitude 2.  Since $\tau$ has length at least 4, $\tau$ has at
%least two ascents.  We can obtain permutations $\mu$ and
%$\mu^{\prime}$ which cover $\tau$ by changing one of the ascents to
%a descent with an adjacent transposition for each of $\mu$ and
%$\mu^{\prime}$.  Since the descent has magnitude 2, $|I(\tau)| = 2$.

%The inversions give two different transpositions that we can apply
%to get permutations $\sigma$ and $\sigma^{\prime}$ that $\tau$
%covers.  Therefore $\mu, \mu^{\prime}, \sigma$, and
%$\sigma^{\prime}$ form a butterfly in the Hasse diagram of the
%Bruhat order on $S_k(\tau)$.

%Suppose $\tau$ has exactly one descent, and that descent has
%magnitude 1.  Then $\tau = 12\cdots (s-1) (s+1) s (s+2) \cdots k$
%for some $1\leq s \leq k-1$.  Let $\tau^{\prime} = (n+1) 12\cdots
%(s-1) (s+1) s (s+2) \cdots k$.  Since $k \geq 4$, $\tau$ has at
%least two ascents.  Therefore we can obtain two permutations $\mu$
%and $\mu^{\prime}$ which cover $\tau^{\prime}$ in the Bruhat order
%by changing a corresponding ascent to a descent in $\tau^{\prime}$.
%$\tau^{\prime}$ also covers permutations $\sigma$ and
%$\sigma^{\prime}$ defined by $\sigma = (n+1)12\cdots n$ and
%$\sigma^{\prime} = s12\cdots (s-1)(s+1)(n+1)(s+2)\cdots n$.  These
%permutations $\mu, \mu^{\prime}, \sigma$, and $\sigma^{\prime}$
%avoid $\tau$, so they form a butterfly in the Hasse diagram of the
%Bruhat order on $S_{k+1}(\tau)$.
%\end{proof}

%Note the similarity of Proposition \ref{Bruhatprop} and Theorem
%\ref{mainsubtheorem}.  It would be interesting to know if there is a
%deeper connection between these concepts.

\subsection*{Acknowledgements}
I would like to thank Nathan Reading for a conversation that
inspired this project, and for comments on an earlier draft of this
paper.  I would also like to thank Ira Gessel for helpful conversations.  


%------------------------------------------------------------------------------
\begin{thebibliography}{99}

\bibitem{BBFP} E. Barcucci, A. Bernini, L. Ferrari, and M. Poneti,
\emph{A distributive lattice structure connecting Dyck paths, noncrossing partitions and 312-avoiding permutations}, Order {\bf 22} (2005), 311--328.

\bibitem{Birkhoff} G. Birkhoff, \emph{Lattice Theory}, American Mathematical
Society Colloquium Publications, vol. 25, 1948.

%\bibitem{Bjorner} A. Bj\"{o}rner, \emph{Orderings of Coxeter Groups}, in``Contemporary
%Mathematics'' {\bf 34} (1984), 175--195.

\bibitem{BB} A. Bj\"{o}rner and F. Brenti, \emph{Combinatorics of
Coxeter Groups}, Graduate Texts in Mathematics, vol. 231,
Springer-Verlag, New York, 2005.

\bibitem{BW} A. Bj\"{o}rner and M. Wachs, \emph{Shellable nonpure
complexes and posets. II}, Trans. Amer. Math. Soc. {\bf 349} (1997),
no. 10, 5247--5287.

\bibitem{Branden} P. Br\"{a}nd\'{e}n, \emph{q-Narayana numbers and the flag h-vector of
$J(2\times n)$}, Discrete Mathematics {\bf 281} (2004), 67--81.

%\bibitem{Erdos} P. Erd\H{o}s and G. Szekeres, \emph{A combinatorial
%theorem in geometry}, Compositio Math {\bf 2} (1935), 463--470.

%\bibitem{FZ} S. Fomin and A. Zelevinsky, \emph{Y-systems and Generalized
%Associahedra}, Annals of Mathematics {\bf 158} (2003), 977--1018.

%\bibitem{FS} S. Fomin and D. Stanton, \emph{Rim Hook Lattices},
%St. Petersburg Mathematical Journal {\bf 9} (1998), 1007--1016.

\bibitem{F} S. Fomin, \emph{Duality of graded graphs}, J. Alg.
Combinatorics {\bf 3} (1994), 357--404.

\bibitem{Guilbaud} G.Th. Guilbaud and P. Rosenstiehl, \emph{Analyse alg\'{e}brique
d'un scrutin} (French), in ``Ordres totaux finis'',
Gauthiers-villars et Mouton, Paris, 1971, 71--100.

%\bibitem{KM} S. Kitaev and T. Mansour, \emph{Survey on Certain
%Pattern Problems}, preprint, 2006.

\bibitem{PB} C. Le Conte de Poly-Barbut, \emph{Sur les Trellis de
Coxeter Finis} (French), Math. Inf. Sci. hum. {\bf 32}, no. 125
(1994), 41--57.

\bibitem{Reading} N. Reading, \emph{Cambrian Lattices}, Adv. Math.
{\bf 205} (2006), no. 2, 313--353.

\bibitem{SS} R. Simion and F. Schmidt, \emph{Restricted Permutations},
Europ. J. Combinatorics {\bf 6} (1985), 383--406.

\bibitem{Stanley} R. Stanley, \emph{Enumerative Combinatorics}, vol. 1.  Cambridge
University Press, Cambridge, 1999.

%\bibitem{Stanley2} R. Stanley, \emph{Enumerative Combinatorics}, vol. 2.  Cambridge
%University Press, Cambridge, 1999.

%\bibitem{Stembridge} J. Stembridge, \emph{A maple package for
%posets}, 2002.

%\bibitem{Tamari} D. Tamari, \emph{The algebra of bracketings and their enumeration},  Nieuw Arch. Wisk. {\bf 10} (1962), 131--146.

\bibitem{Vatter} V. Vatter, \emph{Finitely labeled generating trees and restricted
permutations} J. Symbolic Comput. {\bf 41} (2006), 559--572.

%\bibitem{Wilf} H. Wilf, \emph{The patterns of permutations}, Discrete
%Math {\bf 257} (2002) no. 2-3, 575--583.

\bibitem{YO} T. Yanagimoto and M. Okamoto, \emph{Partial orderings of
permutations and monotonicity of a rank correlation statistic}, Ann.
Inst. Statist. Math. {\bf 21} (1969), 489--506.

\end{thebibliography}

\end{document}
