Laboratoire d'informatique de l'École polytechnique

Exposé par M. Lepoutre : «Diagrammes ouverts au service des marches»

Speaker: Mathias Lepoutre
Location: Salle Philippe Flajolet
Date: Mer. 26 oct. 2016, 11h00-12h00

Le prochain GT Combi du Plateau de Saclay aura lieu ce mercredi 26 octobre à 11h dans la salle Philippe Flajolet du LIX. Mathias Lepoutre (LIX) nous parlera de «Diagrammes ouverts au service des marches».

Résumé : On s’intéresse à deux problèmes énumératifs auxquels manquait une preuve bijective. Ces deux problèmes, le premier proposé par Bousquet-Mélou et Mishna en 2010 et le deuxième proposé par Burrill, Courtiel, Fusy, Melczer et Mishna en 2015, consistent à apporter des preuves bijectives à des résultats analytiques portant sur certains types de marches du plan. La similarité de ces deux problèmes nous amène à emprunter une démarche commune qui consiste à retirer les arcs ouverts de la représentation par diagrammes définies par Chen, Deng, Du, Stanley et Yan en 2005, pour se ramener à des excursions sous-diagonales marquées. La résolution des problèmes initiaux nous amène à donner des preuves bijectives de plusieurs autres résultats portant sur des chemins non-intersectant, en passant notamment par les forêts de Schnyder et les orientations bipolaires. Travail en commun avec Marni Mishna, Éric Fusy et Julien Courtiel.