Séminaire Philippe Flajolet

Enumération bijective des cartes planaires serrées

par Emmanuel Guitter (IPhT)

Europe/Paris
IHP

IHP

Description

Une carte planaire serrée est un graphe plongé dans le plan avec des sommets marqués, de sorte que tous ses sommets de degré 1 soient marqués. Pour un jeu donné de faces étiquetées de 1 à n de degrés prescrits (et en interprétant les sommets marqués comme des faces de degré 0), le nombre de cartes planaires serrées est, comme l’a montré Norbury, un quasi-polynôme de degré n-3 dans les carrés des degrés des faces. Je montrerai comment obtenir la formule explicite de ce quasi-polynôme de manière purement bijective par une décomposition des cartes planaires serrées en tranches (« slices »). Je montrerai enfin comment en déduire une extension de la « formule des slicings » de Tutte (1962) pour l’énumération des cartes planaires non nécessairement serrées, dans le cas où ces cartes ont un nombre arbitraire de faces de degrés impairs. Travail en collaboration avec Jérémie Bouttier et Grégory Miermont.