Two examples of Wilf-collapse

MaRDI QIDQ5074774zbMATH OpenFDO

Authors Vít Jelínek, Michal Opler, Michael Albert

Publication date 10 May 2022

Full work available at URL https://arxiv.org/abs/1912.07713, https://dmtcs.episciences.org/8373

zbMATH Keywords

generating functionsgrowth ratespermutationsWilf-equivalence

Mathematics Subject Classification ID

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

Abstract: Two permutation classes, the X-class and subpermutations of the increasing oscillation are shown to exhibit an exponential Wilf-collapse. This means that the number of distinct enumerations of principal subclasses of each of these classes grows much more slowly than the class itself whereas a priori, based only on symmetries of the class, there is no reason to expect this. The underlying cause of the collapse in both cases is the ability to apply some form of local symmetry which, combined with a greedy algorithm for detecting patterns in these classes, yields a Wilf-collapse.

Recommendations

• Wilf-collapse in permutation classes having two basis elements of size three
• Uniquely-Wilf classes
• Wilf-classification of mesh patterns of short length
• On growth rates of closed permutation classes
• Wilf classification of subsets of four letter patterns

Cites work

• A general theory of Wilf-equivalence for Catalan structures
• Genome Rearrangements and Sorting by Reversals
• Growth rates of permutation classes: categorization up to the uncountability threshold
• Intervals of permutation class growth rates
• Juggling Drops and Descents
• Permutation classes
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• Rationality for subclasses of 321-avoiding permutations
• The complexity of pattern matching for 321-avoiding and skew-merged permutations
• Wilf-collapse in permutation classes having two basis elements of size three

Cited in

(3)

• Deflatability of permutation classes
• scientific article; zbMATH DE number 2202762 (Why is no real title available?)
• Wilf-collapse in permutation classes having two basis elements of size three

This page was built for publication: Two examples of Wilf-collapse

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