Summer School on Algebraic and Enumerative Combinatorics
Lectures by Christian Krattenthaler
S. Miguel de Seide, Portugal
Topic: Map Enumeration
The enumeration of maps is of interest to researchers
in many different areas of mathematics and physics:
- to combinatorialists: obviously so, after all,
map enumeration is a very beautiful subject on
its own; furthermore, it stands at the beginning
of the asymptotic enumeration of planar graphs,
see Marc Noy's lectures;
- to algebraists: if you want to do computations in
the group algebra of the symmetric group, then -
sooner or later - you will run into the problem
of factoring a permutation (subject to certain
constraints) into the product of some other
permutations (subject to certain constrants);
this problem is equivalent to a map enumeration
problem;
- to algebraic topologists: if you want to count
ramified coverings of the sphere by itself, then
this translates into a permutation factorization
problem, and, hence, into map counting problem;
- to probabilists: a way to design a model of
random surfaces is by considering large maps
in a scaling limit;
- to statistical physicists: if you want to develop
quantum gravity then you build models of large
maps.
This course gives an introduction into the enumeration of
maps with a focus on methods, while less so on results.
The methods discussed are:
- recursion, translation into equations for generating
functions;
- quadratic method, kernel method, the generalization by
Bousquet-M\'elou and Jehanne;
- systems of functional equations and the
Lagrange-Good inversion formula;
- map-tree bijections.