<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
On Triangulations with High Vertex Degree
Olivier Bernardi
LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France
Annals of Combinatorics 12 (1) p.17-44 March, 2008
AMS Subject Classification:05C30
We solve three enumerative problems concerning the families of planar maps. More precisely, we establish algebraic equations for the generating function of loopless triangulations in which all vertices have degree at least d, for a certain value d chosen in {3, 4, 5}.
The originality of the problem lies in the fact that degree restrictions are placed both on vertices and faces. Our proofs first follow Tutte's classical approach: We decompose maps by deleting the root-edge and translate the decomposition into an equation satisfied by the generating function of the maps under consideration. Then we proceed to solve the equation obtained using a recent technique that extends the so-called quadratic method.
Keywords: enumeration, asymptotic, triangulation, degree, catalytic variable


1. S.S. Abhyankar, Algebraic geometry for scientists and engineers, Mathematical Surveys and Monographs, Vol. 35, American Mathematical Society, Providence, 1990.

2. C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria, Random maps, coalescing saddles, singularity analysis, and Airy phenomena, Random Structures Algorithms 19 (3-4) (2001) 194-246.

3. D. Bessis, C. Itzykson, and J.B. Zuber, Quantum field theory techniques in graphical enumeration, Adv. Appl. Math. 1 (2) (1980) 109-157.

4. M. Bousquet-Mélou and A. Jehanne, Polynomial equations with one catalytic variable, algebraic series and map enumeration, J. Combin. Theory Ser. B 96 (5) (2006) 623-672.

5. M. Bousquet-Mélou and G. Schaeffer, Enumeration of planar constellations, Adv. Appl. Math. 24 (4) (2000) 337-368.

6. M. Bousquet-Mélou and G. Schaeffer, The degree distribution in bipartite planar maps: application to the Ising model, arXiv: math.CO/0211070.

7. J. Bouttier, P. Di Francesco, and E. Guitter, Census of planar maps: from the one-matrix model solution to a combinatorial proof, Nuclear Phys. B 645 (2002) 477-499.

8. J. Bouttier, P. Di Francesco, and E. Guitter, Combinatorics of bicubic maps with hard particles, J. Phys. A 38 (21) (2005) 4529-4559.

9. W.G. Brown, Enumeration of triangulations of the disk, Proc. London Math. Soc. (3) 14 (1964) 746-768.

10. W.G. Brown, On the existence of square roots in certain rings of power series, Math. Ann. 158 (1965) 82-89.

11. E. Brézin, C. Itzykson, G. Parisi, and J.B. Zuber, Planar diagrams, Comm. Math. Phys. 59 (1) (1978) 35-51.

12. P. Di Francesco, 2D quantum gravity, matrix models and graph combinatorics, In: Applications of Random Matrices in Physics, Springer, Dordrecht, (2006) pp. 33-88.

13. P. Flajolet and A.M. Odlyzko, Singularity analysis of generating functions, SIAM J. Discrete Math. 3 (2) (1990) 216-240.

14. P. Flajolet and R. Sedgewick, Analytic Combinatorics, Book in preparation, available at http://algo.inria.fr/flajolet/Publications/publist.html.

15. Z. Gao, The number of rooted 2-connected triangular maps on the projective plane, J. Combin. Theory Ser. B 53 (1) (1991) 130-142.

16. Z. Gao, The number of rooted triangular maps on a surface, J. Combin. Theory Ser. B 52 (2) (1991) 236-249.

17. Z. Gao and N.C.Wormald, Enumeration of rooted cubic planar maps, Ann. Comb. 6 (2002) 313-325.

18. Z.J. Gao, I.M. Wanless, and N.C. Wormald, Counting 5-connected planar triangulations, J. Graph Theory bf 38 (1) (2001) 18-35.

19. I.P. Goulden and D.M. Jackson, Combinatorial enumeration, John Wiley & Sons, Inc., New York, 1983.

20. R.C. Mullin, On counting rooted triangular maps, Canad. J. Math. 17 (1965) 373-382.

21. B. Salvy and P. Zimmermann, GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable, ACM Trans. Math. Software 20 (2) (1994) 163- 177.

22. D. Poulalhon and G. Schaeffer, A bijection for triangulations of a polygon with interior points and multiple edges, Theoret. Comput. Sci. 307 (2) (2003) 385-401.

23. D. Poulalhon and G. Schaeffer, Optimal coding and sampling of triangulations, In: Automata, Languages and Programming, Springer, Berlin, (2003) pp. 1080-1094.

24. G. Schaeffer, Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees, Electron. J. Combin. (1997) 4 #R20.

25. G. Schaeffer, Conjugaison d'arbres et cartes combinatoires aléatoires, Université Bordeaux I, 1998.

26. G. 't Hooft, A planar diagram theory for strong interactions, Nuclear Phys. B 72 (1974) 461-473.

27. W.T. Tutte, A census of planar triangulations, Canad. J. Math. 14 (1962) 21-38.

28. W.T. Tutte, A census of Hamiltonian polygons, Canad. J. Math. 14 (1962) 402-417.

29. W.T. Tutte, A census of slicings, Canad. J. Math. 14 (1962) 708-722.

30. W.T. Tutte, A census of planar maps, Canad. J. Math. (1963) 15 249-271.

31. W.T. Tutte, Chromatic sums for rooted planar triangulations III: the case λ = 3, Canad. J. Math. 25 (4) (1973) 780-790.

32. W.T. Tutte, Chromatic sums revisited, Aequationes Math. 50 (1-2) (1995) 95-134.

33. D. Zeilberger, The umbral transfer-matrix method. I. foundations, J. Combin. Theory Ser. A 91 (2000) 451-463.

34. A. Zvonkin, Matrix integrals and map enumeration: an accessible introduction, Math. Comput. Modelling 26 (8-10) (1997) 281-304.