BiSC: An algorithm for discovering generalized permutation patterns
Preprint
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.
@misc{ulfarsson2024biscpaper,
author = {Ulfarsson, Henning},
title = {{BiSC}: {An} algorithm for discovering generalized permutation patterns},
year = {2024},
eprint = {2411.17778},
archivePrefix = {arXiv},
primaryClass = {math.CO},
url = {https://arxiv.org/abs/2411.17778},
}
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:
