The Structure of Permutation Classes

Permutations are among most fundamental and ubiquitous abstract mathematical concepts, and are indispensable in modeling a vast array of higher level phenomena in other sciences: from the study of symmetries of the material world in Physics, via genome rearrangements and evolution in Biology to the study of data processing in Computer Science. In many of these, the order-theoretic properties of permutations are of chief importance, and the abstract theory underlying this facet is known as the theory of permutation patterns. From its beginnings as a small topic in Knuth's Art of Computer Programming to do with stack sorting, the theory has undergone a period of rapid expansion and development over the past two decades. The PI and his two proposed collaborators Albert and Vatter have made several ground breaking contributions to this development, consistently placing emphasis on the theoretical/structural foundations of the field, on the links with other parts of mathematics, and on general applicability. This effort has, in the past year, lead the team to the realisation of the crucial importance of so called grid decompositions, and associated geometric ways of representing pattern classes. There is strong evidence that this, combined with the existing theory of encodings by words and formal languages, will provide both a comprehensive structure theory for pattern classes and a pathway to solving several outstanding open problems.

This project involves foundational research and algorithm development in pure mathematics. As such, it is to
be expected that the impact of this research outside academia will likely arise indirectly, through the impact
of our research on other research which (perhaps after many stages and several decades) develops to
have practical applications. Historically, advances in discrete mathematics have led to improvements in web
searching, cryptography, genomics and communication technology.

The freely available software that we intend to release in the course of our work will reduce the hurdles to uptake
of our methods by interested researchers, and will enable researchers in related fields to use our techniques
as a "black box", without sophisticated technical training. We plan to include our
methods "under the hood" in software packages such as GAP and Sage, thereby increasing the scope and effectiveness
of those systems, which are widely used both inside and outside academia.

Overseas researchers and students brought to the UK as collaborators or conference participants will have a direct positive impact on the economy.