Searching for combinatorial specifications
Michael, Ragnar, Christian, Yngvi, Anders, Émile, Jay and Henning
A combinatorial class is often studied by finding a combinatorial specification
for it, which is a description of the class in terms of simpler classes, and
perhaps recursions to smaller instances of the original class.
This project aims to automate the discovery of combinatorial specifications
of combinatorial classes. This is achieved by first generating a universe of
interconnected combinatorial classes and then searching for a specification
inside this universe. The main application has been in the area of permutation
patterns, but other domains such as, set partitions, strings, polyominoes and
lattice paths have been considered.
Counting the permutation classes \(\operatorname{Av}(B)\) for every basis \(B\) of size 4 patterns — almost
There are almost 17 million such classes. Cutting away symmetric bases, and then the classes with a regular insertion encoding, leaves 2,897, and Combinatorial Exploration found a specification for each of them except \(\operatorname{Av}(1324)\) and its reverse, \(\operatorname{Av}(4231)\). The next step adds patterns of length 5: the counts, step by step.
How TileScope expands a class
TileScope looks for a combinatorial specification by expanding tilings, and every so often it checks the tilings found so far for one. This page replays the searches of eleven classes tiling by tiling. At each check, the tilings verified so far are green, and those whose verification alone would finish the search are purple.
How a specification counts its root
A combinatorial specification is a system of equations, one for each tiling but the atoms, the empty permutation and the point, and it can be “pumped” for the terms of its class’s counting sequence. This page shows how, for eight classes: it starts with the counts of the atoms, passes them up to the tilings that use them, and so on, round by round, each round ending with the class’s count at the next size. Each count comes with its equation, and a table gathers every count, size by size.
Drawing a permutation uniformly at random
A specification counts its class, and the counts are all it takes to draw a permutation uniformly at random. This page shows the steps for six classes: it counts how many permutations each tiling of a specification has, then draws permutations as the sampler does, choosing at each branch and split in proportion to the counts, and gathers thousands of them into a heatmap of the class.
Using parallel specifications to discover bijections
Two classes with the same counting sequence may have specifications of the same shape, parallel ones, and then taking an object apart down one and building it up the other proves a bijection between the classes. This page shows how TileScope finds parallel specifications, following Jón Steinn Elíasson’s MSc thesis: the two searches and the matching of their rules, the bijection carrying a permutation from one class to the other, and where each of its points goes. It also seeks Claesson and Kitaev’s ten bijections between \(\operatorname{Av}(321)\) and \(\operatorname{Av}(132)\) this way.
Permutation classes by topic
The permutation classes and sets of permutations that come up in a topic, with the specifications found for them: which of them a permutation belongs to, how they sit among each other, and how each specification builds a permutation, step by step.
Papers
- Combinatorial Exploration: An algorithmic framework for enumeration
- Automated enumeration of combinatorial classes with proof-number search
- Using large random permutations to partition permutation classes
- Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding
- Multivariate Combinatorial Exploration
