Automatic discovery of conjectured covers of combinatorial classes
Christian, Anders, Bjarki, Bjarni and Henning
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.