The Permutation Pattern Avoidance Library (PermPAL)
PermPAL is a database of algorithmically-derived theorems about permutation classes.
The Combinatorial Exploration framework produces rigorously verified combinatorial specifications for families of combinatorial objects. These specifications then lead to generating functions, counting sequence, polynomial-time counting algorithms, random sampling procedures, and more.
This database contains 24,454 permutation classes for which specifications have been automatically found. This includes many classes that have been previously enumerated by other means and many classes that have not been previously enumerated.
Some Notables Successes:
- 6 out of 7 of the principal classes of length 4
- all 56 symmetry classes avoiding two patterns of length 4
- all 317 symmetry classes avoiding three patterns of length 4
- the "domino set" used by Bevan, Brignall, Elvey Price, and Pantone to investigate Av(1324)
- the class Av(3412, 52341, 635241) of Alland and Richmond corresponding a type of Schubert variety
- the class Av(2341, 3421, 4231, 52143) equal to the (Av(12), Av(21))-staircase (see Albert, Pantone, and Vatter), which appears to be non-D-finite
- all of the permutation classes counted by the Schröder numbers conjectured by Eric Egge
- the class Av(34251, 35241, 45231), equal to the preimage of Av(321) under the West-stack-sorting operation (see Defant)
Section 2.4 of the article Combinatorial Exploration: An Algorithmic Framework for Enumeration gives a more comprehensive list of notable results.
The comb_spec_searcher github repository contains the open-source python framework for Combinatorial Exploration, and the tilings github repository contains the code needed to apply it to the field of permutation patterns.
@misc{combinatorial-exploration,
title={Combinatorial {E}xploration: An algorithmic framework for enumeration},
author={Michael H. Albert and Christian Bean and Anders Claesson and \'Emile Nadeau and Jay Pantone and Henning Ulfarsson},
year={2022},
eprint={2202.07715},
archivePrefix={arXiv},
primaryClass={math.CO},
howpublished={\url{https://arxiv.org/abs/2202.07715}},
}