 |
|
|
| | | | | |
|
|
|
|
|
Asymptotics for rooted bipartite planar maps and scaling limits of two-type spatial trees
|
Abstract
We prove some asymptotic results for the radius and the profile of large random bipartite planar maps. Using a bijection due to Bouttier, Di Francesco and Guitter between rooted bipartite planar maps and certain two-type trees with positive labels, we derive our results from a conditional limit theorem for two-type spatial trees. Finally we apply our estimates to separating vertices of bipartite planar maps: with probability close to one when n tends to infinity, a random 2k-angulation with n faces has a separating vertex whose removal disconnects the map into two components each with size greater that n1/2-ε.
|
Full text: PDF
Pages: 862-925
Published on: June 13, 2007
|
Bibliography
- Aldous, David. The continuum random tree. III. Ann. Probab. 21 (1993), no. 1, 248--289. MR1207226 (94c:60015)
- Banderier, Cyril; Flajolet, Philippe; Schaeffer, Gilles; Soria, Michèle. Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Analysis of algorithms (Krynica Morska, 2000). Random Structures Algorithms 19 (2001), no. 3-4, 194--246. MR1871555 (2002k:05012)
- Bouttier, J.; Di Francesco, P.; Guitter, E. Planar maps as labeled mobiles. Electron. J. Combin. 11 (2004), no. 1, Research Paper 69, 27 pp. (electronic). MR2097335 (2005i:05087)
- Chassaing, Philippe; Schaeffer, Gilles. Random planar lattices and integrated superBrownian excursion. Probab. Theory Related Fields 128 (2004), no. 2, 161--212. MR2031225 (2004k:60016)
- Cori, Robert; Vauquelin, Bernard. Planar maps are well labeled trees. Canad. J. Math. 33 (1981), no. 5, 1023--1042. MR0638363 (83c:05070)
- Drmota, Michael; Gittenberger, Bernhard. On the profile of random trees. Random Structures Algorithms 10 (1997), no. 4, 421--451. MR1608230 (99c:05176)
- Duquesne, Thomas. A limit theorem for the contour process of conditioned Galton-Watson trees. Ann. Probab. 31 (2003), no. 2, 996--1027. MR1964956 (2004a:60076)
- Duquesne, Thomas; Le Gall, Jean-François. Probabilistic and fractal aspects of Lévy trees. Probab. Theory Related Fields 131 (2005), no. 4, 553--603. MR2147221 (2006d:60123)
- Janson, Svante; Marckert, Jean-François. Convergence of discrete snakes. J. Theoret. Probab. 18 (2005), no. 3, 615--647. MR2167644 (2006g:60126)
- Le Gall, Jean-François. Spatial branching processes, random snakes and partial differential equations. Lectures in Mathematics ETH Zürich. Birkhäuser Verlag, Basel, 1999. x+163 pp. ISBN: 3-7643-6126-3 MR1714707 (2001g:60211)
- Le Gall, Jean-François. Random trees and applications. Probab. Surv. 2 (2005), 245--311 (electronic). MR2203728 (Review)
- Le Gall, Jean-François. A conditional limit theorem for tree-indexed random walk. Stochastic Process. Appl. 116 (2006), no. 4, 539--567. MR2205115 (2007g:60098)
- c Le Gall, J.F. (2006) The topological structure of scaling limits of large planar maps. arXiv: math.PR/0607567.
- Le Gall, Jean-Francois; Le Jan, Yves. Branching processes in Lévy processes: the exploration process. Ann. Probab. 26 (1998), no. 1, 213--252. MR1617047 (99d:60096)
- Le Gall, Jean-François; Weill, Mathilde. Conditioned Brownian trees. Ann. Inst. H. Poincaré Probab. Statist. 42 (2006), no. 4, 455--489. MR2242956
- Marckert, J.F., Miermont, G. (2006) Invariance principles for random bipartite planar maps. Ann.~Probab., to appear.
- Marckert, Jean-François; Mokkadem, Abdelkader. States spaces of the snake and its tour---convergence of the discrete snake. J. Theoret. Probab. 16 (2003), no. 4, 1015--1046 (2004). MR2033196 (2005c:60095)
- Marckert, Jean-François; Mokkadem, Abdelkader. Limit of normalized quadrangulations: the Brownian map. Ann. Probab. 34 (2006), no. 6, 2144--2202. MR2294979
- Schaeffer G. (1998) Conjugaison d'arbres et cartes aleatoires, These, Universite de Bordeaux I.
|
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|
Context