Minicorso su carte e ipercarte
A short course on maps and hypermaps
Robert Cori (Università di Bordeaux)
In this three-lecture course I will be talking about the classical representation of the embedding of a graph in a surface by means of a pair of permutations. A few examples in combinatorics, algebra and algorithmics will be given.
In this lecture, the combinatorial background will be introduced: permutations, graphs, maps and hypermaps. Special emphasis will be given to the enumeration of permutations by the number of cycles, or equivalently by the number of left-to-right minima. A nice bijection, due to Ossona de Mendez and Rosenstiehl showing the coding of hypermaps through connected permutations will be presented. This will allow us to give the structure of a family of polynomials in two variables defined by weighted Dyck paths.
This lecture will be devoted to the relationship between combinatorial hypermaps and the embedding of graphs in surfaces. The main tool is the fact that the faces of the embedding can be read off the product of the permutations considered. Some relations with the product of commutators in free groups will be investigated. Algorithms for finding minimum and maximum genus of graphs will also be introduced.
Unfortunately, it is not possible to read off the genus of a hypermap from the connected permutation coding it as seen in the first lesson. A different coding has been developed for this purpose; it will be presented during this lecture. A few enumerative applications will be given.