Combinatorial generation via permutation languages

-- Torsten Mütze (University of Warwick)

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; (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).

Category: seminars
Tags: Combi seminar combinatorics