Combinatorics of Surface Triangulations
by
Samuel Vidal
Laboratoire d'Informatique fondamentale de Lille (LIFL)

Triangulations of surfaces are one of the most basic building block of algebraic topology and they constitute an important data structure in computer graphics as they provide a handy discrete model of surfaces. From the point of view of computer science, the applications of surface triangulations are well known and numerous, they touch both practical and theoretical aspects of the discipline and they range from computer graphics to discret methods of solving partial differential equations. They also play a central role in manyalgorithms of computational geometry, a fast growing sub ject having an heavy industrial impact due to its use in computer aided design.

One particularly interesting treat of the sub ject, apart from its broad range of applications, is precisely its ubiquity both in computer science, mathematical physics and even pure mathematics, providing generous range of fruitful exchange between seemingly remote parts of science.

From the point of view of mathematics, the theory of combinatorial maps is also a venerable subject dating back to Cayley and Hamilton. Since those times, it generated an impressive amount of results of all sorts concerning the particular enumeration problem of counting the rooted combinatorial maps. Those results came from various communities of researchers, each with its own methods and tradition. Among them, enumerative combinatorists of course played a significant role, starting with pioneering works by Tutte [6] on rooted planar maps. Those works where at first motivated by the four color problem.

Theoretical physicists also played a significant role, starting with the work by t’Hooft [5] on integration on random matrix spaces and Feynman diagrams. Pure mathematicians like Harer and Zagier [1] also have contributed to the theory in connection with cutting edge algebraic geometry problems concerning moduli spaces of Riemann surfaces. Last but not least, one must mention in mathematical physics the Witten-Kontsevich model of quantum gravity [2] using in a central fashion the higher combinatorics of triangular maps and trivalent diagrams.

Although a lot is known concerning the theory of rooted combinatorial maps, very little is currently known about the outstanding problem of enumeration of unrooted combinatorial maps up to isomorphism, except for planar maps with the pioneering work of Liskovets [3]. It appears as a very difficult problem of combinatorics, which stayed barely untouched for almost 150 years. As a matter of fact, the only general result on those important ob jects were up to now contained in the recent paper by Mednykh and Nedela [4]. Using the Joyal theory of structure species, we describe a way to count both rooted and unrooted triangulations, up to diffeomorphism of the underlying surfaces. The generating series thus obtained are explicitly connected to the asymptotic expansion of the Airy function.

References

[1] J. Harer and D. Zagier. The euler characteristic of the moduli space of curves. Invent. Math., 85:457–486, 1986.

[2] M. Kontsevich. Intersection theory on the moduli space of curves and the matrix airy function. Commun. Math. Phys., 147:1–23, 1992.

[3] V. A. Liskovets. A census of nonisomorphic planar maps. In L. Lovasz and V.T. Sos, editors, Algebraic methods in graph theory, volume II, 1981. North-Holland, Amsterdam.

[4] A. Mednykh and R. Nedela. Enumeration of unrooted maps of a given genus. J. Comb. Theory, Ser. B, 96(5):706–729, 2006.

[5] G. t’Hooft. A planer diagram theory for strong interactions. Nuclear Physics B, 72:461–473, 1974.

[6] W. T. Tutte. A census of planar triangulations. Canad. J. Math., 14:21–38, 1962.

Date received: May 21, 2008

Copyright © 2008 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # caxd-18.