Research Projects

Searching for combinatorial specifications
A combinatorial class is often studied by finding a combinatorial specification for it, which is a description of the class in terms of simpler classes, and perhaps recursions to smaller instances of the original class. This project aims to automate the discovery of combinatorial specifications of combinatorial classes. This is achieved by first generating a universe of interconnected combinatorial classes and then searching for a specification inside this universe. The main application has been in the area of permutation patterns, but other domains such as, set partitions, strings, polyominoes and lattice paths have been considered.

Automatic discovery of conjectured covers of combinatorial classes
This project started with an IRF grant in 2014 and the hiring of Christian as a PhD student. The idea is to guess an exact cover a combinatorial class. Currently we have a program that does this in the case of a permutation class.

Sorting
We introduce an algorithm to determine when a sorting operation, such as stacksort or bubblesort, outputs a given pattern. The algorithm provides a new proof of the description of West2stacksortable permutations, that is permutations that are completely sorted when passed twice through a stack, in terms of patterns. We also solve the longstanding problem of describing West3stacksortable permutations. This requires a new type of generalized permutation pattern we call a decorated pattern.

Heuristic algorithms for pattern and statistics discovery
We study algorithms that given a finite set of permutations conjecture (1) a basis of (mesh) patterns describing the set; (2) a structural description of the set, that can then be translated into a generating function enumerating the set.

Coincidence and Wilfclassification
Two patterns are coincident if they are avoided by the same permutations. They are Wilfequivalent if the are avoided by the same number of permutations. We study general rules which can tell us when patterns (or sets of patterns) are coincident or Wilfequivalent.

Schubert varieties and permutation patterns
Description.