Combinatorial generation via permutation languages
Time: 15:00 -- Location: online
In this talk we present a versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations. This framework provides a unified view on many known Gray code results and allows us to prove many new ones, and it yields efficient algorithms for computing Hamilton paths and cycles on large classes of polytopes. We give an overview of the ingredients of the framework, and we present two of its main applications: (1) the generation of pattern-avoiding permutations (see www.combos.org/jump); (2) the generation of lattice congruences of the weak order on the symmetric group. This talk is based on joint work with Liz Hartung, Hung P. Hoang, and Aaron Williams (SODA 2020).