2017/05/11 by Bean, Christian, Gudmundsson, Bjarki, Ulfarsson, Henning
#05A05 #05A15 #68R15 #Combinatorics (math.CO) #FOS: Mathematics #G.2.1
paper · doi:10.48550/arxiv.1705.04109
We introduce an algorithm that conjectures the structure of a permutation class in the form of a disjoint cover of "rules"; similar to generalized grid classes. The cover is usually easily verified by a human and translated into an enumeration. The algorithm is successful on different inputs than other algorithms and can succeed with any polynomial permutation class. We apply it to every non-polynomial permutation class avoiding a set of length four patterns. The structures found by the algorithm can sometimes allow an enumeration of the permutation class with respect to permutation statistics, as well as choosing a permutation uniformly at random from the permutation class. We sketch a new algorithm formalizing the human verification of the conjectured covers.