On growth rates of closed permutation classes (Q1871365): Difference between revisions
From MaRDI portal
Created a new Item |
Set profile property. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 06:01, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On growth rates of closed permutation classes |
scientific article |
Statements
On growth rates of closed permutation classes (English)
0 references
7 May 2003
0 references
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.
0 references
permutations
0 references
Stanley-Wilf conjecture
0 references
Fibonacci numbers
0 references