Geodesic Distance in Planar Graphs

Abstract

We derive the exact generating function for planar maps (genus zero fatgraphs) with vertices of arbitrary even valence and with two marked points at a fixed geodesic distance. This is done in a purely combinatorial way based on a bijection with decorated trees, leading to a recursion relation on the geodesic distance. The latter is solved exactly in terms of discrete soliton-like expressions, suggesting an underlying integrable structure. We extract from this solution the fractal dimensions at the various (multi)-critical points, as well as the precise scaling forms of the continuum two-point functions and the probability distributions for the geodesic distance in (multi)-critical random surfaces. The two-point functions are shown to obey differential equations involving the residues of the KdV hierarchy.

38 pages, 8 figures, tex, harvmac, epsf

References in corpus (2)

• The degree distribution in bipartite planar maps: applications to the Ising model
• Combinatorics of Hard Particles on Planar Graphs

Cited by in corpus (45)

• Local limit of labeled trees and expected volume growth in a random quadrangulation
• The Multi-Orientable Random Tensor Model, a Review
• 2D Quantum Gravity, Matrix Models and Graph Combinatorics
• The three-point function of planar quadrangulations
• Distance statistics in quadrangulations with a boundary, or with a self-avoiding loop
• Trees and spatial topology change in CDT
• On q-functional equations and excursion moments
• Random trees between two walls: Exact partition function
• Statistics of planar graphs viewed from a vertex: A study via labeled trees
• Statistics of geodesics in large quadrangulations
• Planar maps and continued fractions
• On irreducible maps and slices
• Combinatorics of bicubic maps with hard particles
• Geodesic distances in Liouville quantum gravity
• Q-system Cluster Algebras, Paths and Total Positivity
• Distance statistics in quadrangulations with no multiple edges and the geometry of minbus
• Liouville Quantum Gravity and KPZ
• On the diameter of random planar graphs
• Precision measurements of Hausdorff dimensions in two-dimensional quantum gravity
• Confluence of geodesic paths and separating loops in large planar quadrangulations
• On a conjecture by Chapuy about Voronoi cells in large maps
• The skeleton of the UIPT, seen from infinity
• Integrability of graph combinatorics via random walks and heaps of dimers
• The three-point function of general planar maps
• Trees with exponential height dependent weight
• An invariance principle for conditioned trees
• The distance-dependent two-point function of triangulations: a new derivation from old results
• Matrix integrals and enumeration of maps
• Planar maps and random partitions
• Multi-group Gaussian Processes
• The vertical profile of embedded trees
• Forest structure in epigenetic landscapes
• Distance statistics in large toroidal maps
• On symmetric quadrangulations and triangulations
• The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees
• Statistics of the Voronoi cell perimeter in large bi-pointed maps
• On embedded trees and lattice paths
• A note on naturally embedded ternary trees
• Multicritical continuous random trees
• Random maps: proceeding of the Journ{é}es MAS 2014
• Tamper-Evident Complex Genomic Networks
• A First Look at Developers' Live Chat on Gitter
• Resistance distance distribution in large sparse random graphs
• Maps of unfixed genus and blossoming trees
• Eulerian triangulations: two-point function and hull perimeter statistics