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

Curien, Nicolas; Le Gall, Jean-François

Annales scientifiques de l'École Normale Supérieure, Série 4, Tome 52 (2019) no. 3, pp. 631-701.

Nous étudions l'effet de perturbations locales de la distance de graphe dans les grandes triangulations planaires aléatoires. Nous montrons qu'à grande échelle, la nouvelle distance se comporte comme $c$ fois la distance de graphe où $c$ est une constante déterministe dépendant du type de la perturbation effectuée. Cela s'applique en particulier à la métrique de percolation de premier passage obtenue en donnant des longueurs i.i.d. à chaque arête, à la distance de graphe sur la carte duale et au modèle d'Eden (percolation de premier passage avec poids exponentiels sur la carte duale). Dans les deux derniers cas, nous pouvons même calculer explicitement la constante $c$ en utilisant un lien avec le processus d'épluchage (peeling process). En général, la constante $c$ reste inconnue et provient d'un argument de sous-additivité appliqué à un modèle infini de triangulation du demi-plan qui décrit la structure d'une grande triangulation aléatoire près du bord d'une grande boule centrée à l'origine. Nos résultats s'appliquent également à l'UIPT et montrent que les grandes boules pour la distance modifiée sont proches de boules pour la distance de graphe initiale.

We study local modifications of the graph distance in large random triangulations. Our main results show that, in large scales, the modified distance behaves like a deterministic constant $𝐜\in (0,\infty )$ times the usual graph distance. This applies in particular to the first-passage percolation distance obtained by assigning independent random weights to the edges of the graph. We also consider the graph distance on the dual map, and the first-passage percolation on the dual map with exponential edge weights, which is closely related to the so-called Eden model. In the latter two cases, we are able to compute explicitly the constant $𝐜$ by using earlier results about asymptotics for the peeling process. In general however, the constant $𝐜$ is obtained from a subadditivity argument in the infinite half-plane model that describes the asymptotic shape of the triangulation near the boundary of a large ball. Our results apply in particular to the infinite random triangulation known as the UIPT, and show that balls of the UIPT for the modified distance are asymptotically close to balls for the graph distance.

Ambjørn, J.; Budd, T. G. Multi-point functions of weighted cubic maps, Ann. Inst. Henri Poincaré D, Volume 3 (2016), pp. 1-44 (ISSN: 2308-5827) | DOI | Numdam | MR | Zbl

Addario-Berry, L.; Albenque, M. The scaling limit of random simple triangulations and random simple quadrangulations, Ann. Probab., Volume 45 (2017), pp. 2767-2825 (ISSN: 0091-1798) | DOI | MR | Zbl

Abraham, C. Rescaled bipartite planar maps converge to the Brownian map, Ann. Inst. Henri Poincaré Probab. Stat., Volume 52 (2016), pp. 575-595 (ISSN: 0246-0203) | DOI | MR | Zbl

Angel, O.; Curien, N. Percolations on random maps I: Half-plane models, Ann. Inst. Henri Poincaré Probab. Stat., Volume 51 (2015), pp. 405-431 (ISSN: 0246-0203) | DOI | Numdam | MR | Zbl

Auffinger, A.; Damron, M.; Hanson, J., University Lecture Series, 68, Amer. Math. Soc., 2017, 161 pages (ISBN: 978-1-4704-4183-8) | MR

Ambjørn, J.; Durhuus, B.; Jonsson, T., Cambridge Monographs on Mathematical Physics, Cambridge Univ. Press, 1997, 363 pages (ISBN: 0-521-46167-7) | DOI | MR | Zbl

Athreya, K. B.; Ney, P. E., Grundl. math. Wiss., 196, Springer, 1972, 287 pages | MR | Zbl

Angel, O. Scaling of percolation on infinite planar maps, I (preprint arXiv:math/0501006 )

Angel, O. Growth and percolation on the uniform infinite planar triangulation, Geom. Funct. Anal., Volume 13 (2003), pp. 935-974 (ISSN: 1016-443X) | DOI | MR | Zbl

Angel, O.; Schramm, O. Uniform infinite planar triangulations, Comm. Math. Phys., Volume 241 (2003), pp. 191-213 (ISSN: 0010-3616) | DOI | MR | Zbl

Bertoin, J.; Curien, N.; Kortchemski, I. Random planar maps and growth-fragmentations, Ann. Probab., Volume 46 (2018), pp. 207-260 (ISSN: 0091-1798) | DOI | MR | Zbl

Bettinelli, J.; Jacob, E.; Miermont, G. The scaling limit of uniform random plane maps, via the Ambjørn-Budd bijection, Electron. J. Probab., Volume 19 (2014) (ISSN: 1083-6489) | DOI | MR | Zbl

Budd, T. The peeling process of infinite Boltzmann planar maps, Electron. J. Combin., Volume 23 (2016) (ISSN: 1077-8926) | DOI | MR | Zbl

Caraceni, A.; Curien, N. Geometry of the uniform infinite half-planar quadrangulation, Random Structures Algorithms, Volume 52 (2018), pp. 454-494 (ISSN: 1042-9832) | DOI | MR | Zbl

Curien, N.; Le Gall, J.-F. The Brownian plane, J. Theoret. Probab., Volume 27 (2014), pp. 1249-1291 (ISSN: 0894-9840) | DOI | MR | Zbl

