Counting colored planar maps: algebraicity results

Abstract

We address the enumeration of properly q-colored planar maps, or more precisely, the enumeration of rooted planar maps M weighted by their chromatic polynomial χ_M(q) and counted by the number of vertices and faces. We prove that the associated generating function is algebraic when q\not=0,4 is of the form 2+2 cos (jπ/m), for integers j and m. This includes the two integer values q=2 and q=3. We extend this to planar maps weighted by their Potts polynomial P_M(q,ν), which counts all q-colorings (proper or not) by the number of monochromatic edges. We then prove similar results for planar triangulations, thus generalizing some results of Tutte which dealt with their proper q-colorings. In statistical physics terms, the problem we study consists in solving the Potts model on random planar lattices. From a technical viewpoint, this means solving non-linear equations with two "catalytic" variables. To our knowledge, this is the first time such equations are being solved since Tutte's remarkable solution of properly q-colored triangulations.

60 pages

References in corpus (4)

• Walks with small steps in the quarter plane
• Two Non-holonomic Lattice Walks in the Quarter Plane
• The degree distribution in bipartite planar maps: applications to the Ising model
• Tutte chromatic identities from the Temperley-Lieb algebra

Cited by in corpus (29)

• Critical Gaussian multiplicative chaos: Convergence of the derivative martingale
• Intervals in the greedy Tamari posets
• Counting quadrant walks via Tutte's invariant method
• Percolation on uniform infinite planar maps
• An elementary solution of Gessel's walks in the quadrant
• Loop models, random matrices and planar algebras
• Basic properties of the infinite critical-FK random map
• Combinatorics of loop equations for branched covers of sphere
• Loop models on random maps via nested loops: case of domain symmetry breaking and application to the Potts model
• Spanning forests in regular planar maps
• Liouville Quantum Gravity and KPZ
• Selected non-holonomic functions in lattice statistical mechanics and enumerative combinatorics
• On the number of planar Eulerian orientations
• Local convergence of large random triangulations coupled with an Ising model
• Zero temperature phase transitions and their anomalous influence on thermodynamic behavior in the q-state Potts model on a diamond chain
• Critical Behaviour of Spanning Forests on Random Planar Graphs
• Planar maps and random partitions
• Ising model on random triangulations of the disk: phase transition
• Critical Ising model on random triangulations of the disk: enumeration and local limits
• Is the full susceptibility of the square-lattice Ising model a differentially algebraic function?
• On the stationary distribution of reflected Brownian motion in a wedge: differential properties
• Polyharmonic functions and random processes in cones
• Boundary States of the Potts Model on Random Planar Maps
• Liouville Brownian motion at criticality
• Multiple scaling limits of $\mathrm{U}(N{)}^2\times \mathrm{O}(D)$ multi-matrix models
• Enumeration of non-oriented maps via integrability
• The generating function of planar Eulerian orientations
• Sums of Random Matrices and the Potts Model on Random Planar Maps
• Random Matrices, Boundaries and Branes