BiSC: An algorithm for discovering generalized permutation patterns

Preprint

Henning

Code BiSC is an algorithm inspired by a question asked by Sara Billey in the talk Consequences of the Lakshmibai-Sandhya Theorem at the AWM Anniversary Conference in 2011. She asked whether one could write an algorithm for “learning marked mesh patterns”. The BiSC algorithm answers this question for mesh patterns. The name of the algorithm comes from the last name of Sara Billey, as well as the last names of Einar Steingrímsson and Anders Claesson who were also influential in the development of the algorithm.

This page shows the algorithm at work, step by step, on sets such as the West-2-stack-sortable permutations and the factorial Schubert varieties.

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

Download the paper

Conjectures found by BiSC

Given a set of permutations, BiSC conjectures a description of the set by the patterns it avoids. Below are conjectures it has found since the paper, for sets studied in other papers, and then the conjectures in the paper. As far as I know each is open. If you prove or disprove one, please let me know, and cite the paper. A mesh pattern \((p, R)\) is the classical pattern \(p\) with the boxes in \(R\) shaded, as in the paper.

Found since

Each description below has been checked by computer on all permutations up to length 10.

Set Conjectured description
Permutations avoiding 2143, 2341, 2413, 2431, 4123, 4213 and 4231 whose doubly pruned complex is pure, from Adams-Jessmore, Griffin and Ryan \(\operatorname{Av}(2143, 2341, 2413, 2431, 3412, 4123, 4213, 4231)\)
Avoiders of the arrow pattern \((32; 1 \to 3)\), from Zhou and Yu \(\operatorname{Av}(3142, 4132, (321, \{(0,3), (1,3), (2,3), (3,2)\}))\)
Permutations attaining the bound \(\ell - \ell' = 2\beta\) of Tenner and Vatter, Corollary 1.5 \(\operatorname{Av}(3421, 4312, 4321, 34512, 45123)\)
Permutations sorted by the 123-machine of Cerbai, Claesson and Ferrari \(\operatorname{Av}((132, \{(0,3), (1,2)\}), 3214, 4213)\)
N-free semiorder Fishburn permutations, Dukes and McNamara, Problem 6.3 \(\operatorname{Av}(231, 4123)\)

These sets were generated, and BiSC run on them, by an AI agent working for me, and each set was checked against a second implementation.

In the paper

Set Conjecture
The union of the dihedral groups \(D_n\), acting on the vertices of a regular \(n\)-gon \(\operatorname{Av}(S_4 \setminus D_4)\), the avoiders of the 16 permutations of length 4 that are not in \(D_4\)
The union of the alternating groups Its only basis of mesh patterns is the odd permutations, each with every box shaded
Permutations whose RSK shape does not contain \((3,2)\) The avoiders of four marked mesh patterns, given in the paper
Permutations sortable by a stack whose content avoids \(1324\), followed by a classical stack \(\operatorname{Av}(\mu_1, \mu_2, 42315, 52314)\), where \(\mu_1 = (132, \{(0,1), (0,2), (2,0)\})\) and \(\mu_2 = (132, \{(0,3), (1,2)\})\)

Last updated 13 November 2026.

The code

BiSC is part of Permuta, a Python library for working with permutations and patterns. To try it, it is enough to have a function prop that returns True or False on permutations, and to call auto_bisc(prop), from permuta.bisc.

This paper is a part of the following projects: