Spanning forests in regular planar maps

DOI10.1016/J.JCTA.2015.04.002zbMATH Open1319.05070arXiv1306.4536OpenAlexW2164119028MaRDI QIDQ491963FDOQ491963

Mireille Bousquet-Mélou, Julien Courtiel

Publication date: 19 August 2015

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

Abstract: We address the enumeration of p-valent planar maps equipped with a spanning forest, with a weight z per face and a weight u per connected component of the forest. Equivalently, we count p-valent maps equipped with a spanning tree, with a weight z per face and a weight mu:=u+1 per internally active edge, in the sense of Tutte; or the (dual) p-angulations equipped with a recurrent sandpile configuration, with a weight z per vertex and a variable mu:=u+1 that keeps track of the level of the configuration. This enumeration problem also corresponds to the limit q -> 0 of the q-state Potts model on p-angulations. Our approach is purely combinatorial. The associated generating function, denoted F(z,u), is expressed in terms of a pair of series defined implicitly by a system involving doubly hypergeometric series. We derive from this system that F(z,u) is differentially algebraic in z, that is, satisfies a differential equation in z with polynomial coefficients in z and u. This has recently been proved to hold for the more general Potts model on 3-valent maps, but via a much more involved and less combinatorial proof. For u >= -1, we study the singularities of F(z,u) and the corresponding asymptotic behaviour of its n-th coefficient. For u>0, we find the standard asymptotic behaviour of planar maps, with a subexponential term in n^{-5/2}. At u=0 we witness a phase transition with a term n^{-3}. When uin[-1,0), we obtain an extremely unusual behaviour in n^{-3}(ln n)^{-2}. To our knowledge, this is a new "universality class" for planar maps.

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

Recommendations

• Spanning forests in regular planar maps
• Spanning forests on random planar lattices
• The enumeration of general rooted planar maps
• Counting coloured planar maps: differential equations
• The generating function of planar Eulerian orientations

zbMATH Keywords

enumerationTutte polynomialplanar mapsspanning forests

Mathematics Subject Classification ID

Trees (05C05) Graph polynomials (05C31) Signed and weighted graphs (05C22) Enumeration in graph theory (05C30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Contribution to the Theory of Chromatic Polynomials
• On the Lambert \(w\) function
• Title not available (Why is that?)
• Chip firing and the Tutte polynomial
• The sand-pile model and Tutte polynomials
• Planar diagrams
• Invariance principles for random bipartite planar maps
• More on the \(\mathrm{O}(n)\) model on random maps via nested loops: loops with bending energy
• A recursive approach to theO(n) model on random maps via nested loops
• Title not available (Why is that?)
• On the Enumeration of Tree-Rooted Maps
• A Census of Planar Maps
• On the scaling limit of random planar maps with large faces
• Planar maps and continued fractions
• A characterization of the Tutte polynomial via combinatorial embeddings
• The phase transition in the uniformly grown random graph has infinite order
• The Potts model and the Tutte polynomial.
• Random maps, coalescing saddles, singularity analysis, and Airy phenomena
• D-finite power series
• Bijective census and random generation of Eulerian planar maps with prescribed vertex degrees
• A Bijection for Rooted Maps on Orientable Surfaces
• Loop models, random matrices and planar algebras
• Growth and percolation on the uniform infinite planar triangulation
• Counting colored planar maps: algebraicity results
• Counting planar maps, coloured or uncoloured
• A Census of Planar Triangulations
• Title not available (Why is that?)
• The asymptotic number of rooted maps on a surface
• A bijection for triangulations, quadrangulations, pentagulations, etc.
• Census of planar maps: From the one-matrix model solution to a combinatorial proof
• Blocked edges on Eulerian maps and mobiles: application to spanning trees, hard particles and the Ising model
• The Potts-\(q\) random matrix model: Loop equations, critical exponents, and rational case.
• Characteristic points of recursive systems
• The dilute Potts model on random surfaces
• Infinite-order phase transition in a classical spin system
• Title not available (Why is that?)
• Exact solutions and infinite-order phase transitions for a general class of Ising models on the regularized Apollonian network
• Title not available (Why is that?)
• A Boltzmann Approach to Percolation on Random Triangulations
• Loop models on random maps via nested loops: the case of domain symmetry breaking and application to the Potts model
• On the average activity of a spanning tree of a rooted map
• Chromatic Sums for Rooted Planar Triangulations: The Cases λ = 1 and λ = 2
• Title not available (Why is that?)
• Dichromatic polynomials and Potts models summed over rooted maps
• Spanning forests on random planar lattices

Cited In (10)

• Spanning trees in random series-parallel graphs
• Random tree-weighted graphs
• Interlacements and the wired uniform spanning forest
• Title not available (Why is that?)
• Is the full susceptibility of the square-lattice Ising model a differentially algebraic function?
• Counting coloured planar maps: differential equations
• Random trees have height \(O(\sqrt{n})\)
• Critical behaviour of spanning forests on random planar graphs
• A criterion for sharpness in tree enumeration and the asymptotic number of triangulations in Kuperberg's \(G_2\) spider
• The generating function of planar Eulerian orientations

This page was built for publication: Spanning forests in regular planar maps

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