Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 13 (2008) > Paper 56 open journal systems 


Some families of increasing planar maps

Jean-Francois Marckert, LaBRI, Université Bordeaux
Marie Albenque, LIAFA, Université Paris 7


Abstract
Stack-triangulations appear as natural objects when one wants to define some families of increasing triangulations by successive additions of faces. We investigate the asymptotic behavior of rooted stack-triangulations with 2n faces under two different distributions. We show that the uniform distribution on this set of maps converges, for a topology of local convergence, to a distribution on the set of infinite maps. In the other hand, we show that rescaled by n^{1/2}, they converge for the Gromov-Hausdorff topology on metric spaces to the continuum random tree introduced by Aldous. Under a distribution induced by a natural random construction, the distance between random points rescaled by (6/11)log n converge to 1 in probability. par We obtain similar asymptotic results for a family of increasing quadrangulations.


Full text: PDF

Pages: 1624-1671

Published on: September 19, 2008
Bibliography
  1. Aldous, David. The continuum random tree. II. An overview. Stochastic analysis (Durham, 1990), 23--70, London Math. Soc. Lecture Note Ser., 167, Cambridge Univ. Press, Cambridge, 1991. MR1166406 (93f:60010)
  2. Aldous, David. The continuum random tree. III. Ann. Probab. 21 (1993), no. 1, 248--289. MR1207226 (94c:60015)
  3. J.S. Andrade Jr, H.J. Herrmann, R.F.S. Andrade & L.R. da Silva (2005), Apollonian Networks: Simultaneously Scale-free, Small World, Euclidien, Space Filling, and with Matching graphs,
    Phys. Rev. Lett., 94, 018702 .
  4. Angel, O. Growth and percolation on the uniform infinite planar triangulation. Geom. Funct. Anal. 13 (2003), no. 5, 935--974. MR2024412 (2005b:60015)
  5. Angel, Omer; Schramm, Oded. Uniform infinite planar triangulations. Comm. Math. Phys. 241 (2003), no. 2-3, 191--213. MR2013797 (2005b:60021)
  6. F. Bergeron, P. Flajolet, B. Salvy. Varietes of increasing trees}, research report INRIA 1583, available at ftp://ftp.inria.fr/INRIA/publication/publi-ps-gz/RR/RR-1583.ps.gz
  7. O. Bernardi & N. Bonichon (2007), Catalan intervals and realizers of triangulations., to appear in J. of Comb. Theo. - Series A, ArXiv: math.CO/0704.3731. Extended abstract FPSAC 2007.
  8. Billingsley, Patrick. Convergence of probability measures. John Wiley & Sons, Inc., New York-London-Sydney 1968 xii+253 pp. MR0233396 (38 #1718)
  9. O. Bodini, A. Darrasse, & M. Soria (2008), Distances in random Apollonian network structures, 20th Annual international Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2008, DMTCS Proceedings, to appear.
  10. T. Böhme, M. Stiebitz & M. Voigt (1998), On Uniquely 4-Colorable Planar Graphs, url = citeseer.ist.psu.edu/110448.html
  11. 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)
  12. Broutin, N.; Devroye, L.; McLeish, E.; de la Salle, M. The height of increasing trees. Random Structures Algorithms 32 (2008), no. 4, 494--518. MR2422392
  13. 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 (2007m:60016)
  14. Chassaing, Philippe; Schaeffer, Gilles. Random planar lattices and integrated superBrownian excursion. Probab. Theory Related Fields 128 (2004), no. 2, 161--212. MR2031225 (2004k:60016)
  15. Cori, Robert; Vauquelin, Bernard. Planar maps are well labeled trees. Canad. J. Math. 33 (1981), no. 5, 1023--1042. MR0638363 (83c:05070)
  16. A. Darrasse & M. Soria, (2007), Degree distribution of RAN structures and Boltzmann generation for trees, International Conference on Analysis of Algorithms Antibes, June 2007,DIMACS Series in Discrete Mathematics and Theoretical Computer Science, p. 1-14 .
  17. Dong, Rui; Goldschmidt, Christina; Martin, James B. Coagulation-fragmentation duality, Poisson-Dirichlet distributions and random recursive trees. Ann. Appl. Probab. 16 (2006), no. 4, 1733--1750. MR2288702 (2007k:60232)
  18. 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)
  19. Evans, Steven N.; Pitman, Jim; Winter, Anita. Rayleigh processes, real trees, and root growth with re-grafting. Probab. Theory Related Fields 134 (2006), no. 1, 81--126. MR2221786 (2007d:60003)
  20. Feller, William. An introduction to probability theory and its applications. Vol. II. Second edition John Wiley & Sons, Inc., New York-London-Sydney 1971 xxiv+669 pp. MR0270403 (42 #5292)
  21. Felsner, Stefan; Zickfeld, Florian. On the number of planar orientations with prescribed degrees. Electron. J. Combin. 15 (2008), no. 1, Research Paper 77, 41 pp. MR2411454
  22. P. Flajolet, P. Dumas & V. Puyhaubert, (2006). Some exactly solvable models of urn process theory. Discrete Mathematics and Computer Science, vol. AG, 59-118.
  23. F. Gillet, (2003), Étude d'algorithmes stochastiques et arbres. PhD thesis manuscript.
  24. Gittenberger, Bernhard. A note on: ``State spaces of the snake and its tour---convergence of the discrete snake'' [J. Theoret. Probab. 16 (2003), no. 4, 1015--1046; MR2033196 (2005c:60095)] by J.-F. Marckert and A. Mokkadem. J. Theoret. Probab. 16 (2003), no. 4, 1063--1067 (2004). MR2033198 (2005h:60255)
  25. Graham, Ronald L.; Lagarias, Jeffrey C.; Mallows, Colin L.; Wilks, Allan R.; Yan, Catherine H. Apollonian circle packings: number theory. J. Number Theory 100 (2003), no. 1, 1--45. MR1971245 (2004d:11055)
  26. Janson, Svante. Limit theorems for triangular urn schemes. Probab. Theory Related Fields 134 (2006), no. 3, 417--452. MR2226887 (2007b:60051)
  27. Kallenberg, Olav. Foundations of modern probability. Second edition. Probability and its Applications (New York). Springer-Verlag, New York, 2002. xx+638 pp. ISBN: 0-387-95313-2 MR1876169 (2002m:60002)
  28. Krikun, M. A. A uniformly distributed infinite planar triangulation and a related branching process. (Russian) Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI) 307 (2004), Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 10, 141--174, 282--283; translation in J. Math. Sci. (N. Y.) 131 (2005), no. 2, 5520--5537 MR2050691 (2005m:60016)
  29. Kurtz, Thomas; Lyons, Russell; Pemantle, Robin; Peres, Yuval. A conceptual proof of the Kesten-Stigum theorem for multi-type branching processes. Classical and modern branching processes (Minneapolis, MN, 1994), 181--185, IMA Vol. Math. Appl., 84, Springer, New York, 1997. MR1601737 (98j:60122)
  30. Le Gall, Jean-François. Random trees and applications. Probab. Surv. 2 (2005), 245--311 (electronic). MR2203728 (2007h:60078)
  31. Le Gall, Jean-François. The topological structure of scaling limits of large planar maps. Invent. Math. 169 (2007), no. 3, 621--670. MR2336042 (2008i:60022)
  32. Le Gall, Jean-François; Weill, Mathilde. Conditioned Brownian trees. Ann. Inst. H. Poincaré Probab. Statist. 42 (2006), no. 4, 455--489. MR2242956 (2007k:60268)
  33. Lyons, Russell; Pemantle, Robin; Peres, Yuval. Conceptual proofs of $Llog L$ criteria for mean behavior of branching processes. Ann. Probab. 23 (1995), no. 3, 1125--1138. MR1349164 (96m:60194)
  34. Mahmoud, Hosam M.; Neininger, Ralph. Distribution of distances in random binary search trees. Ann. Appl. Probab. 13 (2003), no. 1, 253--276. MR1951999 (2003m:60022)
  35. Marckert, Jean-François. The lineage process in Galton-Watson trees and globally centered discrete snakes. Ann. Appl. Probab. 18 (2008), no. 1, 209--244. MR2380897 (Review)
  36. Marckert, Jean-François; Miermont, Grégory. Invariance principles for random bipartite planar maps. Ann. Probab. 35 (2007), no. 5, 1642--1705. MR2349571 (Review)
  37. Marckert, Jean-François; Mokkadem, Abdelkader. The depth first processes of Galton-Watson trees converge to the same Brownian excursion. Ann. Probab. 31 (2003), no. 3, 1655--1678. MR1989446 (2004g:60120)
  38. Marckert, Jean-François; Mokkadem, Abdelkader. Limit of normalized quadrangulations: the Brownian map. Ann. Probab. 34 (2006), no. 6, 2144--2202. MR2294979 (2007m:60092)
  39. G. Miermont, (2006). An invariance principle for random planar maps,
    Fourth Colloquium in Mathematics and Computer Sciences CMCS'06, DMTCS Proceedings AG, 39--58, Nancy.
  40. Miermont, Grégory; Weill, Mathilde. Radius and profile of random planar maps with faces of arbitrary degrees. Electron. J. Probab. 13 (2008), no. 4, 79--106. MR2375600 (Review)
  41. Pitman, J. Combinatorial stochastic processes. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7--24, 2002. With a foreword by Jean Picard. Lecture Notes in Mathematics, 1875. Springer-Verlag, Berlin, 2006. x+256 pp. ISBN: 978-3-540-30990-1; 3-540-30990-X MR2245368 (2008c:60001)
  42. G. Schaeffer, (1998). Conjugaison d'arbres et cartes combinatoires aléatoires., PhD Thesis, Université Bordeaux I.
  43. Weill, Mathilde. Asymptotics for rooted bipartite planar maps and scaling limits of two-type spatial trees. Electron. J. Probab. 12 (2007), no. 31, 887--925 (electronic). MR2318414 (Review)
  44. Z. Zhang, L. Rong, F. Comellas, (2006). High-dimensional random Apollonian networks, Physica A, Volume 364, p. 610-618.
  45. Z. Zhang, L. Chen, S. Zhou, L. Fang, J. Guan, Y. Zhang, (2007). Exact analytical solution of average path length for Apollonian networks, arXiv:0706.3491.
  46. T. Zhou, G. Yan & B.H. Wang (2005). Maximal planar networks with large clustering oefficient and power-law degree distribution, Phys. Rev. E 71, 046141.













Research
Support Tool
Capture Cite
View Metadata
Printer Friendly
Context
Author Address
Action
Email Author
Email Others


Home | Contents | Submissions, editors, etc. | Login | Search | ECP

Electronic Journal of Probability. ISSN: 1083-6489