Back to Search Start Over

Two examples of Wilf-collapse

Authors :
Albert, Michael
Jelínek, Vít
Opler, Michal
Source :
Discrete Mathematics & Theoretical Computer Science, vol. 22 no. 2, Permutation Patterns 2019, Special issues (August 19, 2021) dmtcs:5986
Publication Year :
2019

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.<br />Comment: Final version as accepted by DMTCS. Formatting changes only

Details

Database :
arXiv
Journal :
Discrete Mathematics & Theoretical Computer Science, vol. 22 no. 2, Permutation Patterns 2019, Special issues (August 19, 2021) dmtcs:5986
Publication Type :
Report
Accession number :
edsarx.1912.07713
Document Type :
Working Paper
Full Text :
https://doi.org/10.46298/dmtcs.5986