Curien, N.; Le Gall, J.-F. The hull process of the Brownian plane, Probab. Theory Related Fields, Volume 166 (2016), pp. 187-231 (ISSN: 0178-8051) | DOI | MR | Zbl

Curien, N.; Le Gall, J.-F. Scaling limits for the peeling process on random maps, Ann. Inst. Henri Poincaré Probab. Stat., Volume 53 (2017), pp. 322-357 (ISSN: 0246-0203) | DOI | MR | Zbl

Curien, N. A glimpse of the conformal structure of random planar maps, Comm. Math. Phys., Volume 333 (2015), pp. 1417-1463 (ISSN: 0010-3616) | DOI | MR | Zbl

Denisov, D.; Dieker, A. B.; Shneer, V. Large deviations for random walks under subexponentiality: the big-jump domain, Ann. Probab., Volume 36 (2008), pp. 1946-1991 (ISSN: 0091-1798) | DOI | MR | Zbl

Flajolet, P.; Sedgewick, R., Cambridge Univ. Press, 2009, 810 pages (ISBN: 978-0-521-89806-5) | DOI | MR | Zbl

Gill, J. T.; Rohde, S. On the Riemann surface type of random planar maps, Rev. Mat. Iberoam., Volume 29 (2013), pp. 1071-1090 (ISSN: 0213-2230) | DOI | MR | Zbl

Howard, C. D., Probability on discrete structures (Encyclopaedia Math. Sci.), Volume 110, Springer, 2004, pp. 125-173 | DOI | MR | Zbl

Krikun, M. Local structure of random quadrangulations (preprint arXiv:math/0512304 )

Krikun, M. A uniformly distributed infinite planar triangulation and a related branching process, J. Math. Sci., Volume 131 (2005), pp. 5520-5537 | Zbl

Krikun, M. Explicit enumeration of triangulations with multiple boundaries, Electron. J. Combin., Volume 14 (2007) http://www.combinatorics.org/Volume_14/Abstracts/v14i1r61.html (ISSN: 1077-8926) | DOI | MR | Zbl

Le Gall, J.-F. Uniqueness and universality of the Brownian map, Ann. Probab., Volume 41 (2013), pp. 2880-2960 (ISSN: 0091-1798) | DOI | MR | Zbl

Le Gall, J.-F. Random geometry on the sphere, Proceedings of the International Congress of Mathematicians—Seoul 2014. Vol. 1, Kyung Moon Sa (2014), pp. 421-442 | MR | Zbl

Liggett, T. M. An improved subadditive ergodic theorem, Ann. Probab., Volume 13 (1985), pp. 1279-1285 (ISSN: 0091-1798) | DOI | MR | Zbl

Lyons, R.; Pemantle, R.; Peres, Y. Conceptual proofs of $LlogL$ criteria for mean behavior of branching processes, Ann. Probab., Volume 23 (1995), pp. 1125-1138 (ISSN: 0091-1798) | DOI | MR | Zbl

Miermont, G. Aspects of random maps (lecture notes from the 2014 St-Flour Probability School http://perso.ens-lyon.fr/gregory.miermont/coursSaint-Flour.pdf )

Miermont, G. An invariance principle for random planar maps, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (2006), pp. 39-57 | MR | Zbl

Miermont, G. Tessellations of random maps of arbitrary genus, Ann. Sci. Éc. Norm. Supér., Volume 42 (2009), pp. 725-781 (ISSN: 0012-9593) | DOI | Numdam | MR | Zbl

Miermont, G. The Brownian map is the scaling limit of uniform random plane quadrangulations, Acta Math., Volume 210 (2013), pp. 319-401 (ISSN: 0001-5962) | DOI | MR | Zbl

Miller, J.; Sheffield, S. Quantum Loewner evolution, Duke Math. J., Volume 165 (2016), pp. 3241-3378 (ISSN: 0012-7094) | DOI | MR | Zbl

Miermont, G.; Weill, M. Radius and profile of random planar maps with faces of arbitrary degrees, Electron. J. Probab., Volume 13 (2008), pp. no. 4, 79-106 (ISSN: 1083-6489) | DOI | MR | Zbl

Stephenson, R. Local convergence of large critical multi-type Galton-Watson trees and applications to random maps, J. Theoret. Probab., Volume 31 (2018), pp. 159-205 (ISSN: 0894-9840) | DOI | MR | Zbl

Stufler, B. Scaling limits of random outerplanar maps with independent link-weights, Ann. Inst. Henri Poincaré Probab. Stat., Volume 53 (2017), pp. 900-915 (ISSN: 0246-0203) | DOI | MR | Zbl

Vahidi-Asl, M. Q.; Wierman, J. C., Random graphs, Vol. 2 (Poznań, 1989) (Wiley-Intersci. Publ.), Wiley, 1992, pp. 247-262 | MR | Zbl

van der Hofstadt, R. Random graphs and complex networks. II (2018) (preprint https://www.win.tue.nl/~rhofstad/NotesRGCNII.pdf )

Watabiki, Y. Construction of non-critical string field theory by transfer matrix formalism in dynamical triangulation, Nuclear Phys. B, Volume 441 (1995), pp. 119-163 (ISSN: 0550-3213) | DOI | MR | Zbl