Planar Maps are Well Labeled Trees

Cori, Robert ; Vauquelin, Bernard

Canadian journal of mathematics, Tome 33 (1981) no. 5, pp. 1023-1042

Résumé

In the theory of enumeration, the part devoted to the counting of planar maps gives rather surprising results. Of special interest to the combinatorialists is the conspicuous feature of counting numbers associated with families of maps as discussed in the papers of Tutte, Brown and Mullin. These formulas are by no means easy to prove; this is also a part of their charm. We are convinced therefore that these maps possess deep combinatorial properties. We discuss such properties in this paper.The main result of this article is the construction of a bisection between planar maps and a special family of trees: their vertices are labeled with numbers that differ by at most 1 on adjacent vertices. These trees are said to be well labeled. Combinatorialists usually claim that theorems specifying the “geometry” of objects lead to enumerating formulas. Our result obeys this general rule: we can indeed obtain a new proof of the formula counting the number of rooted planar maps with m edges. Four different proofs of this formula are known to date.

Détail

DOI : 10.4153/CJM-1981-078-2

Bibliographie

[1] 1. Cartier, P. and Foata, D., Problèmes combinatoires de commutation et rearrangement, Lecture Notes in Math. 55 (Springer-Verlag, Berlin, 1969). Google Scholar

[2] 2. Cori, R., Un code pour les graphes planaires et ses applications, Astérisque, Société Math, de France 27 (1975). Google Scholar

[3] 3. Cori, R. and Richard, J., Enumeration des graphes planaires à l'aide de séries formelles en variables non commutatives, Discrete Math. 2 (1972), 115–162. Google Scholar

[4] 4. de Bruijn, N. G. and Morselt, B. J. M., A note on plane trees, J. Combinatorial Theory 2 (1967), 27–34. Google Scholar

[5] 5. Edmonds, J., Combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. 7 (1960), 646. Google Scholar

[6] 6. Foata, D. and Schûtzenberger, M. P., Théorie géométrique des polynômes eulériens, Lecture Notes in Math. 138 (Springer-Verlag, Berlin, 1970). Google Scholar

[7] 7. Jacques, A., Sur le genre d'une paire de substitutions, C. R. Acad. Sci. Paris 267 (1968), 625–627. Google Scholar

[8] 8. Jacques, A., Constellations et graphes topologiques in Combinatorial theory and its applications, Colloq. Math. Soc. Janos Bolyai (North Holland Amsterdam, 1970), 657–672. Google Scholar

[9] 9. Klarner, D. A., Correspondance between plane tree and binary sequences, J. Comb. Theory 9 (1970), 401–411. Google Scholar

[10] 10. Lehman, A. B., A bijective census of rooted planar maps, Communication at Ontario Math. Conference (1970), unpublished. Google Scholar

[11] 11. Raney, G. N., Functional composition patterns and power series reversion, Trans. Amer. Math. Soc. 94 (1960), 441–451. Google Scholar

[12] 12. Read, R. C., The coding of various kinds of unlabeled trees in Graph theory and computing (Academic Press, New York, 1972), 153–182. Google Scholar

[13] 13. Tutte, W. T., A census of slicings, Can. J. Math. 14 (1962), 708–722. Google Scholar

[14] 14. Tutte, W. T., A census of planar maps, Can. J. Math. 15 (1963), 249–271. Google Scholar

[15] 15. Tutte, W. T., On the enumeration of planar maps, Bull. Amer. Math. Soc. 74 (1968), 64–74. Google Scholar

[16] 16. Walsh, T. S. and Lehman, A. B., Counting rooted maps by genus I and II, J. Comb. Theory 13B (1972), 192–218 and 122-141. Google Scholar