Grid classes and the Fibonacci dichotomy for restricted permutations

MaRDI QIDQ2500973zbMATH OpenFDO

Authors Sophie Huczynska, Vincent Vatter

Publication date 30 August 2006

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

Full work available at URL https://arxiv.org/abs/math/0602143, https://eudml.org/doc/126506, http://www.emis.de/journals/EJC/Volume_13/Abstracts/v13i1r54.html

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

zbMATH Keywords

Fibonacci numberpermutation classes

Mathematics Subject Classification ID

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

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.

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

Cited in

(28)

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

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)