Bloom, Jonathan and Saracino, Dan - Pattern avoidance for set partitions à la Klazar

dmtcs:2023 - Discrete Mathematics & Theoretical Computer Science, September 7, 2016, Vol. 18 no. 2, Permutation Patterns 2015
Pattern avoidance for set partitions à la Klazar

Authors: Bloom, Jonathan and Saracino, Dan

In 2000 Klazar introduced a new notion of pattern avoidance in the context of set partitions of $[n]=\{1,\ldots, n\}$. The purpose of the present paper is to undertake a study of the concept of Wilf-equivalence based on Klazar's notion. We determine all Wilf-equivalences for partitions with exactly two blocks, one of which is a singleton block, and we conjecture that, for $n\geq 4$, these are all the Wilf-equivalences except for those arising from complementation. If $\tau$ is a partition of $[k]$ and $\Pi_n(\tau)$ denotes the set of all partitions of $[n]$ that avoid $\tau$, we establish inequalities between $|\Pi_n(\tau_1)|$ and $|\Pi_n(\tau_2)|$ for several choices of $\tau_1$ and $\tau_2$, and we prove that if $\tau_2$ is the partition of $[k]$ with only one block, then $|\Pi_n(\tau_1)| <|\Pi_n(\tau_2)|$ for all $n>k$ and all partitions $\tau_1$ of $[k]$ with exactly two blocks. We conjecture that this result holds for all partitions $\tau_1$ of $[k]$. Finally, we enumerate $\Pi_n(\tau)$ for all partitions $\tau$ of $[4]$.


Source : oai:arXiv.org:1511.00192
Volume: Vol. 18 no. 2, Permutation Patterns 2015
Section: Permutation Patterns
Published on: September 7, 2016
Submitted on: September 7, 2016
Keywords: Mathematics - Combinatorics,05A18


Share

Browsing statistics

This page has been seen 125 times.
This article's PDF has been downloaded 68 times.