Counting colored planar maps: algebraicity results

DOI10.1016/J.JCTB.2011.02.003MaRDI QIDQ2275895zbMATH OpenOpenAlexFDO

Authors Olivier Bernardi, Mireille Bousquet-Mélou

Publication date 10 August 2011

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

enumerationTutte polynomialalgebraic generating functionscolored planar maps

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Enumeration in graph theory (05C30)

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 chi_M(q) and counted by the number of vertices and faces. We prove that the associated generating function is algebraic when q

ot=0,4 is of the form 2+2 cos (jpi/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,

u), 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.

Recommendations

• Counting coloured planar maps: differential equations
• Counting planar maps, coloured or uncoloured
• scientific article; zbMATH DE number 431811
• Dichromatic polynomials and Potts models summed over rooted maps
• Counting colored random triangulations

Cites work

• scientific article; zbMATH DE number 3882458 (Why is no real title available?)
• scientific article; zbMATH DE number 3849263 (Why is no real title available?)
• scientific article; zbMATH DE number 3891398 (Why is no real title available?)
• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 3620034 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3353321 (Why is no real title available?)
• scientific article; zbMATH DE number 3360190 (Why is no real title available?)
• A Contribution to the Theory of Chromatic Polynomials
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• Acyclic orientations and the chromatic polynomial
• Analytic combinatorics
• Analytic models and ambiguity of context-free languages
• Asymptotic enumeration of constellations and related families of maps on orientable surfaces
• Basic analytic combinatorics of directed lattice paths
• Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees
• Bijective counting of tree-rooted maps and shuffles of parenthesis systems
• Census of planar maps: From the one-matrix model solution to a combinatorial proof
• Chromatic Solutions
• Chromatic Solutions, II
• Chromatic Sums for Rooted Planar Triangulations II: The Case λ = τ + 1
• Chromatic Sums for Rooted Planar Triangulations, III: The Case λ = 3
• Chromatic Sums for Rooted Planar Triangulations, IV: The Case λ = ∞
• Chromatic Sums for Rooted Planar Triangulations, V: Special Equations
• Chromatic Sums for Rooted Planar Triangulations: The Cases λ = 1 and λ = 2
• Chromatic sums revisited
• Complex-temperature phase diagram of Potts and RSOS models
• Dichromatic polynomials and Potts models summed over rooted maps
• Dissections, orientations, and trees with applications to optimal mesh encoding and random sampling
• Exact solution of the \(O(n)\) model on a random lattice
• Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels
• GFUN
• Generating functions for generating trees
• Limits of chromatic zeros of some families of maps
• Linear recurrences with constant coefficients: The multivariate case
• More on the exact solution of the \(O(n)\) model on a random lattice and an investigation of the case \(|n|>2\)
• On a pair of functional equations of combinatorial interest
• On chromatic and dichromatic sum equations
• On the Enumeration of Tree-Rooted Maps
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• On the enumeration of planar maps
• Planar maps as labeled mobiles
• Polynomial equations with one catalytic variable, algebraic series and map enumeration
• The Number of Degree-Restricted Rooted Maps on the Sphere
• The Potts model and the Tutte polynomial.
• The Potts-\(q\) random matrix model: Loop equations, critical exponents, and rational case.
• The dilute Potts model on random surfaces
• The kernel method: a collection of examples
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. II: Extended results for square-lattice chromatic polynomial.
• Tutte chromatic identities from the Temperley-Lieb algebra
• Two non-holonomic lattice walks in the quarter plane
• Walks in the quarter plane: Kreweras' algebraic model
• Walks with small steps in the quarter plane
• Zeroes of chromatic polynomials: A new approach to Beraha conjecture using quantum groups

Cited in

(30)

• Multiple scaling limits of \(\mathrm{U} (N)^2 \times \mathrm{O} (D)\) multi-matrix models
• scientific article; zbMATH DE number 431811 (Why is no real title available?)
• Enumeration of rooted 3-connected bipartite planar maps
• Counting colored random triangulations
• Spanning forests in regular planar maps
• Stochastic processes under constraints. Abstracts from the workshop held September 27 -- October 3, 2020 (hybrid meeting)
• Critical Gaussian multiplicative chaos: convergence of the derivative martingale
• Liouville Brownian motion at criticality
• Critical exponents on Fortuin-Kasteleyn weighted planar maps
• Counting planar maps, coloured or uncoloured
• Liouville quantum gravity and KPZ
• Counting quadrant walks via Tutte's invariant method
• Enumeration of non-oriented maps via integrability
• An elementary solution of Gessel's walks in the quadrant
• The expected number of perfect matchings in cubic planar graphs
• On the number of planar Eulerian orientations
• On the expected number of perfect matchings in cubic planar graphs
• Is the full susceptibility of the square-lattice Ising model a differentially algebraic function?
• An algebraic approach to the planar coloring problem
• Counting coloured planar maps: differential equations
• What is a random surface?
• Local convergence of large random triangulations coupled with an Ising model
• Loop models, random matrices and planar algebras
• Critical behaviour of spanning forests on random planar graphs
• scientific article; zbMATH DE number 671731 (Why is no real title available?)
• Spanning forests in regular planar maps
• Dichromatic polynomials and Potts models summed over rooted maps
• The generating function of planar Eulerian orientations
• Ising model on random triangulations of the disk: phase transition
• Critical Ising model on random triangulations of the disk: enumeration and local limits

Describes a project that uses

Uses Software

• gfun

This page was built for publication: Counting colored planar maps: algebraicity results

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