Notable successes for TileScope (aka PermScope) as of June 2019

17 Jun 2019 - Henning

Tilescope is an algorithm for finding and proving structures of permutation classes. When it succeeds it returns a combinatorial specification for the class. In many cases the specification only uses Cartesian products and disjoint unions, and this allows us to turn the specification into a system of equations with a single variable. Some notable examples include:

• Several 2x4 classes enumerated by the Schröder numbers: Av(1342,1432), Av(1342,3142), Av(2413,3142)
• All but one of the 2x4 classes equinumerous to the smooth permutations: Av(1324,2143), Av(1324,2413), Av(1342,2431), Av(1342,3241)
• Permutations drawn on an X and a diamond: Av(2143,2413,3142,3412)

In other cases more complicated operators are needed, producing a system with a catalytic variable. The system can still be solved using the kernel method or other approaches:

• The remainder of the 2x4 classes enumerated by the Schröder numbers: Av(1234,1243), Av(1243,1324), Av(1243,1342), Av(1243,2143), Av(1324,1342), Av(1342,1423), Av(1342,2341)
• The remaining 2x4 class equinumerous to the smooth permutations: Av(1342,2314)

Finally, there are cases when we get systems with several catalytic variables. In these cases the structures represent polynomial-time algorithms that can be used to generate terms

• Av(1234)
• Av(1234,1324), conjectured to not satisfy any ADE, see Albert et al
• Av(1342,3412), first enumerated by Bevan in 2015
• Av(1243,2341), first enumerated by Miner in 2016