On growth rates of closed permutation classes (Q1871365): Difference between revisions

This paper derives several quantitative estimates for closed permutation classes. ``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.'' (For example, the permutation \((3,5,4,2,1,7,8,6,9)\) contains \((2,1,3)\) but not \((3,1,2)\).) The well-known Stanley-Wilf conjecture can be reformulated as saying that any closed class of permutations different from the class of all permutations has at most exponential cardinality. The main result of this paper states roughly that the cardinality of any class of closed permutations is either bounded above polynomially or bounded below exponentially.