Counting colored planar maps: algebraicity results

DOI10.1016/J.JCTB.2011.02.003zbMATH Open1223.05123arXiv0909.1695OpenAlexW2033490359MaRDI QIDQ2275895FDOQ2275895

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)

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.

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

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

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)

Cites Work

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

Cited In (30)

• Multiple scaling limits of \(\mathrm{U} (N)^2 \times \mathrm{O} (D)\) multi-matrix models
• Title not available (Why is that?)
• Enumeration of rooted 3-connected bipartite planar maps
• Counting colored random triangulations
• Stochastic processes under constraints. Abstracts from the workshop held September 27 -- October 3, 2020 (hybrid meeting)
• Spanning forests in regular planar maps
• Critical Gaussian multiplicative chaos: convergence of the derivative martingale
• Liouville Brownian motion at criticality
• Counting planar maps, coloured or uncoloured
• Critical exponents on Fortuin-Kasteleyn weighted planar maps
• Liouville quantum gravity and KPZ
• Counting quadrant walks via Tutte's invariant method
• The expected number of perfect matchings in cubic planar graphs
• Enumeration of non-oriented maps via integrability
• An elementary solution of Gessel's walks in the quadrant
• 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?
• Counting coloured planar maps: differential equations
• An algebraic approach to the planar coloring problem
• What is a random surface?
• Local convergence of large random triangulations coupled with an Ising model
• Title not available (Why is that?)
• Critical behaviour of spanning forests on random planar graphs
• Spanning forests in regular planar maps
• Loop models, random matrices and planar algebras
• 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

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)