pith. sign in

arxiv: 1906.10079 · v1 · pith:LBHND3LInew · submitted 2019-06-24 · 🧮 math.PR

First-passage percolation in random planar maps and Tutte's bijection

Thomas Leh\'ericy This is my paper

Pith reviewed 2026-05-25 16:50 UTC · model grok-4.3

classification 🧮 math.PR
keywords first-passage percolationrandom planar mapsquadrangulationsTutte bijectiongraph distancescaling limits
0
0 comments X

The pith

First-passage percolation distance on random planar maps scales like a constant times the graph distance at large scales.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies first-passage percolation on large random planar maps, assigning i.i.d. lengths to edges and examining the resulting shortest-path distances. It establishes that this percolation distance is asymptotically a constant multiple of the ordinary graph distance for both quadrangulations and general planar maps under uniform or Boltzmann sampling. The same technique is applied to Tutte's bijection, proving that the graph distances on a quadrangulation and its image as a general map remain equivalent as size tends to infinity. Readers care because the result shows that random edge lengths do not alter the large-scale geometry of these maps.

Core claim

In large random quadrangulations and general planar maps, the first-passage percolation distance obtained from i.i.d. edge lengths is shown to behave at large scales like a constant times the usual graph distance. The method also yields that the graph distances on the quadrangulation and on the associated general planar map under Tutte's bijection are equivalent when the number of faces or edges tends to infinity.

What carries the argument

The first-passage percolation distance, formed by summing i.i.d. random edge lengths along paths and taking the infimum, compared against the graph distance that simply counts edges.

If this is right

  • The percolation and graph distances share the same scaling limit up to multiplication by that constant.
  • Tutte's bijection preserves large-scale distances between the two map classes.
  • The large-scale metric structure of these random maps is insensitive to the particular choice of i.i.d. length distribution, provided the scaling constant exists.
  • Metric properties of the maps can be transferred between the quadrangulation and general-map models via the bijection.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The existence of the scaling constant for typical length distributions might allow explicit computation via the maps' generating functions.
  • Similar equivalences could hold for other natural bijections between map classes or for maps with bounded face degrees.
  • After suitable rescaling the percolation distances may converge to the same limiting metric space as the graph distances.
  • The robustness result suggests that first-passage percolation on these maps inherits the same scaling limits already known for graph distance.

Load-bearing premise

The maps are sampled from the standard uniform or Boltzmann distributions on quadrangulations or general maps, and the i.i.d. edge lengths admit a positive finite scaling constant for the percolation distance.

What would settle it

A sequence of maps of increasing size in which the ratio between the first-passage percolation distance and the graph distance fails to converge to any positive constant.

Figures

Figures reproduced from arXiv: 1906.10079 by Thomas Leh\'ericy.

