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-collapseArticle

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

    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

    Consultation statistics

    This page has been seen 491 times.
    This article's PDF has been downloaded 198 times.