On growth rates of closed permutation classes
type: Item
instance of: scholarly article
title: On growth rates of closed permutation classes
zbMATH Open document ID: 1015.05002
author: Tomáš Kaiser
author: Martin Klazar
published in: The Electronic Journal of Combinatorics
publication date: 2003-05-07T00:00:00Z
full work available at URL: https://eudml.org/doc/122726
full work available at URL: v9i2r10.html
review text: 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.
reviewed by: Hsien-Kuei Hwang
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A16
zbMATH DE Number: 1907088
zbMATH Keywords: permutations
zbMATH Keywords: Stanley-Wilf conjecture
zbMATH Keywords: Fibonacci numbers
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1907088