Cover
article
Butiran eJurnal
Wilf collapse in permutation classes
HARVEST (oa) oa826588
category EJURNAL event 2019-09-29 open_in_new Buka Pautan
Tarikh
2019-09-29
Pencipta
Albert, Michael
Subjek
Combinatorics; 05A05, 05A15, 05A16
Jenis
text
Pengenal (Identifier)
Sumber Harvest
ARXIV
Deskripsi
For a hereditary permutation class $\mathcal{C}$, we say that two permutations $π$ and $σ$ of $\mathcal{C}$ are Wilf-equivalent in $\mathcal{C}$, if $\mathcal{C}$ has the same number of permutations avoiding $π$ as those avoiding $σ$. We say that a permutation class $\mathcal{C}$ exhibits a Wilf collapse if the number of permutations of size $n$ in $\mathcal{C}$ 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 $\mathcal{C}$ as words, and analyzing the structure of a random permutation in $\mathcal{C}$ using this representation.