Generating Multiset Permutations One Bump at a Time by Prof. Aaron Williams, Williams College

Not-So-Plain Changes: Generating Multiset Permutations One Bump at a Time by Prof. Aaron Williams, Williams College, Wednesday July 10, 1:00 – 1:40pm, North Science Building 113, Wachenheim

Abstract:
Two of the most famous Hamilton paths are the binary reflected Gray code in the hypercube, and plain changes in the permutohedron.  We discuss classic applications of these orders including bell-ringing, puzzle design, mechanical sensors, and exact algorithms for NP-complete problems like the knapsack and traveling salesman problems.  Historically, these paths have been defined using different types of recursion, but in the past decade they have been viewed as the result of simple greedy algorithms.  We survey results arising from this alternate perspective including applications for a wide variety of mathematical objects including matroids, rectangulations, and quotientopes.  During SMALL 2024 the Combinatorial Algorithms for Hamilton Paths group generalized the greedy plain changes algorithm from permutations to multiset permutations.  Moreover, the generalized algorithm generates any subset of multiset permutations satisfying a simple zig-zag property, including those that avoid certain patterns.  As a specific application, our algorithm generates a bump Gray code for the (r-1)-regular words avoiding 132 and 121, which in turn provides minimal-change orders for a variety of r-Catalan objects including r-ary trees and the partitions of convex n-gons into (r+1)-gons.