Enumerative properties of Surface Maps and Chromatic Numbers of Random Maps

A map is a graph G embedded in a surface Σ such that each component of Σ−G is a simply connected region. Those components are called the faces of the map. A circuit map, roughly speaking, is a 2-connected planar map which is internally 3-connected. It has been shown that circuit maps share many nice properties with 3-connected planar maps. In this talk, we discuss some recent developments on the asymptotic number of surface maps which lead to the proof of a conjecture of ’t Hooft in quantum physics. Those asymptotic formulas are also used to study the chromatic numbers of a random map. We will also derive an asymptotic expression for the number of circuit maps with n edges and compare it with the number of 2-connected (3-connected) planar maps. 1 Enumerative properties of surface maps For enumeration purpose, Tutte introduced the notion of rooting a map. A map is rooted by specifying a vertex (called the root vertex), an edge incident with the vertex (called the root edge) and a side of the edge. The face on the specified side is called the root face. Two rooted maps are equivalent (isomorphic) if there is an automorphism of the surface which takes one map to the other and preserves the rooting. Let Mn be the number of rooted planar maps with n edges (loops and multiple edges are allowed) and define the generating function M(x) = n≥