10.46298/dmtcs.5986
Albert, Michael
Michael
Albert
Jelínek, Vít
Vít
Jelínek
Opler, Michal
Michal
Opler
Two examples of Wilf-collapse
episciences.org
2021
Mathematics - Combinatorics
05A05, 05A15
contact@episciences.org
episciences.org
2019-12-18T23:16:10+01:00
2021-08-23T23:08:41+02:00
2021-08-19
eng
Journal article
https://dmtcs.episciences.org/5986
arXiv:1912.07713
1365-8050
PDF
1
Discrete Mathematics & Theoretical Computer Science ; vol. 22 no. 2, Permutation Patterns 2019 ; Special issues ; 1365-8050
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.
Comment: Final version as accepted by DMTCS. Formatting changes only