Theses and dissertations

Ph.D.: Combinatorial enumeration of rooted maps on a surface and a bijection

Jury

MM. Robert Cori

Alexandre Zvonkine

Jean-Yves Thibon

Paul Zimmermann

Didier Arquès

Abstract

A map is a connected graph embedded in a surface. Maps are topological objects which can be counted up to homeomorphism by their number of vertices, edges and faces. Maps admit inner symmetries which make them hard to enumerate. The scope of this work is limited to rooted maps, since rooting eliminates all symmetries.

The exact number of rooted maps on a given surface is only known for surfaces with small genus, like the sphere (genus 0) or the projective plane (genus 1), since the enumeration methods complexity strongly increases with the surface genus.

An important part of this work was to convert such a computational method into a common pattern symbolic proof for all the generating series of rooted maps with positive genus.

For any orientable surface, the problem unknown is reduced to a polynomial whose degree is bounded by a simple function of the surface genus. A similar result is obtained for non orientable surfaces.

These results lead to practical methods for exact enumeration. They have been implemented in a software tool. New explicit formulas are given for enumerations up to genus 3.

Independently, a new bijection between a planar hypermaps family and a polygon dissections family, both counted by Schröder numbers, is described.

 KEYWORDS: combinatorics, enumeration, rooted map, surface, generating series.