Abstract
We introduce and characterise grid classes, which are natural generalisations of other well-studied permutation classes. This characterisation allows us to give a new, short proof of the Fibonacci dichotomy: the number of permutations of length n in a permutation class is either at least as large as the n th Fibonacci number or is eventually polynomial.
Original language | English |
---|---|
Pages (from-to) | R54 |
Number of pages | 14 |
Journal | Electronic Journal of Combinatorics |
Volume | 13 |
Issue number | 1 |
Publication status | Published - 23 Jun 2006 |
Keywords
- CLOSED-SETS
- SUBSEQUENCES
- GRAPHS