-
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.
-
This project started in 2014 with a grant from the Icelandic Research Fund, which brought Christian in as a PhD student. The idea is to guess an exact cover of a combinatorial class: a split of the class into disjoint parts, each described by a rule similar to a generalized grid class. Such a cover is usually easy for a human to check, and it can often be translated directly into an enumeration. For permutation classes we have an algorithm that does this. It succeeds in many cases where other algorithms fail, it is guaranteed to succeed on every polynomial permutation class, and we have run it on every non-polynomial class avoiding a set of patterns of length 4. The covers it finds sometimes enumerate a class by permutation statistics too, and often give a way to sample uniformly at random from it.
-
We introduce an algorithm to determine when a sorting operation, such as
stack-sort or bubble-sort, outputs a given pattern. The algorithm provides a
new proof of the description of West-2-stack-sortable permutations, that is
permutations that are completely sorted when passed twice through a stack, in
terms of patterns. We also solve the long-standing problem of describing
West-3-stack-sortable permutations. This requires a new type of generalized
permutation pattern we call a decorated pattern.
-
We study algorithms that take a finite set of permutations and conjecture (1) a basis of patterns, classical or mesh, that describes the set, or (2) a structural description of the set, which can then be translated into a generating function that enumerates it. The first kind began with a question Sara Billey asked at the AWM Anniversary Conference in 2011: could an algorithm learn the marked mesh patterns that describe a set of permutations? BiSC answers it for mesh patterns. Given a set of permutations, it conjectures the patterns that describe it. It finds the statements of known theorems, such as the descriptions of the smooth and the forest-like permutations, the Baxter permutations, and the stack-sortable and West-2-stack-sortable permutations, and it has led to new theorems and conjectures about the dihedral and alternating subgroups of the symmetric group, Young tableaux, Wilf-equivalences and sorting devices.
-
Two patterns are coincident if they are avoided by the same permutations, and Wilf-equivalent if they are avoided by the same number of permutations of each length. We study general rules that tell when patterns, or sets of patterns, are coincident or Wilf-equivalent. For mesh patterns, the Shading Lemma gives sufficient conditions for when a box can be added to the mesh of a pattern without changing the permutations that avoid it. With it and other rules, the mesh patterns of length 2 fall into at most 56 Wilf-classes. Later we gave necessary conditions for coincidence, such as having the same enclosed diagonals, and rules for coincidence among the permutations that avoid a longer classical pattern, with which we Wilf-classified the mesh patterns of length 2 inside the 231-avoiding permutations. The notion of a force on a pattern then completed the coincidence classification of mesh patterns up to length 3, and it can also be used to enumerate classical permutation classes.
-
Many geometric properties of a Schubert variety can be read off from the
permutation that indexes it. The best-known example is the theorem of
Lakshmibai and Sandhya: a Schubert variety for \(GL_n\) is smooth exactly when its
permutation avoids the patterns 3412 and 4231. We study which other
properties can be described by patterns. We have characterized the Schubert
varieties that are local complete intersections by avoidance of classical
patterns, and described the Gorenstein Schubert varieties, and those defined
by inclusions, with bivincular and marked mesh patterns.