10.46298/dmtcs.1327
https://dmtcs.episciences.org/1327
Bloom, Jonathan
Jonathan
Bloom
Saracino, Dan
Dan
Saracino
Pattern avoidance for set partitions \`a la Klazar
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]$.
Comment: 21 pages
episciences.org
Mathematics - Combinatorics
05A18
arXiv.org - Non-exclusive license to distribute
2016-09-07
2016-09-07
2016-09-07
eng
journal article
arXiv:1511.00192
10.48550/arXiv.1511.00192
1365-8050
10.48550/arxiv.1511.00192
https://dmtcs.episciences.org/1327/pdf
VoR
application/pdf
Discrete Mathematics & Theoretical Computer Science
Vol. 18 no. 2, Permutation Patterns 2015
Permutation Patterns
Researchers
Students