Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 6 (2001) > Paper 23 open journal systems 


Recurrence of Distributional Limits of Finite Planar Graphs

Itai Benjamini, The Weizmann Institute of Science
Oded Schramm, Microsoft Research


Abstract
Suppose that Gj is a sequence of finite connected planar graphs, and in each Gj a special vertex, called the root, is chosen randomly-uniformly. We introduce the notion of a distributional limit G of such graphs. Assume that the vertex degrees of the vertices in Gj are bounded, and the bound does not depend on j. Then after passing to a subsequence, the limit exists, and is a random rooted graph G. We prove that with probability one G is recurrent. The proof involves the Circle Packing Theorem. The motivation for this work comes from the theory of random spherical triangulations.


Full text: PDF

Pages: 1-13

Published on: September 19, 2001
Bibliography
  1. Jan Ambjørn, Konstantinos N. Anagnostopoulos, Lars Jensen, Takashi Ichihara, and Yoshiyuki Watabiki. Quantum geometry and diffusion. J. High Energy Phys. 11 Paper 22, 16 pp. (electronic), 1998. MR 99m:83059
  2. Jan Ambjørn, Bergfinnur Durhuus, and Thordur Jonsson. Quantum geometry. Cambridge University Press, Cambridge, 1997. A statistical field theory approach. MR 98i:82001
  3. Jan Ambjørn, Jakob L. Nielsen, Juri Rolf, Dimitrij Boulatov, and Yoshiyuki Watabiki. The spectral dimension of 2D quantum gravity. J. High Energy Phys. 2 Paper 10, 8 pp. (electronic), 1998. MR 99c:83026
  4. L. Babai. The growth rate of vertex-transitive planar graphs. Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans, LA, 1997), pages 564--573, New York, 1997. ACM. MR 1447704
  5. Marcel Berger. Les placements de cercles. Pour la Science (French Scientific American), 176 , 1992.
  6. I. Benjamini, R. Lyons, Y. Peres, and O. Schramm. Group-invariant percolation on graphs. Geom. Funct. Anal. 9 (1):29--66, 1999. MR 99m:60149
  7. I. Benjamini and O. Schramm. Harmonic functions on planar and almost planar graphs and manifolds, via circle packings. Invent. Math. 126 565--587, 1996. MR 97k:31009
  8. Yves Colin de Verdière. Une principe variationnel pour les empilements de cercles. Inventiones Mathematicae, 104 655--669, 1991. MR 92h:57020
  9. Zhicheng Gao and Nicholas C. Wormald. The distribution of the maximum vertex degree in random planar maps. J. Combin. Theory Ser. A 89 (2):201--230, 2000. MR 2000m:05211
  10. Olle Häggström. Infinite clusters in dependent automorphism invariant percolation on trees. Ann. Probab. 25 (3):1423--1436, 1997. MR 98f:60207
  11. Zheng-Xu He and O. Schramm. Hyperbolic and parabolic packings. Discrete Comput. Geom. 14 (2):123--149, 1995. MR 96h:52017
  12. Johan Jonasson and Oded Schramm. On the cover time of planar graphs. Electron. Comm. Probab. 5 85--90, 2000. paper no. 10. MR 2001g:60170
  13. Koebe. Kontaktprobleme der Konformen Abbildung. Ber. Sächs. Akad. Wiss. Leipzig, Math.-Phys. Kl. 88 141--164, 1936.
  14. V. A. Malyshev. Probability related to quantum gravitation: planar gravitation. Uspekhi Mat. Nauk 54 (4(328)):3--46, 1999. MR 2000k:83024
  15. Gareth McCaughan. A recurrence/transience result for circle packings. Proc. Amer. Math. Soc. 126 (12):3647--3656, 1998. MR 99b:52041
  16. S. Malitz and A. Papakostas. On the angular resolution of planar graphs. SIAM J. Discrete Math. 7 172--183, 1994. MR 95c:05055
  17. Gary L. Miller and William Thurston. Separators in two and three dimensions. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, pages 300--309. ACM, Baltimore, May 1990.
  18. Burt Rodin and Dennis Sullivan. The convergence of circle packings to the Riemann mapping. J. Differential Geom. 26 (2):349--360, 1987. MR 90c:30007
  19. Horst Sachs. Coin graphs, polyhedra, and conformal mapping. Discrete Math. 134 133--138, 1994. MR 95j:52020
  20. Gilles Schaeffer. Random sampling of large planar maps and convex polyhedra. In Annual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), pages 760--769 (electronic). ACM, New York, 1999. MR 2001i:05142
  21. Kenneth Stephenson. Approximation of conformal structures via circle packing. In N. Papamichael, St. Ruscheweyh, and E. B. Saff, editors, Computational Methods and Function Theory 1997, Proceedings of the Third CMFT Conference 11 , pages 551--582. World Scientific, 1999. MR 2000h:30011
  22. Robin Thomas. Recent excluded minor theorems for graphs. In Surveys in combinatorics, 1999 (Canterbury), pages 201--222. Cambridge Univ. Press, Cambridge, 1999. MR 2001e:05118
  23. W. T. Tutte. A census of planar triangulations. Canad. J. Math. 14 21--38, 1962. MR 24:A695
















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