Grid classes and the Fibonacci dichotomy for restricted permutations
With Sophie Huczynska.
Electronic Journal of Combinatorics 13 (2006), #R54, 14 pp.
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 nth Fibonacci number or is eventually polynomial.
Download the paper:
- download from the journal website
- ps
- source: tex and bbl
Links and open questions:
- The approach we used to prove the Fibonacci dichotomy has been significantly extended in my paper "Small permutation classes."
- Conjecture 2.3, which states that all monotone grid classes are finitely based, is still open.
- Conjecture 2.8, which states that monotone grid classes of forests have rational generating functions, is still open.
- While we know which permutation classes have polynomial enumeration, it is not yet known which polynomials can arise.
- While we know how to decide if a permutation class is monotone griddable, we do not know how to decide if it lies in the monotone grid class of a forest.