Seminar: Jumping through Permutation Patterns: Gray Codes for Catalan Structures, Rectangulations, and more!

Speaker: Dr. Aaron Williams

Abstract: In 1677 Fabian Stedman published a book on bell-ringing called Campanalogia. This book described a pattern of permutations which came to be known as plain changes to bell ringers and the Steinhaus-Johnson-Trotter algorithm for mathematicians and computer scientists.

In this talk we generalize the simple idea behind this order so that it generates various subsets of permutations, including subsets that can be described using pattern avoidance. In particular, the 132-avoiding permutations are counted by the Catalan numbers, and our generalized order provides Gray codes for Catalan structures including binary trees with n nodes, diagonalizations of an n-gon. Similarly, the 1-32-avoiding permutations (using vincular notation) are counted by the Bell-numbers, and our generalized order provides a Gray code for the partitions of an n-set. More impressively, we provide the first Gray code for diagonal rectangulations which are in correspondence with Baxter permutations which avoid the patterns 3-14-2 and 2-41-3.

This is joint work with Elizabeth Hartung (MCLA) and Torsten Mütze (TU Berlin).