Recurrence of bipartite planar maps

Jakob Erik Björnberg (Uppsala University)
Sigurdur Örn Stefánsson (Uppsala University)


This paper concerns random bipartite planar maps which are defined by assigning weights to their faces. The paper presents a threefold contribution to the theory. Firstly, we prove the existence of the local limit for all choices of weights and describe it in terms of an infinite mobile. Secondly, we show that the local limit is in all cases almost surely recurrent.  And thirdly, we show that for certain choices of weights the local limit has exactly one face of infinite degree and has in that case spectral dimension 4/3 (the latter requires a mild moment condition).

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-40

Publication Date: March 12, 2014

DOI: 10.1214/EJP.v19-3102


  • Aldous, David; Pitman, Jim. Tree-valued Markov chains derived from Galton-Watson processes. Ann. Inst. H. Poincaré Probab. Statist. 34 (1998), no. 5, 637--686. MR1641670
  • S. Alexander and R. Orbach, Density of states on fractals: ''fractons'', J. Physique (Paris) Lett. 43 (1982), 625-631.
  • Angel, Omer; Schramm, Oded. Uniform infinite planar triangulations. Comm. Math. Phys. 241 (2003), no. 2-3, 191--213. MR2013797
  • Barlow, Martin T.; Kumagai, Takashi. Random walk on the incipient infinite cluster on trees. Illinois J. Math. 50 (2006), no. 1-4, ISBN: 0-9746986-1-X 33--65 (electronic). MR2247823
  • Berger, Noam. Transience, recurrence and critical behavior for long-range percolation. Comm. Math. Phys. 226 (2002), no. 3, 531--558. MR1896880
  • Benjamini, Itai; Schramm, Oded. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 (2001), no. 23, 13 pp. (electronic). MR1873300
  • J. Bettinelli, Scaling limit of random planar quadrangulations with a boundary. Ann. Inst. H. Poincaré Probab. Statist. (to appear)
  • Bouttier, J.; Di Francesco, P.; Guitter, E. Planar maps as labeled mobiles. Electron. J. Combin. 11 (2004), no. 1, Research Paper 69, 27 pp. MR2097335
  • Chassaing, Philippe; Durhuus, Bergfinnur. Local limit of labeled trees and expected volume growth in a random quadrangulation. Ann. Probab. 34 (2006), no. 3, 879--917. MR2243873
  • Curien, N.; Ménard, L.; Miermont, G. A view from infinity of the uniform infinite planar quadrangulation. ALEA Lat. Am. J. Probab. Math. Stat. 10 (2013), no. 1, 45--88. MR3083919
  • Durhuus, Bergfinnur; Jonsson, Thordur; Wheater, John F. The spectral dimension of generic trees. J. Stat. Phys. 128 (2007), no. 5, 1237--1260. MR2348795
  • Fujii, Ichiro; Kumagai, Takashi. Heat kernel estimates on the incipient infinite cluster for critical branching processes. Proceedings of RIMS Workshop on Stochastic Analysis and Applications, 85--95, RIMS Kôkyûroku Bessatsu, B6, Res. Inst. Math. Sci. (RIMS), Kyoto, 2008. MR2407556
  • Gurel-Gurevich, Ori; Nachmias, Asaf. Recurrence of planar graph limits. Ann. of Math. (2) 177 (2013), no. 2, 761--781. MR3010812
  • Gut, Allan. Stopped random walks. Limit theorems and applications. Second edition. Springer Series in Operations Research and Financial Engineering. Springer, New York, 2009. xiv+263 pp. ISBN: 978-0-387-87834-8 MR2489436
  • Janson, Svante; Jonsson, Thordur; Stefánsson, Sigurdur Örn. Random trees with superexponential branching weights. J. Phys. A 44 (2011), no. 48, 485002, 16 pp. MR2860856
  • Janson, Svante. Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. Probab. Surv. 9 (2012), 103--252. MR2908619
  • S. Janson and S. Ö. Stefánsson, Scaling limits of random planar maps with a unique large face. (To appear.) arXiv:1212.5072.
  • Jonsson, Thordur; Stefánsson, Sigurdur Örn. Condensation in nongeneric trees. J. Stat. Phys. 142 (2011), no. 2, 277--313. MR2764126
  • Kennedy, Douglas P. The Galton-Watson process conditioned on the total progeny. J. Appl. Probability 12 (1975), no. 4, 800--806. MR0386042
  • Kesten, Harry. Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 4, 425--487. MR0871905
  • Komlós, J.; Major, P.; Tusnády, G. An approximation of partial sums of independent ${\rm RV}$'s and the sample ${\rm DF}$. I. Z. Wahrscheinlichkeitstheorie und Verw. Gebiete 32 (1975), 111--131. MR0375412
  • Kozma, Gady; Nachmias, Asaf. The Alexander-Orbach conjecture holds in high dimensions. Invent. Math. 178 (2009), no. 3, 635--654. MR2551766
  • M. Krikun, Local structure of random quadrangulations. arXiv:0512304.
  • Kumagai, Takashi; Misumi, Jun. Heat kernel estimates for strongly recurrent random walk on random media. J. Theoret. Probab. 21 (2008), no. 4, 910--935. MR2443641
  • Le Gall, Jean-Francois; Miermont, Grégory. Scaling limits of random trees and planar maps. Probability and statistical physics in two and more dimensions, 155--211, Clay Math. Proc., 15, Amer. Math. Soc., Providence, RI, 2012. MR3025391
  • Le Gall, Jean-Francois. The topological structure of scaling limits of large planar maps. Invent. Math. 169 (2007), no. 3, 621--670. MR2336042
  • Le Gall, Jean-Francois; Miermont, Grégory. Scaling limits of random planar maps with large faces. Ann. Probab. 39 (2011), no. 1, 1--69. MR2778796
  • Le Gall, Jean-Francois. Uniqueness and universality of the Brownian map. Ann. Probab. 41 (2013), no. 4, 2880--2960. MR3112934
  • R. Lyons and Y. Peres, Probability on trees and networks. CUP, 2005.
  • Marckert, Jean-Francois; Miermont, Grégory. Invariance principles for random bipartite planar maps. Ann. Probab. 35 (2007), no. 5, 1642--1705. MR2349571
  • L. Ménard and P. Nolin, Percolation on uniform infinite planar maps, arXiv:1302.2851.
  • Miermont, Grégory. The Brownian map is the scaling limit of uniform random plane quadrangulations. Acta Math. 210 (2013), no. 2, 319--401. MR3070569
  • Miermont, Grégory. An invariance principle for random planar maps. Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities, 39--57, Discrete Math. Theor. Comput. Sci. Proc., AG, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2006. MR2509622
  • G. Schaeffer, Conjugaison d’arbres et cartes combinatoires aléatoires. Ph.D. thesis, Univ. Bordeaux I (1998).

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.