Combinatorial generation via permutation languages

Abstract: In this talk I present a general and versatile algorithmic framework for exhaustively generating a large variety of different combinatorial objects, based on encoding them as permutations, which provides a unified view on many known results and allows us to prove many new ones. This talk gives an overview over three main applications of our framework: (1) the generation of pattern-avoiding permutations; (2) the generation of various classes of rectangulations; (3) the generation of lattice congruences of the weak order on the symmetric group and of graph associahedra.

This talk is based on joint work with Liz Hartung, Hung P. Hoang, and Aaron Williams (SODA 2020), and with Arturo Merino (SoCG 2021) and Jean Cardinal.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).