Wilf collapse in permutation classes

MaRDI QIDQ6326201FDO

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

Publication date 29 September 2019

Mathematics Subject Classification ID

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

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.

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)