logo Journal de l'École Polytechnique
The mesoscopic geometry of sparse random maps
[La géométrie mésoscopique des cartes aléatoires clairsemées]
Nicolas Curien1 ; Igor Kortchemski2 ; Cyril Marzouk2
1 Département de Mathématique, Université Paris-Saclay, Faculté des Sciences d’Orsay Orsay, France
2 CNRS et Centre de Mathématiques Appliquées, École Polytechnique Palaiseau, France
Journal de l’École polytechnique — Mathématiques, Tome 9 (2022), pp. 1305-1345.

Nous étudions la structure de grandes cartes aléatoires choisies uniformément au hasard avec un nombre donné de sommets, d’arêtes et de faces et sur une surface de genre donné. Nous nous concentrons sur deux cas : le cas planaire et le cas unicellulaire, en faisant tendre les trois autres paramètres vers l’infini dans un régime clairsemé, dans lequel le rapport entre le nombre de sommets et d’arêtes tend vers 1. Si les deux cas semblent différents, ils peuvent être traités dans un cadre unifié en utilisant une version probabiliste de la décomposition classique en cœur-noyau. Dans les deux cas, nous identifions une échelle mésoscopique à laquelle les limites d’échelles de ces cartes s’obtiennent en prenant la limite locale de leur noyau (ou schéma) – qui est le dual de la Triangulation Planaire Infinie Uniforme dans le cas planaire et l’arbre infini 3-régulier dans le cas unicellulaire – et en remplaçant chaque arête par des arbres browniens indépendants (biaisés par la taille) avec deux points marqués.

We investigate the structure of large uniform random maps with a given number of vertices, edges, faces and on a surface of a given genus. We focus on two regimes: the planar case and the unicellular case, letting the three other parameters tend to infinity in a sparse regime, in which the ratio between the number of vertices and edges tends to 1. Albeit different at first sight, these two models can be treated in a unified way, using a probabilistic version of the classical core–kernel decomposition. In both cases, we identify a mesoscopic scale at which the scaling limits of these random maps can be obtained by first taking the local limit of their kernels (or scheme) – which turns out to be the dual of the Uniform Infinite Planar Triangulation in the planar case and the infinite three-regular tree in the unicellular case – and then replacing each edge by an independent (mass-biased) Brownian tree with two marked points.

Reçu le :
Accepté le :
Publié le :
DOI : 10.5802/jep.207
Classification : 05C80, 60D05, 05C07, 05C10, 60C05
Keywords: Random maps, intermediate scaling limits, kernel, drifted Brownian motion
Mot clés : Cartes aléatoires, limites d’échelle intermédiaire, noyau, mouvement brownien avec drift
Nicolas Curien 1 ; Igor Kortchemski 2 ; Cyril Marzouk 2

