Abstract
We prove that any distributional limit of finite planar graphs in which the degree of the root has an exponential tail is almost surely recurrent. As a corollary, we obtain that the uniform infinite planar triangulation and quadrangulation (UIPT and UIPQ) are almost surely recurrent, resolving a conjecture of Angel, Benjamini and Schramm.
We also settle another related problem of Benjamini and Schramm. We show that in any bounded degree, finite planar graph the probability that the simple random walk started at a uniform random vertex avoids its initial location for $T$ steps is at most ${C \over \log T}$.
-
[AldLyo]
D. Aldous and R. Lyons, "Processes on unimodular random networks," Electron. J. Probab., vol. 12, pp. 1454-1508, 2007.@article {AldLyo, MRKEY = {2354165},
AUTHOR = {Aldous, David and Lyons, Russell},
TITLE = {Processes on unimodular random networks},
JOURNAL = {Electron. J. Probab.},
FJOURNAL = {Electronic Journal of Probability},
VOLUME = {12},
YEAR = {2007},
PAGES = {1454--1508},
ISSN = {1083-6489},
MRCLASS = {60C05 (05C80 60G50)},
MRNUMBER = {2354165},
MRREVIEWER = {Jean-Fran{ç}ois Delmas},
DOI = {10.1214/EJP.v12-463},
ZBLNUMBER = {1131.60003},
} -
[AldSte] D. Aldous and M. J. Steele, "The objective method: probabilistic combinatorial optimization and local weak convergence," in Probability on Discrete Structures, New York: Springer-Verlag, 2004, vol. 110, pp. 1-72.
@incollection {AldSte, MRKEY = {2023650},
AUTHOR = {Aldous, David and Steele, J. Michael},
TITLE = {The objective method: probabilistic combinatorial optimization and local weak convergence},
BOOKTITLE = {Probability on Discrete Structures},
SERIES = {Encyclopaedia Math. Sci.},
VOLUME = {110},
PAGES = {1--72},
PUBLISHER = {Springer-Verlag},
ADDRESS = {New York},
YEAR = {2004},
MRCLASS = {60C05 (05C80 60F05)},
MRNUMBER = {2023650},
MRREVIEWER = {Ralph Neininger},
ZBLNUMBER = {1037.60008},
} -
[ADJ] J. Ambjørn, B. Durhuus, and T. Jonsson, Quantum Geometry. A Statistical Field Theory Approach, Cambridge: Cambridge Univ. Press, 1997.
@book {ADJ, MRKEY = {1465433},
AUTHOR = {Ambjørn, Jan and Durhuus, Bergfinnur and Jonsson, Thordur},
TITLE = {Quantum Geometry. A Statistical Field Theory Approach},
SERIES = {Cambridge Monog. Math. Phys.},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {1997},
PAGES = {xiv+363},
ISBN = {0-521-46167-7},
MRCLASS = {82-02 (81T30 82B41 82B80 83C45)},
MRNUMBER = {1465433},
MRREVIEWER = {E. J. Janse van Rensburg},
DOI = {10.1017/CBO9780511524417},
ZBLNUMBER = {0993.82500},
} -
[A] O. Angel, "Growth and percolation on the uniform infinite planar triangulation," Geom. Funct. Anal., vol. 13, iss. 5, pp. 935-974, 2003.
@article {A, MRKEY = {2024412},
AUTHOR = {Angel, O.},
TITLE = {Growth and percolation on the uniform infinite planar triangulation},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {13},
YEAR = {2003},
NUMBER = {5},
PAGES = {935--974},
ISSN = {1016-443X},
CODEN = {GFANFB},
MRCLASS = {60C05 (52B70 60K35 81T25)},
MRNUMBER = {2024412},
MRREVIEWER = {Wolfgang Stadje},
DOI = {10.1007/s00039-003-0436-5},
ZBLNUMBER = {1039.60085},
} -
[AS] O. Angel and O. Schramm, "Uniform infinite planar triangulations," Comm. Math. Phys., vol. 241, iss. 2-3, pp. 191-213, 2003.
@article {AS, MRKEY = {2013797},
AUTHOR = {Angel, Omer and Schramm, Oded},
TITLE = {Uniform infinite planar triangulations},
JOURNAL = {Comm. Math. Phys.},
FJOURNAL = {Communications in Mathematical Physics},
VOLUME = {241},
YEAR = {2003},
NUMBER = {2-3},
PAGES = {191--213},
ISSN = {0010-3616},
CODEN = {CMPHAY},
MRCLASS = {60D05 (05C10 52B70 60F05 60K35 81T25 82B41 83C27)},
MRNUMBER = {2013797},
MRREVIEWER = {L. Bruce Richmond},
DOI = {10.1007/978-1-4419-9675-6_16},
ZBLNUMBER = {1098.60010},
} -
[BC2] I. and N. Curien, "Ergodic theory on stationary random graphs," Electron. J. Probab., vol. 17, pp. 1-20, 2012.
@article{BC2,
author={I.~Benjamini and N.~Curien},
TITLE={Ergodic theory on stationary random graphs},
JOURNAL = {Electron. J. Probab.},
VOLUME = {17},
PAGES={1--20},
YEAR={2012},
DOI={10.1214/EFP.v17-2401},
} -
[BC1] I. and N. Curien, Simple random walk on the uniform infinite planar quadrangulation: Subdiffusivity via pioneer points.
@misc{BC1,
author={I.~Benjamini and N.~Curien},
TITLE={Simple random walk on the uniform infinite planar quadrangulation: {S}ubdiffusivity via pioneer points},
NOTE={\emph{Geom. Funct. Anal.},
to appear},
SORTYEAR={2012},
ARXIV = {1202.5454},
} -
[BS2] I. Benjamini and O. Schramm, "Harmonic functions on planar and almost planar graphs and manifolds, via circle packings," Invent. Math., vol. 126, iss. 3, pp. 565-587, 1996.
@article {BS2, MRKEY = {1419007},
AUTHOR = {Benjamini, Itai and Schramm, Oded},
TITLE = {Harmonic functions on planar and almost planar graphs and manifolds, via circle packings},
JOURNAL = {Invent. Math.},
FJOURNAL = {Inventiones Mathematicae},
VOLUME = {126},
YEAR = {1996},
NUMBER = {3},
PAGES = {565--587},
ISSN = {0020-9910},
CODEN = {INVMBH},
MRCLASS = {31C20 (30F20 52C15)},
MRNUMBER = {1419007},
MRREVIEWER = {Sam Northshield},
DOI = {10.1007/s002220050109},
ZBLNUMBER = {0868.31008},
} -
[BS] I. Benjamini and O. Schramm, "Recurrence of distributional limits of finite planar graphs," Electron. J. Probab., vol. 6, p. 13, 2001.
@article {BS, MRKEY = {1873300},
AUTHOR = {Benjamini, Itai and Schramm, Oded},
TITLE = {Recurrence of distributional limits of finite planar graphs},
JOURNAL = {Electron. J. Probab.},
FJOURNAL = {Electronic Journal of Probability},
VOLUME = {6},
YEAR = {2001},
PAGES = {13 pp.},
ISSN = {1083-6489},
MRCLASS = {82B41 (05C80 52C26 60G50)},
MRNUMBER = {1873300},
MRREVIEWER = {Olle H{ä}ggstr{ö}m},
DOI = {10.1214/EJP.v6-96},
ZBLNUMBER = {1010.82021},
} -
[BCKL] C. Borgs, J. T. Chayes, J. Kahn, and L. Lovász, "Left and right convergence of graphs with bounded degree," Random Structures Algorithms, vol. 42, pp. 1-28, 2013.
@article{BCKL,
author = {Borgs, C. and Chayes, J. T. and Kahn, J. and Lov{á}sz, L.},
TITLE = {Left and right convergence of graphs with bounded degree},
JOURNAL = {Random Structures Algorithms},
VOLUME = {42},
PAGES = {1--28},
YEAR = {2013},
NOTE = {published online: 4 Apr 2012},
DOI = {10.1002/rsa.20414},
} -
[BCLSV] C. Borgs, J. T. Chayes, L. Lovász, V. T. Sós, and K. Vesztergombi, "Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing," Adv. Math., vol. 219, iss. 6, pp. 1801-1851, 2008.
@article {BCLSV, MRKEY = {2455626},
AUTHOR = {Borgs, C. and Chayes, J. T. and Lov{á}sz, L. and S{ó}s, V. T. and Vesztergombi, K.},
TITLE = {Convergent sequences of dense graphs. {I}. {S}ubgraph frequencies, metric properties and testing},
JOURNAL = {Adv. Math.},
FJOURNAL = {Advances in Mathematics},
VOLUME = {219},
YEAR = {2008},
NUMBER = {6},
PAGES = {1801--1851},
ISSN = {0001-8708},
CODEN = {ADMTA4},
MRCLASS = {05C80 (05C12 05C35 68R10)},
MRNUMBER = {2455626},
MRREVIEWER = {Michael Krivelevich},
DOI = {10.1016/j.aim.2008.07.008},
ZBLNUMBER = {1213.05161},
} -
[CS] P. Chassaing and G. Schaeffer, "Random planar lattices and integrated superBrownian excursion," Probab. Theory Related Fields, vol. 128, iss. 2, pp. 161-212, 2004.
@article {CS, MRKEY = {2031225},
AUTHOR = {Chassaing, Philippe and Schaeffer, Gilles},
TITLE = {Random planar lattices and integrated super{B}rownian excursion},
JOURNAL = {Probab. Theory Related Fields},
FJOURNAL = {Probability Theory and Related Fields},
VOLUME = {128},
YEAR = {2004},
NUMBER = {2},
PAGES = {161--212},
ISSN = {0178-8051},
CODEN = {PTRFEU},
MRCLASS = {60C05 (05C62 60G57 82B41)},
MRNUMBER = {2031225},
MRREVIEWER = {Ilya S. Molchanov},
DOI = {10.1007/s00440-003-0297-8},
ZBLNUMBER = {1041.60008},
} -
[CV] R. Cori and B. Vauquelin, "Planar maps are well labeled trees," Canad. J. Math., vol. 33, iss. 5, pp. 1023-1042, 1981.
@article {CV, MRKEY = {0638363},
AUTHOR = {Cori, Robert and Vauquelin, Bernard},
TITLE = {Planar maps are well labeled trees},
JOURNAL = {Canad. J. Math.},
FJOURNAL = {Canadian Journal of Mathematics. Journal Canadien de Mathématiques},
VOLUME = {33},
YEAR = {1981},
NUMBER = {5},
PAGES = {1023--1042},
ISSN = {0008-414X},
CODEN = {CJMAAB},
MRCLASS = {05C30 (05A05 05C05 05C10)},
MRNUMBER = {0638363},
MRREVIEWER = {W. T. Tutte},
DOI = {10.4153/CJM-1981-078-2},
ZBLNUMBER = {0415.05020},
} -
[CMM] N. Curien, L. Ménard, and G. Miermont, A view from infinity of the uniform infinite planar quadrangulation.
@misc{CMM,
author = {Curien, Nicolas and Ménard, L. and Miermont, Grégory},
TITLE = {A view from infinity of the uniform infinite planar quadrangulation},
NOTE = {preprint},
ARXIV = {1201.1052},
} -
[DS] B. Duplantier and S. Sheffield, "Liouville quantum gravity and KPZ," Invent. Math., vol. 185, iss. 2, pp. 333-393, 2011.
@article {DS, MRKEY = {2819163},
AUTHOR = {Duplantier, Bertrand and Sheffield, Scott},
TITLE = {Liouville quantum gravity and {KPZ}},
JOURNAL = {Invent. Math.},
FJOURNAL = {Inventiones Mathematicae},
VOLUME = {185},
YEAR = {2011},
NUMBER = {2},
PAGES = {333--393},
ISSN = {0020-9910},
CODEN = {INVMBH},
MRCLASS = {81T40 (60K35)},
MRNUMBER = {2819163},
MRREVIEWER = {Lee-Peng Teo},
DOI = {10.1007/s00222-010-0308-1},
ZBLNUMBER = {1226.81241},
} -
[GR] Z. Gao and B. L. Richmond, "Root vertex valency distributions of rooted maps and rooted triangulations," European J. Combin., vol. 15, iss. 5, pp. 483-490, 1994.
@article {GR, MRKEY = {1292958},
AUTHOR = {Gao, Zhicheng and Richmond, L. Bruce},
TITLE = {Root vertex valency distributions of rooted maps and rooted triangulations},
JOURNAL = {European J. Combin.},
FJOURNAL = {European Journal of Combinatorics},
VOLUME = {15},
YEAR = {1994},
NUMBER = {5},
PAGES = {483--490},
ISSN = {0195-6698},
MRCLASS = {05C30 (05C10)},
MRNUMBER = {1292958},
DOI = {10.1006/eujc.1994.1050},
ZBLNUMBER = {0807.05026},
} -
[RG] J. T. Gill and S. Rohde, On the Riemann surface type of Random Planar Maps.
@misc{RG,
author = {Gill, James T. and Rohde, Steffen},
TITLE = {On the {R}iemann surface type of Random Planar Maps},
NOTE={\emph{Rev. Mat. Iberoamericana},
to appear},
} -
[Krik] M. Krikun, Local structure of random quadrangulations.
@misc{Krik,
author = {Krikun, Maxim},
TITLE = {Local structure of random quadrangulations},
NOTE= {preprint}
} -
[Le2] J. Le Gall, Uniqueness and universality of the Brownian map.
@misc{Le2,
author = {Le Gall, Jean-Fran{ç}ois},
TITLE = {Uniqueness and universality of the {B}rownian map},
NOTE={\emph{Ann. Prob.},
to appear},
SORTYEAR={2012},
ARXIV = {1105.4842},
} -
[Le1] J. Le Gall, "The topological structure of scaling limits of large planar maps," Invent. Math., vol. 169, iss. 3, pp. 621-670, 2007.
@article {Le1, MRKEY = {2336042},
AUTHOR = {Le Gall, Jean-Fran{ç}ois},
TITLE = {The topological structure of scaling limits of large planar maps},
JOURNAL = {Invent. Math.},
FJOURNAL = {Inventiones Mathematicae},
VOLUME = {169},
YEAR = {2007},
NUMBER = {3},
PAGES = {621--670},
ISSN = {0020-9910},
CODEN = {INVMBH},
MRCLASS = {60D05 (60C05)},
MRNUMBER = {2336042},
MRREVIEWER = {Gr{é}gory Miermont},
DOI = {10.1007/s00222-007-0059-9},
ZBLNUMBER = {1132.60013},
} -
[LeM] J. Le Gall and G. Miermont, "Scaling limits of random trees and planar maps."
@article{LeM,
author = {Le Gall, Jean-Francois and Miermont, Gregory},
TITLE = {Scaling limits of random trees and planar maps},
NOTE = {Lecture notes for the Clay Mathematical Institute Summer School in Buzios, July 11 - August 7, 2010.}
} -
[LS] L. Lovász and B. Szegedy, "Limits of dense graph sequences," J. Combin. Theory Ser. B, vol. 96, iss. 6, pp. 933-957, 2006.
@article {LS, MRKEY = {2274085},
AUTHOR = {Lov{á}sz, L{á}szl{ó} and Szegedy, Bal{á}zs},
TITLE = {Limits of dense graph sequences},
JOURNAL = {J. Combin. Theory Ser. B},
FJOURNAL = {Journal of Combinatorial Theory. Series B},
VOLUME = {96},
YEAR = {2006},
NUMBER = {6},
PAGES = {933--957},
ISSN = {0095-8956},
CODEN = {JCBTB8},
MRCLASS = {05C35 (05C50 05C80)},
MRNUMBER = {2274085},
MRREVIEWER = {Yoshiharu Kohayakawa},
DOI = {10.1016/j.jctb.2006.05.002},
ZBLNUMBER = {1113.05092},
} -
[LP] R. Lyons and Y. Peres, Probability on Trees and Networks, Cambridge University Press.
@book{LP,
author = {R. Lyons and Y. Peres},
title = {Probability on Trees and Networks},
publisher = {Cambridge University Press},
date = {2008},
note = {in preparation},
URL={http://mypage.iu.edu/~rdlyons/prbtree/book.pdf},
} -
[MM] J. Marckert and A. Mokkadem, "Limit of normalized quadrangulations: the Brownian map," Ann. Probab., vol. 34, iss. 6, pp. 2144-2202, 2006.
@article {MM, MRKEY = {2294979},
AUTHOR = {Marckert, Jean-Fran{ç}ois and Mokkadem, Abdelkader},
TITLE = {Limit of normalized quadrangulations: the {B}rownian map},
JOURNAL = {Ann. Probab.},
FJOURNAL = {The Annals of Probability},
VOLUME = {34},
YEAR = {2006},
NUMBER = {6},
PAGES = {2144--2202},
ISSN = {0091-1798},
CODEN = {APBYAE},
MRCLASS = {60F99 (60C05 60F05 60K35)},
MRNUMBER = {2294979},
MRREVIEWER = {David J. Aldous},
DOI = {10.1214/009117906000000557},
ZBLNUMBER = {1117.60038},
} -
[Mier] G. Miermont, The Brownian map is the scaling limit of uniform random plane quadrangulations.
@misc{Mier,
author = {Miermont, Gregory},
TITLE = {The {B}rownian map is the scaling limit of uniform random plane quadrangulations},
NOTE = {\emph{Acta Math},
to appear},
ARXIV = {1104.1606},
} -
[RS] B. Rodin and D. Sullivan, "The convergence of circle packings to the Riemann mapping," J. Differential Geom., vol. 26, iss. 2, pp. 349-360, 1987.
@article {RS, MRKEY = {0906396},
AUTHOR = {Rodin, Burt and Sullivan, Dennis},
TITLE = {The convergence of circle packings to the {R}iemann mapping},
JOURNAL = {J. Differential Geom.},
FJOURNAL = {Journal of Differential Geometry},
VOLUME = {26},
YEAR = {1987},
NUMBER = {2},
PAGES = {349--360},
ISSN = {0022-040X},
CODEN = {JDGEAS},
MRCLASS = {30C35 (05B40 11H31 52A45 57N05)},
MRNUMBER = {0906396},
URL = {http://projecteuclid.org/euclid.jdg/1214441375},
ZBLNUMBER = {0694.30006},
} -
[R] S. Rohde, "Oded Schramm: from circle packing to SLE," Ann. Probab., vol. 39, iss. 5, pp. 1621-1667, 2011.
@article {R, MRKEY = {2884870},
AUTHOR = {Rohde, Steffen},
TITLE = {Oded {S}chramm: from circle packing to {SLE}},
JOURNAL = {Ann. Probab.},
FJOURNAL = {The Annals of Probability},
VOLUME = {39},
YEAR = {2011},
NUMBER = {5},
PAGES = {1621--1667},
ISSN = {0091-1798},
CODEN = {APBYAE},
MRCLASS = {60D05 (01A70 30C35 52C26 60J67)},
MRNUMBER = {2884870},
MRREVIEWER = {Andrew R. Wade},
DOI = {10.1007/978-1-4419-9675-6_1},
ZBLNUMBER = {1236.60004},
} -
[Sc] G. Schaeffer, Conjugaison d’arbres et cartes combinatoires aléatoires.
@misc{Sc,
author = {Schaeffer, Gilles},
TITLE = {Conjugaison d'arbres et cartes combinatoires aléatoires},
NOTE= {Ph.D. thesis, Université Bordeaux I, 1998}
} -
[St] K. Stephenson, Introduction to Circle Packing. The Theory of Discrete Analytic Functions, Cambridge: Cambridge Univ. Press, 2005.
@book {St, MRKEY = {2131318},
AUTHOR = {Stephenson, Kenneth},
TITLE = {Introduction to Circle Packing. The Theory of Discrete Analytic Functions},
PUBLISHER = {Cambridge Univ. Press},
ADDRESS = {Cambridge},
YEAR = {2005},
PAGES = {xii+356},
ISBN = {978-0-521-82356-2; 0-521-82356-0},
MRCLASS = {52C26 (30G25)},
MRNUMBER = {2131318},
MRREVIEWER = {Fr{é}d{é}ric Math{é}us},
ZBLNUMBER = {1074.52008},
} -
[T] W. T. Tutte, "A census of planar triangulations," Canad. J. Math., vol. 14, pp. 21-38, 1962.
@article {T, MRKEY = {0130841},
AUTHOR = {Tutte, W. T.},
TITLE = {A census of planar triangulations},
JOURNAL = {Canad. J. Math.},
FJOURNAL = {Canadian Journal of Mathematics. Journal Canadien de Mathématiques},
VOLUME = {14},
YEAR = {1962},
PAGES = {21--38},
ISSN = {0008-414X},
MRCLASS = {05.65 (52.45)},
MRNUMBER = {0130841},
MRREVIEWER = {G. de B. Robinson},
ZBLNUMBER = {0103.39603},
}
Full Article