BiSC: an algorithm for guessing bases
BiSC looks at the permutations in a set up to some finite length, and then conjectures the mesh patterns the set avoids.
Visual legend
The permutations BiSC learns from
The patterns missing from the set
How BiSC works
Mesh patterns
Mesh patterns were introduced by Brändén and Claesson, in "Mesh patterns and the expansion of permutation statistics as sums of permutation patterns", Electron. J. Combin. 18(2) (2011), P5. A mesh pattern (p, R) is a classical pattern p of length k together with a set R of shaded boxes, among the (k + 1)² boxes that the lines through the points of p cut its square into: the box (i, j) is the i-th from the left and the j-th from the bottom, counting from 0. A permutation π contains (p, R) when π has an occurrence of p that leaves every shaded box empty: no other point of π lies in the region between the occurrence's points that the box stands for.
Learning
We consider all permutations in the set up to some fixed length n. For a classical pattern p, and an occurrence of p in some permutation π, we note the maximum shading R we can put on p so that the mesh pattern (p, R) has the same occurrence in π. In this way we learn the maximal allowed shadings of all the classical patterns, up to some length m.
Forbidding
For a pattern p that occurs in no permutation, we output p as an unshaded classical pattern. For patterns that have occurrences, we output their minimal shadings that lie outside of the allowed shadings we learned in the previous step.
The basis, and the check
We try to find a smallest subset of the patterns we output that describes the set of permutations, and check it on longer permutations.