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

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

doi:10.24033/asens.2394

Geodesic

Parcourir par

First-passage percolation and local modifications of distances in random triangulations
[Percolation de premier passage et perturbations locales des distances dans les triangulations aléatoires]

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.

Voir la notice de l'article provenant de la source Numdam

Abstract (VO)
Résumé

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.

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.

MR Zbl

DOI : 10.24033/asens.2394

Classification : 05C80; 60K35.
Keywords: Random planar maps, Brownian map, UIPT, peeling process, first-passage percolation, Eden model.
Mots-clés : Cartes planaires aléatoires, Carte brownienne, UIPT, processus d'épluchage, percolation de premier passage, modèle d'Eden.

@article{ASENS_2019__52_3_631_0,
     author = {Curien, Nicolas and Le Gall, Jean-Fran\c{c}ois},
     title = {First-passage percolation  and local modifications  of distances in random triangulations},
     journal = {Annales scientifiques de l'\'Ecole Normale Sup\'erieure},
     pages = {631--701},
     publisher = {Soci\'et\'e Math\'ematique de France. Tous droits r\'eserv\'es},
     volume = {Ser. 4, 52},
     number = {3},
     year = {2019},
     doi = {10.24033/asens.2394},
     mrnumber = {3982872},
     zbl = {1429.05188},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.24033/asens.2394/}
}

TY  - JOUR
AU  - Curien, Nicolas
AU  - Le Gall, Jean-François
TI  - First-passage percolation  and local modifications  of distances in random triangulations
JO  - Annales scientifiques de l'École Normale Supérieure
PY  - 2019
SP  - 631
EP  - 701
VL  - 52
IS  - 3
PB  - Société Mathématique de France. Tous droits réservés
UR  - http://geodesic.mathdoc.fr/articles/10.24033/asens.2394/
DO  - 10.24033/asens.2394
LA  - en
ID  - ASENS_2019__52_3_631_0
ER  -

%0 Journal Article
%A Curien, Nicolas
%A Le Gall, Jean-François
%T First-passage percolation  and local modifications  of distances in random triangulations
%J Annales scientifiques de l'École Normale Supérieure
%D 2019
%P 631-701
%V 52
%N 3
%I Société Mathématique de France. Tous droits réservés
%U http://geodesic.mathdoc.fr/articles/10.24033/asens.2394/
%R 10.24033/asens.2394
%G en
%F ASENS_2019__52_3_631_0

Curien, Nicolas; Le Gall, Jean-François. First-passage percolation  and local modifications  of distances in random triangulations. Annales scientifiques de l'École Normale Supérieure, Série 4, Tome 52 (2019) no. 3, pp. 631-701. doi : 10.24033/asens.2394. http://geodesic.mathdoc.fr/articles/10.24033/asens.2394/

Bibliographie
Cité par

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) | MR | Zbl | mathdoc-id | DOI

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) | MR | Zbl | DOI

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) | MR | Zbl | DOI

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) | MR | Zbl | mathdoc-id | DOI

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) | MR | Zbl | DOI

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) | MR | Zbl | DOI

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

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

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) | MR | Zbl | DOI

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

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

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

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) | MR | Zbl | DOI

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) | MR | Zbl | DOI

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

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) | MR | Zbl | DOI

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

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) | MR | Zbl | DOI

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

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/... (ISSN: 1077-8926) | MR | Zbl | DOI

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

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) | MR | Zbl | DOI

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

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) | MR | Zbl | mathdoc-id | DOI

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) | MR | Zbl | DOI

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

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) | MR | Zbl | DOI

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) | MR | Zbl | DOI

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) | MR | Zbl | DOI

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) | MR | Zbl | DOI

Cité par Sources :