\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 Joshua N. Cooper}
%
%
\medskip
\noindent
%
%
{\bf A Permutation Regularity Lemma}
%
%
\vskip 5mm
\noindent
%
%
%
%
We introduce a permutation analogue of the celebrated Szemer\'{e}di
Regularity Lemma, and derive a number of consequences. This tool
allows us to provide a structural description of permutations which
avoid a specified pattern, a result that permutations which scatter
small intervals contain all possible patterns of a given size, a proof
that every permutation avoiding a specified pattern has a nearly
monotone linear-sized subset, and a ``thin deletion'' result. We also
show how one can count sub-patterns of a permutation with an integral,
and relate our results to permutation quasirandomness in a manner
analogous to the graph-theoretic setting.
\bye