Two examples of Wilf-collapse
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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2021-08-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/5986/pdf |
| _version_ | 1797270043445166080 |
|---|---|
| author | Michael Albert Vít Jelínek Michal Opler |
| author_facet | Michael Albert Vít Jelínek Michal Opler |
| author_sort | Michael Albert |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-11T21:32:16Z |
| format | Article |
| id | doaj.art-e7c63001283d4036b1edbaade457a20c |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:00Z |
| publishDate | 2021-08-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-e7c63001283d4036b1edbaade457a20c2024-03-07T15:41:55ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502021-08-01vol. 22 no. 2, Permutation...Special issues10.46298/dmtcs.59865986Two examples of Wilf-collapseMichael AlbertVít Jelínekhttps://orcid.org/0000-0003-4831-4079Michal Oplerhttps://orcid.org/0000-0002-4389-5807Two 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.https://dmtcs.episciences.org/5986/pdfmathematics - combinatorics05a05, 05a15 |
| spellingShingle | Michael Albert Vít Jelínek Michal Opler Two examples of Wilf-collapse Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05a05, 05a15 |
| title | Two examples of Wilf-collapse |
| title_full | Two examples of Wilf-collapse |
| title_fullStr | Two examples of Wilf-collapse |
| title_full_unstemmed | Two examples of Wilf-collapse |
| title_short | Two examples of Wilf-collapse |
| title_sort | two examples of wilf collapse |
| topic | mathematics - combinatorics 05a05, 05a15 |
| url | https://dmtcs.episciences.org/5986/pdf |
| work_keys_str_mv | AT michaelalbert twoexamplesofwilfcollapse AT vitjelinek twoexamplesofwilfcollapse AT michalopler twoexamplesofwilfcollapse |