Back to Search
Start Over
Two examples of Wilf-collapse
- 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
- Subjects :
- Mathematics - Combinatorics
05A05, 05A15
Subjects
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