\magnification=1200
\hsize=4in
\overfullrule=0pt
\nopagenumbers
\noindent
%
%
{\bf Tom\' a\v s Kaiser and Martin Klazar}
%
%
\medskip
\noindent
%
%
{\bf On Growth Rates of Closed Permutation Classes}
%
%
\vskip 5mm
\noindent
%
%
%
%
A class of permutations $\Pi$ is called closed if
$\pi\subset\sigma\in\Pi$ implies $\pi\in\Pi$, where the relation
$\subset$ is the natural containment of permutations. Let $\Pi_n$ be
the set of all permutations of $1,2,\dots,n$ belonging to $\Pi$. We
investigate the counting functions $n\mapsto|\Pi_n|$ of closed
classes. Our main result says that if $|\Pi_n|<2^{n-1}$ for at least
one $n\ge 1$, then there is a unique $k\ge 1$ such that $F_{n,k}\le
|\Pi_n|\le F_{n,k}\cdot n^c$ holds for all $n\ge 1$ with a constant
$c>0$. Here $F_{n,k}$ are the generalized Fibonacci numbers which grow
like powers of the largest positive root of $x^k-x^{k-1}-\cdots-1$. We
characterize also the constant and the polynomial growth of closed
permutation classes and give two more results on these.
\bye