Un code pour les graphes planaires et ses applications
Un code pour les graphes planaires et ses applications
Français
In the years 1962-1967 W.T. TUTTE and his school have discovered the following remarkable properties of the numbers counting certain families of planar maps : these numbers are expressed as a monomial of factorials and their generating power series are the expansions of algebraic functions. In this article we establish that the properties of these counting numbers are, in most cases, a consequence of the existence of a 1 to 1 mapping from the set of planar maps onto a context free language. In chapter 1 it is shown that the existence of the 1 to 1 mapping (coding) follows from a theorem on permutation-couples (hypermaps). In chapter 2 we use the previous coding theory to establish combinatorial proofs of counting formulas and to explain the relationship between planar maps and the word problem in a group defined by generators and relations. Finally, in chapter 3, we study differential-type equations which are satisfied by codes of families of planar maps. By solving these equations we demonstrate the algebraicity of the power series which generate the map-counting numbers.