Heuristic algorithms for pattern and statistics discovery

Henning

Code 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.

BiSC, step by step

BiSC learning from the West-2-stack-sortable permutations, step by step

This page shows BiSC at work, step by step, on the West-2-stack-sortable permutations, the permutations sortable by the 132-machine and by the 1324-machine, the factorial Schubert varieties and the simsun permutations. Length by length, BiSC goes through the permutations: each one missing from the set is a pattern it must explain, and each member teaches it which shadings of those patterns the members allow. It then forbids the shadings no member allows, keeps the fewest forbidden patterns that explain every missing permutation, and checks them on longer permutations.

Papers