Matchings and partial patterns

Vít Jelínek ; Toufik Mansour

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

A matching of size $2n$ is a partition of the set $[2n]=\{1,2,\dotsc,2n\}$ into $n$ disjoint pairs. A matching may be identified with a canonical sequence, which is a sequence of integers in which each integer $i\in[n]$ occurs exactly twice, and the first occurrence of $i$ precedes the first occurrence of $i+1$. A partial pattern with $k$ symbols is a sequence of integers from the set $[k]$, in which each $i\in[k]$ appears at least once and at most twice, and the first occurrence of $i$ always precedes the first occurrence of $i+1$. Given a partial pattern $\sigma$ and a matching $\mu$, we say that $\mu$ avoids $\sigma$ if the canonical sequence of $\mu$ has no subsequence order-isomorphic to $\sigma$. Two partial patterns $\tau$ and $\sigma$ are equivalent if there is a size-preserving bijection between $\tau$-avoiding and $\sigma$-avoiding matchings. In this paper, we describe several families of equivalent pairs of patterns, most of them involving infinitely many equivalent pairs. We verify by computer enumeration that these families contain all the equivalences among patterns of length at most six. Many of our arguments exploit a close connection between partial patterns and fillings of diagrams.

Détail

DOI : 10.37236/430

Classification : 05A18, 05A05, 05A15
Mots-clés : matching, canonical sequence, partial pattern, avoiding