Counting planar maps, coloured or uncoloured

MaRDI QIDQ3089366zbMATH OpenFDO

Authors Mireille Bousquet-Mélou

Publication date 24 August 2011

Full work available at URL https://arxiv.org/abs/2004.08792

zbMATH Keywords

enumerationgenerating functionscoloured planar mapsuncoloured planar maps

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30)

Abstract: We present recent results on the enumeration of $q$-coloured planar maps, where each monochromatic edge carries a weight $u$. This is equivalent to weighting each map by its Tutte polynomial, or to solving the $q$-state Potts model on random planar maps. The associated generating function, obtained by Olivier Bernardi and the author, is differentially algebraic. That is, it satisfies a (non-linear) differential equation. The starting point of this result is a functional equation written by Tutte in 1971, which translates into enumerative terms a simple recursive description of planar maps. The proof follows and adapts Tutte's solution of properly $q$-coloured triangulations (1973-1984). We put this work in perspective with the much better understood enumeration of families of uncoloured planar maps, for which the recursive approach almost systematically yields algebraic generating functions. In the past 15 years, these algebraicity properties have been explained combinatorially by illuminating bijections between maps and families of plane trees. We survey both approaches, recursive and bijective. Comparing the coloured and uncoloured results raises the question of designing bijections for coloured maps. No complete bijective solution exists at the moment, but we present bijections for certain specialisations of the general problem. We also show that for these specialisations, Tutte's functional equation is much easier to solve that in the general case. We conclude with some open questions.

Recommendations

• Counting coloured planar maps: differential equations
• Counting colored planar maps: algebraicity results
• Enumeration of multi-colored rooted maps
• scientific article; zbMATH DE number 3871396
• scientific article; zbMATH DE number 3918402

Cited in

(17)

• Bipolar orientations on planar maps and \(\mathrm{SLE}_{12}\)
• Critical Ising model on random triangulations of the disk: enumeration and local limits
• Concurrency theorems for non-linear rewriting theories
• Precision measurements of Hausdorff dimensions in two-dimensional quantum gravity
• Counting coloured planar maps: differential equations
• Counting colored random triangulations
• Counting colored planar maps: algebraicity results
• Spanning forests in regular planar maps
• On the enumeration of plane bipolar posets and transversal structures
• scientific article; zbMATH DE number 1984533 (Why is no real title available?)
• The two-point function of bicolored planar maps
• Enumeration of rooted 3-connected bipartite planar maps
• Product-coproduct prographs and triangulations of the sphere
• Tree-decorated planar maps
• An elementary solution of Gessel's walks in the quadrant
• scientific article; zbMATH DE number 3882458 (Why is no real title available?)
• Critical behaviour of spanning forests on random planar graphs

Describes a project that uses

Uses Software

• ROTA

This page was built for publication: Counting planar maps, coloured or uncoloured

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3089366)