Grid classes and the Fibonacci dichotomy for restricted permutations

S Huczynska, V Vatter

Research output: Contribution to journalArticlepeer-review

31 Citations (Scopus)

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 languageEnglish
Pages (from-to)R54
Number of pages14
JournalElectronic Journal of Combinatorics
Volume13
Issue number1
Publication statusPublished - 23 Jun 2006

Keywords

  • CLOSED-SETS
  • SUBSEQUENCES
  • GRAPHS

Fingerprint

Dive into the research topics of 'Grid classes and the Fibonacci dichotomy for restricted permutations'. Together they form a unique fingerprint.

Cite this