On growth rates of closed sets of permutations, set partitions, ordered graphs and other objects

Martin Klazar

Charles University, Prague

If $X$ is a closed set of finite permutations (i.e., a lower ideal in $({\cal S},\preceq)$ where ${\cal S}$ is the set of all finite permutations and $\preceq$ is the standard containment ordering) and $X_n\subset X$ denotes the set of all $n$-permutations in $X$, then the counting function $n\mapsto \vert X_n\vert$ is subject to various dichotomies and restrictions forbidding many functions to have this form; this was shown (Electronic J. of Combinatorics, 2003) by T. Kaiser and M. Klazar. For example, either $\vert X_n\vert\ge n$ for all $n\ge 1$ or $\vert X_n\vert$ is eventually constant, or--another dichotomy--either $\vert X_n\vert\le n^c$ for all $n\ge 1$ with a constant $c>0$ or $\vert X_n\vert\ge F_n$ for all $n\ge 1$, where $F_n=1,2,3,5,8,13,\dots$ are the Fibonacci numbers.

In my talk I will present generalizations and extensions of these results to other classes of objects (like those mentioned in the title) and other containments, and I will discuss a general approach to obtain them uniformly as instances of a general metaresult.