Skip to main content

Research Repository

Advanced Search

Algorithmic coincidence classification of mesh patterns

Bean, Christian; Gudmundsson, Bjarki; Magnusson, Tomas Ken; Ulfarsson, Henning

Algorithmic coincidence classification of mesh patterns Thumbnail


Bjarki Gudmundsson

Tomas Ken Magnusson

Henning Ulfarsson


Permutations have connections to other mathematical objects such as Schubert varieties, sorting networks, and genome rearrangements. Often the connection is described in terms of patterns that are absent from the permutations. There can be ambiguity in this description, in the sense that the same subset of permutations can be defined with two different patterns. This is called coincidence and we focus on the coincidence of mesh patterns, one of the most descriptive version of patterns in permutations. We review and extend previous results on coincidence of mesh patterns. We introduce the notion of a force on a permutation pattern and apply it to the coincidence classification of mesh patterns, completing the classification up to size three. We also show that this concept can be used to enumerate classical permutation classes.

Acceptance Date Feb 16, 2023
Online Publication Date Feb 24, 2023
Publication Date Jun 1, 2023
Publicly Available Date Feb 25, 2024
Journal Information and Computation
Print ISSN 0890-5401
Publisher Elsevier
Publisher URL


You might also like

Downloadable Citations