Wilf collapse in permutation classes

arXiv1909.13348MaRDI QIDQ6326201FDOQ6326201

Authors: Michael Albert, Vít Jelínek, Michal Opler 

Publication date: 29 September 2019

Abstract: For a hereditary permutation class $mathcalC$, we say that two permutations $pi$ and $sigma$ of $mathcalC$ are Wilf-equivalent in $mathcalC$, if $mathcalC$ has the same number of permutations avoiding $pi$ as those avoiding $sigma$. We say that a permutation class $mathcalC$ exhibits a Wilf collapse if the number of permutations of size $n$ in $mathcalC$ is asymptotically larger than the number of Wilf-equivalence classes formed by these permutations. In this paper, we show that Wilf collapse is a surprisingly common phenomenon. Among other results, we show that Wilf collapse occurs in any permutation class with unbounded growth and finitely many sum-indecomposable permutations. Our proofs are based on encoding the elements of a permutation class $mathcalC$ as words, and analyzing the structure of a random permutation in $mathcalC$ using this representation.

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16)

This page was built for publication: Wilf collapse in permutation classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326201)