Grid classes and the Fibonacci dichotomy for restricted permutations

zbMATH Open1098.05003arXivmath/0602143MaRDI QIDQ2500973FDOQ2500973

Authors: Sophie Huczynska, Vincent Vatter 

Publication date: 30 August 2006

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 nth Fibonacci number or is eventually polynomial.

Full work available at URL: https://arxiv.org/abs/math/0602143

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Geometric grid classes of permutations
• Small permutation classes
• Growth rates of geometric grid classes of permutations
• Permutation classes of polynomial growth
• Growth rates of permutation classes: from countable to uncountable

zbMATH Keywords

Fibonacci numberpermutation classes

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16)

Cited In (28)

• \(2\times 2\) monotone grid classes are finitely based
• Geometric grid classes of permutations
• On the effective and automatic enumeration of polynomial permutation classes
• Letter graphs and geometric grid classes of permutations: characterization and recognition
• Classes of graphs without star forests and related graphs
• Fibonacci numbers, consecutive patterns, and inverse peaks
• Prolific permutations
• Inflations of geometric grid classes of permutations
• Generating permutations with restricted containers
• Automatic discovery of structural rules of permutation classes
• Forbidden substructures and combinatorial dichotomies: WQO and universality
• Intervals of permutation class growth rates
• Combinatorial generation via permutation languages. I: Fundamentals
• Well-quasi-order for permutation graphs omitting a path and a clique
• Labelled well-quasi-order for permutation classes
• An Algorithm to Enumerate Grid Signed Permutation Classes
• Square permutations are typically rectangular
• The enumeration of three pattern classes using monotone grid classes
• Letter graphs and geometric grid classes of permutations
• Enumeration of cyclic permutations in vector grid classes
• Finding regular insertion encodings for permutation classes
• Growth rates of permutation grid classes, tours on graphs, and the spectral radius
• Characterising inflations of monotone grid classes of permutations
• An antichain of monomial ideals in a twisted commutative algebra
• Title not available (Why is that?)
• Generalizations of Khovanskiĭ's theorems on the growth of sumsets in abelian semigroups
• Grid classes and partial well order
• Wilf-collapse in permutation classes having two basis elements of size three

This page was built for publication: Grid classes and the Fibonacci dichotomy for restricted permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2500973)