\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf V\'\i t Jel\'\i nek and Toufik Mansour}
%
%
\medskip
\noindent
%
%
{\bf On Pattern-Avoiding Partitions}
%
%
\vskip 5mm
\noindent
%
%
%
%
A {\it set partition of size $n$} is a collection of disjoint blocks
$B_1,B_2,\ldots$, $B_d$ whose union is the set $[n]=\{1,2,\ldots,n\}$. We
choose the ordering of the blocks so that they satisfy $\min B_1<\min
B_2<\cdots<\min B_d$. We represent such a set partition by a {\it canonical
sequence} $\pi_1,\pi_2,\ldots,\pi_n$, with $\pi_i=j$ if $i\in B_j$.  We say
that a partition $\pi$ {\it contains} a partition $\sigma$ if the canonical
sequence of $\pi$ contains a subsequence that is order-isomorphic to the
canonical sequence of $\sigma$. Two partitions $\sigma$ and $\sigma'$ are
{\it equivalent}, if there is a size-preserving bijection between
$\sigma$-avoiding and $\sigma'$-avoiding partitions.

We determine all the equivalence classes of partitions of size at most $7$.
This extends previous work of Sagan, who described the equivalence classes
of partitions of size at most $3$.

Our classification is largely based on several new infinite families of pairs
of equivalent patterns. For instance, we prove that there is a bijection
between $k$-noncrossing and $k$-nonnesting partitions, with a notion of
crossing and nesting based on the canonical sequence. Our results also yield
new combinatorial interpretations of the Catalan numbers and the Stirling
numbers.

\bye

.