Figure 1
Figure 1. Figure 1: Illustration of Tutte’s bijection. (a) On the left, a quadrangulation with 7 faces. Color the tail of its root vertex in white, and every other vertex in black and white so that adjacent vertices have a different color. (b) In every face of the quadrangulation, add a diagonal between its white corners. (c) Erase the edges of the quadrangulation. (d) The black vertices now have degree zero and are also eras… view at source ↗
Figure 2
Figure 2. Figure 2: We can split the root edge of a truncated hull, add a loop inside the newly created face, and see the map as a quadrangulation of the cylinder of bottom cycle the added loop. We also need to define truncated hulls. To this end, consider first the case where Q is finite and pointed. We label the vertices of Q with their graph distance to ρ, and we consider an integer r such that 0 < r < d Q gr(ρ, ∂). Inside… view at source ↗
Figure 3
Figure 3. Figure 3: Left, a quadrangulation of the cylinder of height 3, with its cycles ∂1Q, ∂2Q in dashed lines. We always draw the top face as the infinite face. Downward triangles are in white and the slots in grey. Right, we erased the content of the slots; in green, the genealogical relation on edges of ∂rQ for 0 ≤ r ≤ 3, in red, the left-most geodesics to the bottom cycle follow the “right” side of downward triangles (… view at source ↗
Figure 4
Figure 4. Figure 4: Left (in grey and thick black lines), the map with simple boundary filling the slot of an edge e (in blue) of ∂rQ with 3 offspring. Right, the truncated quadrangulation we obtain by adding a root edge “over the top vertex of the slot”. Recalling the definition in [11], we say that a forest F with one marked vertex is (R, p, q)-admissible if (i) the forest consists of an ordered sequence of q rooted plane t… view at source ↗
Figure 5
Figure 5. Figure 5: Embedding of the lhpq and its skeleton. The vertices of the lattice Z × −N are the red dots, the vertices of the forest are the green dots, the trees are drawn in green. We drew the downward triangles in cyan, and the slots in grey. Notice that the slot associated with an edge having no offspring may be empty though it is represented here as the “inside” of a double edge (this simply means that this double… view at source ↗
Figure 6
Figure 6. Figure 6: Constructing a part of the lhpq from truncated quadrangulations. In the lower part, the dotted lines are trees of the skeleton and the dashed lines are ∂−r−1L and ∂−rL for some r ≥ 0. The upper part of the figure shows 5 truncated quadrangulations that fill in successive slots as shown in the lower part. Note that any edge of a truncated quadrangulation that is glued to some edge of ∂−rL is removed in the … view at source ↗
Figure 7
Figure 7. Figure 7: Block decomposition of the half-slice HL0 −3 . The first block is pictured in green, the second one in red, the third one in blue. In the upper figure, we represented the skeleton in brown (with trees of height 3 in thick lines), slots in dark gray, and the left-most geodesics following the right boundary of trees of height 3 in green. In this example, ξ1 = 1, ξ2 = 4, ξ3 = 8. The skeleton of L is made of i… view at source ↗
Figure 8
Figure 8. Figure 8: Paths started from a point x on the left boundary can either stay in a slice of height 3m around x (and have length at least C [PITH_FULL_IMAGE:figures/full_fig_p017_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: As soon as there are no bad intervals, every left-most geodesic started at a vertex v of the top boundary coalesces before time γr with the left-most geodesic started at one of the endpoints of the interval that contains v. By choosing A large enough, we ensure that with high probability there is no bad interval. to proving that we can choose A > 0 such that, for all r large enough, the probability of havi… view at source ↗
Figure 10
Figure 10. Figure 10: The CVS correspondence applied to a finite labeled tree (in black). The thick red edge is the root edge of the quadrangulation, and its orientation is determined by  (here  = 1). The CVS correspondence allows us to code uniform rooted and pointed quadrangulations by uniform rooted labeled plane trees. More precisely, let Tn be a uniform rooted plane tree with n edges. Given Tn, assign i.i.d. weights on … view at source ↗
Figure 11
Figure 11. Figure 11: Tutte’s bijection applied to a truncated hull of even radius, here of radius 2. In every face of Q of degree 4 but the external one, draw a “diagonal” between the two white corners. Then erase the edges of the original map and all black vertices, keeping however the edges of the boundary. The map we obtain is rooted at the edge drawn in the face of Q on the left of the root edge of Q, oriented in such a w… view at source ↗
Figure 12
Figure 12. Figure 12: Left, a part of the annulus C(2R − 2, 2R) with slots in pale yellow, the skeleton in dotted blue lines, and the special slot in green. We have not drawn the edges and vertices inside the other slots. The downward path (in red) visits u0, u−1, u−2, . . . until it meets a “good” vertex (here u−4), whose corresponding slot is filled by the truncated quadrangulation on the right side. This path can be extende… view at source ↗
Figure 13
Figure 13. Figure 13: In blue, the left-most geodesics (in Q∞) started from v, w two vertices of ∂2RQ∞, that coalesce before reaching ∂2sQ∞. The downward path in T (Q∞) started at w (in green) cannot cross the left-most geodesic in Q∞ from w, and the right downward path in T (Q∞) started at v (in red) cannot cross the left-most geodesic in Q∞ from v: by planarity, they must cross (and thus intersect) before reaching ∂2sQ∞. We … view at source ↗
read the original abstract

We consider large random planar maps and study the first-passage percolation distance obtained by assigning independent identically distributed lengths to the edges. We consider the cases of quadrangulations and of general planar maps. In both cases, the first-passage percolation distance is shown to behave in large scales like a constant times the usual graph distance. We apply our method to the metric properties of the classical Tutte bijection between quadrangulations with $n$ faces and general planar maps with $n$ edges. We prove that the respective graph distances on the quadrangulation and on the associated general planar map are in large scales equivalent when $n \to \infty$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript claims that in large random planar maps sampled from the uniform or Boltzmann distributions (quadrangulations and general maps), the first-passage percolation distance with i.i.d. edge lengths is asymptotically equivalent to a constant multiple of the graph distance. It further claims that the graph distances on a quadrangulation with n faces and the associated general planar map with n edges under Tutte's bijection are asymptotically equivalent as n tends to infinity.

Significance. If the results hold, they extend existing knowledge on the metric properties of random planar maps from the unweighted graph-distance case to the first-passage percolation setting with random edge weights. The application to Tutte's bijection provides a direct link between the two models without introducing additional load-bearing assumptions beyond those already used for the FPP result. The reliance on standard models and the assumption that a scaling constant exists for the i.i.d. lengths is a strength, as it allows the work to build directly on established literature in the field.

minor comments (1)
  1. The abstract would benefit from a brief explicit statement of the distributions (uniform/Boltzmann) and the precise assumption on the edge-length distribution that guarantees the existence of the scaling constant.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report and recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper's central claims rest on the standard uniform/Boltzmann distributions for random planar maps together with i.i.d. edge lengths (for which a scaling constant is posited to exist). The equivalence between first-passage percolation distance and graph distance, as well as the large-scale equivalence under Tutte's bijection, is derived from these model assumptions without any reduction of the target quantities to fitted parameters, self-definitions, or load-bearing self-citations. The derivation chain is self-contained against external benchmarks and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

Abstract-only review; no explicit free parameters, ad-hoc axioms, or invented entities are identifiable. Relies on standard domain assumptions about random map distributions and i.i.d. edge lengths.

axioms (2)
  • domain assumption Random planar maps follow uniform or Boltzmann distributions on quadrangulations or general maps with n faces/edges
    The paper considers large random planar maps under these standard models.
  • domain assumption Edge lengths are i.i.d. random variables allowing a positive finite scaling constant to exist
    Required for the FPP distance to behave like a constant times graph distance.

pith-pipeline@v0.9.0 · 5626 in / 1264 out tokens · 32195 ms · 2026-05-25T16:50:55.717167+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · 1 internal anchor

  1. [1]

    Rescaled bipartite planar maps converge to the brownian map

    Céline Abraham et al. Rescaled bipartite planar maps converge to the brownian map. InAnn. Inst. Henri Poincaré Probab. Stat., volume 52, pages 575–595. Institut Henri Poincaré, 2016

    work page 2016

  2. [2]

    The scaling limit of random simple triangulations and random simple quadrangulations.Ann

    Louigi Addario Berry and Marie Albenque. The scaling limit of random simple triangulations and random simple quadrangulations.Ann. Probab., 45(5):2767–2825, 2017

    work page 2017

  3. [3]

    The scaling limit of uniform random plane maps, via the Ambjørn–Budd bijection.Electron

    Jérémie Bettinelli, Emmanuel Jacob, and Grégory Miermont. The scaling limit of uniform random plane maps, via the Ambjørn–Budd bijection.Electron. J. Probab., 19, 2014

    work page 2014

  4. [4]

    Geometric and spectral properties of causal maps

    Nicolas Curien, Tom Hutchcroft, and Asaf Nachmias. Geometric and spectral properties of causal maps. J. Eur. Math. Soc. (JEMS), to appear. 45

    work page

  5. [5]

    The Brownian plane.J

    Nicolas Curien and Jean-François Le Gall. The Brownian plane.J. Theoret. Probab., 27(4):1249– 1291, 2014

    work page 2014

  6. [6]

    First-passage percolation and local modifications of distances in random triangulations.Ann

    Nicolas Curien and Jean-François Le Gall. First-passage percolation and local modifications of distances in random triangulations.Ann. Sci. Éc. Norm. Supér.(4), to appear

    work page

  7. [7]

    A view from infinity of the uniform infinite planar quadrangulation

    Nicolas Curien, Laurent Ménard, and Grégory Miermont. A view from infinity of the uniform infinite planar quadrangulation. Lat. Am. J. Probab. Math. Stat. (ALEA), 10(1):45–88, 2013

    work page 2013

  8. [8]

    The distribution of the maximum vertex degree in random planar maps

    Zhicheng Gao and Nicholas C Wormald. The distribution of the maximum vertex degree in random planar maps. J. Combin. Theory Ser. A, 89(2):201–230, 2000

    work page 2000

  9. [9]

    Convergence of discrete snakes.J

    Svante Janson and Jean-François Marckert. Convergence of discrete snakes.J. Theoret. Probab., 18(3):615–645, 2005

    work page 2005

  10. [10]

    Local structure of random quadrangulations

    Maxim Krikun. Local structure of random quadrangulations.arXiv:math/0512304v2, 2008

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  11. [11]

    Separating cycles and isoperimetric inequalities in the uniform infinite planar quadrangulation.Ann

    Jean-François Le Gall and Thomas Lehéricy. Separating cycles and isoperimetric inequalities in the uniform infinite planar quadrangulation.Ann. Probab., 2017

    work page 2017

  12. [12]

    Geodesics in large planar maps and in the brownian map

    Jean-François Le Gall. Geodesics in large planar maps and in the brownian map. Acta Math., 205(2):287–360, 2010

    work page 2010

  13. [13]

    Brownian disks and the Brownian snake

    Jean-François Le Gall. Brownian disks and the Brownian snake. In Ann. Inst. Henri Poincaré Probab. Stat., volume 55, pages 237–313. Institut Henri Poincaré, 2019

    work page 2019

  14. [14]

    Uniqueness and universality of the Brownian map

    Jean-François Le Gall et al. Uniqueness and universality of the Brownian map. Ann. Probab., 41(4):2880–2960, 2013

    work page 2013

  15. [15]

    Scaling limits of random trees and planar maps

    Jean-François Le Gall, Grégory Miermont, et al. Scaling limits of random trees and planar maps. Probability and statistical physics in two and more dimensions, 15:155–211, 2012

    work page 2012

  16. [16]

    An improved subadditive ergodic theorem

    Thomas M Liggett. An improved subadditive ergodic theorem. Ann. Probab., pages 1279–1285, 1985

    work page 1985

  17. [17]

    Percolation on uniform infinite planar maps

    Laurent Ménard, Pierre Nolin, et al. Percolation on uniform infinite planar maps. Electron. J. Probab., 19, 2014

    work page 2014

  18. [18]

    The Brownian map is the scaling limit of uniform random plane quadrangula- tions

    Grégory Miermont. The Brownian map is the scaling limit of uniform random plane quadrangula- tions. Acta Math., 210(2):319–401, 2013. 46

    work page 2013