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

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

Authors: Jonathan Bloom ; Dan Saracino

    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]$.

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

    1 Document citing this article

    Consultation statistics

    This page has been seen 658 times.
    This article's PDF has been downloaded 370 times.