Michael Albert ; Vít Jelínek ; Michal Opler - Two examples of Wilf-collapse

dmtcs:5986 - Discrete Mathematics & Theoretical Computer Science, August 19, 2021, vol. 22 no. 2, Permutation Patterns 2019 - https://doi.org/10.46298/dmtcs.5986
Two examples of Wilf-collapse

Authors: Michael Albert ; Vít Jelínek ; Michal Opler

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.


Volume: vol. 22 no. 2, Permutation Patterns 2019
Section: Special issues
Published on: August 19, 2021
Accepted on: May 21, 2021
Submitted on: December 18, 2019
Keywords: Mathematics - Combinatorics,05A05, 05A15


Share

Consultation statistics

This page has been seen 30 times.
This article's PDF has been downloaded 7 times.