Recognition of Ordered Patterns

The relation of pattern containment or involvement in permutations has
become an active area of research in computer science and combinatorics. In
CS pattern containment restrictions have been used to describe permutations
sortable in various restricted settings. In combinatorics the focus has
been on enumerating such classes of permutations, and on describing or
explaining the relationships between them.

Experimental research in both areas has been difficult owing to the lack of
good algorithms for recognising ordered patterns within a permutation. We
will describe recent results that improve the running time of these
algorithms, sometimes in a spectacular fashion. The lecture will be both
introductory, and self-contained.