Tutte Colloquium - Mireille Bousquet-Mélou

Title: Counting planar maps, 50 years after William Tutte

Abstract:

Every planar map can be properly coloured with four colours. But how many proper colourings has, on average, a planar map with $n$ edges? What if we allow a prescribed number of "monochromatic" edges, the endpoints of which share the same colour? What if we have $q$ colours rather than four?

To address these questions, one considers the generating function (GF) of planar maps, weighted by their chromatic polynomial, or more generally their Tutte polynomial. In the seventies and eighties, Tutte himself studied an instance of the above questions, and obtained an exact result that remained unique in his style for almost 40 years: he established for the GF of properly coloured triangulations an explicit differential equation. The corresponding recurrence relation on the number of these triangulations is still missing a direct combinatorial explanation.

In this survey, I will explain why coloured maps are significantly harder to count than uncoloured ones - whose GFs satisfy polynomial, rather than differential, equations - and present our joint efforts with Olivier Bernardi to understand and extend Tutte's work on coloured maps.
Finally, I will describe how Tutte's key notion of "invariants" has recently been applied to other counting problems (involving lattice walks) in a very successful way.