Combinatorics of bicubic maps with hard particles

Abstract

We present a purely combinatorial solution of the problem of enumerating planar bicubic maps with hard particles. This is done by use of a bijection with a particular class of blossom trees with particles, obtained by an appropriate cutting of the maps. Although these trees have no simple local characterization, we prove that their enumeration may be performed upon introducing a larger class of "admissible" trees with possibly doubly-occupied edges and summing them with appropriate signed weights. The proof relies on an extension of the cutting procedure allowing for the presence on the maps of special non-sectile edges. The admissible trees are characterized by simple local rules, allowing eventually for an exact enumeration of planar bicubic maps with hard particles. We also discuss generalizations for maps with particles subject to more general exclusion rules and show how to re-derive the enumeration of quartic maps with Ising spins in the present framework of admissible trees. We finally comment on a possible interpretation in terms of branching processes.

41 pages, 19 figures, tex, lanlmac, hyperbasics, epsf. Introduction and discussion/conclusion extended, minor corrections, references added

References in corpus (15)

• 2D Gravity and Random Matrices
• Matrix Model Calculations beyond the Spherical Limit
• Transfer Matrix Formalism for Two-Dimensional Quantum Gravity and Fractal Structures of Space-time
• Geodesic Distance in Planar Graphs
• Scaling in quantum gravity
• Construction of Non-critical String Field Theory by Transfer Matrix Formalism in Dynamical Triangulation
• Census of Planar Maps: From the One-Matrix Model Solution to a Combinatorial Proof
• The degree distribution in bipartite planar maps: applications to the Ising model
• Critical and Tricritical Hard Objects on Bicolorable Random Lattices: Exact Solutions
• Random trees between two walls: Exact partition function
• Statistics of planar graphs viewed from a vertex: A study via labeled trees
• The Two-point Function of c=-2 Matter Coupled to 2D Quantum Gravity
• Counting Colored Random Triangulations
• Combinatorics of Hard Particles on Planar Graphs
• Geometrically Constrained Statistical Models on Fixed and Random Lattices: From Hard Squares to Meanders

Cited by in corpus (9)

• The three-point function of planar quadrangulations
• Blocked edges on Eulerian maps and mobiles: Application to spanning trees, hard particles and the Ising model
• Loop models on random maps via nested loops: case of domain symmetry breaking and application to the Potts model
• Confluence of geodesic paths and separating loops in large planar quadrangulations
• Matrix integrals and enumeration of maps
• Planar maps and random partitions
• Combinatoire du polynôme de Tutte et des cartes planaires
• On triangulations with high vertex degree
• Multicritical continuous random trees