Journal of Combinatorics

Volume 6 (2015)

Number 1–2

Isomorphisms between pattern classes

Pages: 3 – 17

DOI: http://dx.doi.org/10.4310/JOC.2015.v6.n1.a1

Authors

M. H. Albert (Department of Computer Science, University of Otago, Dunedin, New Zealand)

M. D. Atkinson (Department of Computer Science, University of Otago, Dunedin, New Zealand)

Anders Claesson (Department of Computer Science, University of Strathclyde, Glasgow, Scotland, United Kingdom)

Abstract

Isomorphisms $\phi : \mathcal{A} \longrightarrow \mathcal{B}$ between pattern classes are considered. It is shown that, if $\phi$ is not itself a symmetry of the entire set of permutations, then, to within symmetry, $\mathcal{A}$ is a subset of one of a small set of pattern classes whose structure, including their enumeration, is determined.

Keywords

pattern class, permutation, isomorphism

2010 Mathematics Subject Classification

05A05

Full Text (PDF format)