1 Département de Mathématique, Université Paris-Saclay, Faculté des Sciences d’Orsay Orsay, France
2 CNRS et Centre de Mathématiques Appliquées, École Polytechnique Palaiseau, France
Licence : CC-BY 4.0
Droits d'auteur : Les auteurs conservent leurs droits 
@article{JEP_2022__9__1305_0,
     author = {Nicolas Curien and Igor Kortchemski and Cyril Marzouk},
     title = {The mesoscopic geometry of sparse~random~maps},
     journal = {Journal de l{\textquoteright}\'Ecole polytechnique {\textemdash} Math\'ematiques},
     pages = {1305--1345},
     publisher = {\'Ecole polytechnique},
     volume = {9},
     year = {2022},
     doi = {10.5802/jep.207},
     language = {en},
     url = {https://jep.centre-mersenne.org/articles/10.5802/jep.207/}
}
TY  - JOUR
AU  - Nicolas Curien
AU  - Igor Kortchemski
AU  - Cyril Marzouk
TI  - The mesoscopic geometry of sparse random maps
JO  - Journal de l’École polytechnique — Mathématiques
PY  - 2022
SP  - 1305
EP  - 1345
VL  - 9
PB  - École polytechnique
UR  - https://jep.centre-mersenne.org/articles/10.5802/jep.207/
DO  - 10.5802/jep.207
LA  - en
ID  - JEP_2022__9__1305_0
ER  - 
%0 Journal Article
%A Nicolas Curien
%A Igor Kortchemski
%A Cyril Marzouk
%T The mesoscopic geometry of sparse random maps
%J Journal de l’École polytechnique — Mathématiques
%D 2022
%P 1305-1345
%V 9
%I École polytechnique
%U https://jep.centre-mersenne.org/articles/10.5802/jep.207/
%R 10.5802/jep.207
%G en
%F JEP_2022__9__1305_0
Nicolas Curien; Igor Kortchemski; Cyril Marzouk. The mesoscopic geometry of sparse random maps. Journal de l’École polytechnique — Mathématiques, Tome 9 (2022), pp. 1305-1345. doi : 10.5802/jep.207. https://jep.centre-mersenne.org/articles/10.5802/jep.207/

[ABA21] L. Addario-Berry & M. Albenque - “Convergence of non-bipartite maps via symmetrization of labeled trees”, Ann. H. Lebesgue 4 (2021), p. 653-683 | DOI | MR | Zbl

[ABBG10] L. Addario-Berry, N. Broutin & C. Goldschmidt - “Critical random graphs: limiting constructions and distributional properties”, Electron. J. Probab. 15 (2010), p. 741-775 | DOI | MR | Zbl

[ACCR13] O. Angel, G. Chapuy, N. Curien & G. Ray - “The local limit of unicellular maps in high genus”, Electron. Comm. Probab. 18 (2013), article ID 86, 8 pages | DOI | MR | Zbl

[Ald85] D. Aldous - “Exchangeability and related topics”, in École d’été de probabilités de Saint-Flour, XIII – 1983, Lect. Notes in Math., vol. 1117, Springer, Berlin, 1985, p. 1-198 | DOI | MR | Zbl

[Ald91] D. Aldous - “The continuum random tree II: An overview”, in Stochastic analysis (Durham, 1990), London Math. Soc. Lecture Note Ser., vol. 167, Cambridge University Press, Cambridge, 1991, p. 23-70 | DOI | MR | Zbl

[AS03] O. Angel & O. Schramm - “Uniform infinite planar triangulations”, Comm. Math. Phys. 241 (2003) no. 2-3, p. 191-213 | DOI | MR | Zbl

[BBI01] D. Burago, Y. Burago & S. Ivanov - A course in metric geometry, Graduate Studies in Math., vol. 33, American Mathematical Society, Providence, RI, 2001

[BCR93] E. Bender, R. Canfield & B. Richmond - “The asymptotic number of rooted maps on a surface. II: Enumeration by vertices and faces”, J. Combin. Theory Ser. A 63 (1993) no. 2, p. 318-329 | DOI | MR | Zbl

[BJM14] J. Bettinelli, E. Jacob & G. Miermont - “The scaling limit of uniform random plane maps, via the Ambjørn-Budd bijection”, Electron. J. Probab. 19 (2014), article ID 74, 16 pages | DOI | Zbl

[BL21] T. Budzinski & B. Louf - “Local limits of uniform triangulations in high genus”, Invent. Math. 223 (2021) no. 1, p. 1-47 | DOI | MR | Zbl

[BL22] T. Budzinski & B. Louf - “Local limits of bipartite maps with prescribed face degrees in high genus”, Ann. Probab. 50 (2022) no. 3, p. 1059-1126 | DOI | MR | Zbl

[BMR19] E. Baur, G. Miermont & G. Ray - “Classification of scaling limits of uniform quadrangulations with a boundary”, Ann. Probab. 47 (2019) no. 6, p. 3397-3477 | MR | Zbl

[Bud21] T. Budzinski - “Multi-ended Markovian triangulations and robust convergence to the UIPT”, 2021 | arXiv

[Cha10] G. Chapuy - “The structure of unicellular maps, and a connection between maps of positive genus and planar labelled trees”, Probab. Theory Related Fields 147 (2010) no. 3-4, p. 415-447 | DOI | MR | Zbl

[CLG14] N. Curien & J.-F. Le Gall - “The Brownian plane”, J. Theoret. Probab. 27 (2014) no. 4, p. 1249-1291 | DOI | MR | Zbl

[CLG19] N. Curien & J.-F. Le Gall - “First-passage percolation and local modifications of distances in random triangulations”, Ann. Sci. École Norm. Sup. (4) 52 (2019) no. 3, p. 631-701 | DOI | MR | Zbl

[CMS09] G. Chapuy, M. Marcus & G. Schaeffer - “A bijection for rooted maps on orientable surfaces”, SIAM J. Discrete Math. 23 (2009) no. 3, p. 1587-1611 | DOI | MR | Zbl

[Cur16] N. Curien - “Planar stochastic hyperbolic triangulations”, Probab. Theory Related Fields 165 (2016) no. 3-4, p. 509-540 | DOI | MR | Zbl

[DLG05] T. Duquesne & J.-F. Le Gall - “Probabilistic and fractal aspects of Lévy trees”, Probab. Theory Related Fields 131 (2005) no. 4, p. 553-603 | DOI | Zbl

[FG14] É. Fusy & E. Guitter - “The three-point function of general planar maps”, J. Stat. Mech. Theory Exp. 2014 (2014) no. 9, p. 39 | DOI | MR | Zbl

[Jan05] K. M. Jansons - “Brownian excursion with a single mark”, Proc. Roy. Soc. London Ser. A 461 (2005) no. 2064, p. 3705-3709 | DOI | MR | Zbl

[Jan12] S. Janson - “Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation”, Probab. Surv. 9 (2012), p. 103-252 | DOI | MR | Zbl

[JKŁP93] S. Janson, D. E. Knuth, T. Łuczak & B. Pittel - “The birth of the giant component”, Random Structures Algorithms 4 (1993) no. 3, p. 233-358 | DOI | MR | Zbl

[JL21] S. Janson & B. Louf - “Unicellular maps vs hyperbolic surfaces in large genus: simple closed curves”, 2021 | arXiv

[JL22] S. Janson & B. Louf - “Short cycles in high genus unicellular maps”, Ann. Inst. H. Poincaré Probab. Statist. 58 (2022) no. 3, p. 1547-1564 | DOI | MR | Zbl

[Kal02] O. Kallenberg - Foundations of modern probability, Probability and its Appl., Springer-Verlag, New York, 2002 | DOI

[KM21a] M. Kang & M. Missethan - “Local limit of sparse random planar graphs”, 2021 | arXiv

[KM21b] I. Kortchemski & C. Marzouk - “Large deviation local limit theorems and limits of biconditioned trees and maps”, 2021 | arXiv

[Kri07] M. Krikun - “Explicit enumeration of triangulations with multiple boundaries”, Electron. J. Combin. 14 (2007) no. 1, article ID 61, 14 pages | MR | Zbl

[LG10] J.-F. Le Gall - “Itô’s excursion theory and random trees”, Stochastic Processes Appl. 120 (2010) no. 5, p. 721-749 | DOI | Zbl

[LG13] J.-F. Le Gall - “Uniqueness and universality of the Brownian map”, Ann. Probab. 41 (2013) no. 4, p. 2880-2960 | DOI | MR | Zbl

[Lou21] B. Louf - “Large expanders in high genus unicellular maps”, 2021 | arXiv

[Mar22] C. Marzouk - “Scaling limits of random looptrees and bipartite plane maps with prescribed large faces”, 2022 | arXiv

[Mie13] G. Miermont - “The Brownian map is the scaling limit of uniform random plane quadrangulations”, Acta Math. 210 (2013) no. 2, p. 319-401 | DOI | MR | Zbl

[MNS70] R. C. Mullin, E. Nemeth & P. J. Schellenberg - “The enumeration of almost cubic maps”, in Proc. Louisiana Conf. on Combinatorics, Graph Theory and Computing, Louisiana State Univ., Baton Rouge, La., 1970, p. 281-295 | Zbl

[MP19] M. Mirzakhani & B. Petri - “Lengths of closed geodesics on random surfaces of large genus”, Comment. Math. Helv. 94 (2019) no. 4, p. 869-889 | DOI | MR | Zbl

[Mug19] D. Mugnolo - “What is actually a metric graph?”, 2019 | arXiv

[NR18] M. Noy & L. Ramos - “Random planar maps and graphs with minimum degree two and three”, Electron. J. Combin. 25 (2018) no. 4, article ID P4.5, 38 pages | DOI | MR | Zbl

[NRR15] M. Noy, V. Ravelomanana & J. Rué - “On the probability of planarity of a random graph near the critical point”, Proc. Amer. Math. Soc. 143 (2015) no. 3, p. 925-936 | MR | Zbl

[Pit06] J. Pitman - “Combinatorial stochastic processes”, in École d’été de probabilités de Saint-Flour, XXXII – 2002, Lect. Notes in Math., vol. 1875, Springer-Verlag, Berlin, 2006, p. 1-251 | DOI | MR | Zbl

[Ray15] G. Ray - “Large unicellular maps in high genus”, Ann. Inst. H. Poincaré Probab. Statist. 51 (2015) no. 4, p. 1432-1456 | DOI | Numdam | MR | Zbl

[RY99] D. Revuz & M. Yor - Continuous martingales and Brownian motion, Grundlehren Math. Wiss., vol. 293, Springer-Verlag, Berlin, 1999 | DOI

[Ste18] R. Stephenson - “Local convergence of large critical multi-type Galton-Watson trees and applications to random maps”, J. Theoret. Probab. 31 (2018) no. 1, p. 159-205 | DOI | MR | Zbl

[WL72] T. R. S. Walsh & A. B. Lehman - “Counting rooted maps by genus. I”, J. Combin. Theory Ser. B 13 (1972), p. 192-218 | DOI | Zbl

[Wor99] N. C. Wormald - “Models of random regular graphs”, in Surveys in combinatorics, 1999, Cambridge University Press, 1999, p. 239-298 | DOI | Zbl

[Łu91] T. Łuczak - “Cycles in a random graph near the critical point”, Random Structures Algorithms 2 (1991) no. 4, p. 421-439 | DOI | MR | Zbl

Cité par Sources :