Permuting machines and permutation patterns

Summary

Abstract

Permuting machines were the early inspiration of the theory of permutation pattern classes. Some examples are given which lead up to distilling the key properties that link them to pattern classes. It is shown how relatively simple ways of combining permuting machines can lead to quite complex behaviour and that the notion of regularity can sometimes be used to contain this complexity. Machines which are sensitive to their input data values are shown to be connected to a more general notion than pattern classes. Finally some open problems are presented.

Introduction

Although permutation patterns have only recently been studied in a systematic manner their history can be traced back many decades. It could be argued that the well-known lemma of Erdős and Szekeres is really a result about pattern classes (a pattern class whose basis contains both an increasing and a decreasing permutation is necessarily finite). However it is perhaps more convincing to attribute the birth of the subject to the ground-breaking first volume of Donald Knuth's Art of Computer Programming series. In the main body of his text, and in some fascinating follow-up exercises, Knuth enumerated some pattern classes, and found some bases, while at the same time introducing some techniques on generating functions that, in due time, were codified as “the kernel method”.