Talk by Torsten Mütze: « Combinatorial generation via permutation languages ».
La prochaine séance du séminaire de combinatoire du plateau de Saclay aura lieu ce lundi 29 novembre à 15h en ligne (informations de connexion ci-dessous) avec retransmission en salle Philippe Flajolet du LIX. Nous aurons le plaisir d’écouter Torsten Mütze (University of Warwick) nous parler de « Combinatorial generation via permutation languages ». Le résumé et les informations de connexion sont disponibles ci-dessous.
Résumé : 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).
Connexion:
- Lien : https://ecolepolytechnique.zoom.us/j/84295489822?pwd=QW5Xcjhqbjg5NWJ2L2JQRzhmTkhrUT09
- ID de réunion : 842 9548 9822
- Code secret : 139712
Le programme du séminaire est disponible sur la page https://galac.lri.fr/fr/pages/combi-seminar.html