Ergodic theory on stationary random graphs

Itai Benjamini (Weizmann institute of science)
Nicolas Curien (ÉNS Paris)

Abstract


A stationary random graph is a random rooted graph whose distribution is invariant under re-rooting along the simple random walk. We adapt the entropy technique developed for Cayley graphs and show in particular that stationary random graphs of subexponential growth are almost surely Liouville, that is, admit no non constant bounded harmonic functions. Applications include the uniform infinite planar quadrangulation and  long-range percolation clusters.

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

Pages: 1-20

Publication Date: October 29, 2012

DOI: 10.1214/EJP.v17-2401

References

  • Alcalde Cuesta, Fernando; Fernández de Córdoba, María P. Nombre de branchement d'un pseudogroupe. (French) [Number of branchings of a pseudogroup] Monatsh. Math. 163 (2011), no. 4, 389--414. MR2820370
  • Aldous, David; Lyons, Russell. Processes on unimodular random networks. Electron. J. Probab. 12 (2007), no. 54, 1454--1508. MR2354165
  • Angel, O. Growth and percolation on the uniform infinite planar triangulation. Geom. Funct. Anal. 13 (2003), no. 5, 935--974. MR2024412
  • Angel, Omer; Schramm, Oded. Uniform infinite planar triangulations. Comm. Math. Phys. 241 (2003), no. 2-3, 191--213. MR2013797
  • Avez, André. Théorème de Choquet-Deny pour les groupes à croissance non exponentielle. (French) C. R. Acad. Sci. Paris Sér. A 279 (1974), 25--28. MR0353405
  • Benjamini, Itai; Curien, Nicolas. On limits of graphs sphere packed in Euclidean space and applications. European J. Combin. 32 (2011), no. 7, 975--984. MR2825530
  • Benjamini, Itai; Curien, Nicolas. Recurrence of the $\Bbb Z^ d$-valued infinite snake via unimodularity. Electron. Commun. Probab. 17 (2012), no. 1, 10 pp. MR2872570
  • Benjamini, I.; Lyons, R.; Peres, Y.; Schramm, O. Group-invariant percolation on graphs. Geom. Funct. Anal. 9 (1999), no. 1, 29--66. MR1675890
  • Benjamini, Itai; Schramm, Oded. Harmonic functions on planar and almost planar graphs and manifolds, via circle packings. Invent. Math. 126 (1996), no. 3, 565--587. MR1419007
  • Benjamini, Itai; Schramm, Oded. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 (2001), no. 23, 13 pp. (electronic). MR1873300
  • Berger, Noam. Transience, recurrence and critical behavior for long-range percolation. Comm. Math. Phys. 226 (2002), no. 3, 531--558. MR1896880
  • Biskup, Marek. Graph diameter in long-range percolation. Random Structures Algorithms 39 (2011), no. 2, 210--227. MR2850269
  • L. Bowen. Random walks on coset spaces with applications to Furstenberg entropy. preprint available on arxiv.
  • 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
  • N. Curien, L. Ménard, and G. Miermont. A view from infinity of the uniform infinite planar quadrangulation. arXiv:1201.1052.
  • Derriennic, Yves. Quelques applications du théorème ergodique sous-additif. (French) Conference on Random Walks (Kleebach, 1979) (French), pp. 183--201, 4, Astérisque, 74, Soc. Math. France, Paris, 1980. MR0588163
  • Feldman, Jacob; Moore, Calvin C. Ergodic equivalence relations, cohomology, and von Neumann algebras. I. Trans. Amer. Math. Soc. 234 (1977), no. 2, 289--324. MR0578656
  • Gaboriau, D. Invariant percolation and harmonic Dirichlet functions. Geom. Funct. Anal. 15 (2005), no. 5, 1004--1051. MR2221157
  • J. T. Gill and S. Rohde. On the Riemann surface type of random planar maps. arXiv:1101.1320.
  • Guivarc'h, Y. Sur la loi des grands nombres et le rayon spectral d'une marche aléatoire. (French) Conference on Random Walks (Kleebach, 1979) (French), pp. 47--98, 3, Astérisque, 74, Soc. Math. France, Paris, 1980. MR0588157
  • O. Gurel-Gurevich and A. Nachmias. Recurrence of planar graph limits. Ann. Maths (to appear), 2012.
  • Häggström, Olle. Infinite clusters in dependent automorphism invariant percolation on trees. Ann. Probab. 25 (1997), no. 3, 1423--1436. MR1457624
  • Ka?manovich, V. A. Brownian motion on foliations: entropy, invariant measures, mixing. (Russian) Funktsional. Anal. i Prilozhen. 22 (1988), no. 4, 82--83; translation in Funct. Anal. Appl. 22 (1988), no. 4, 326--328 (1989) MR0977003
  • Ka?manovich, V. A. Boundary and entropy of random walks in random environment. Probability theory and mathematical statistics, Vol. I (Vilnius, 1989), 573--579, "Mokslas'', Vilnius, 1990. MR1153846
  • Kaimanovich, Vadim A. Hausdorff dimension of the harmonic measure on trees. Ergodic Theory Dynam. Systems 18 (1998), no. 3, 631--660. MR1631732
  • Kaimanovich, Vadim A. Random walks on Sierpi?ski graphs: hyperbolicity and stochastic homogenization. Fractals in Graz 2001, 145--183, Trends Math., Birkhäuser, Basel, 2003. MR2091703
  • Kaimanovich, V. A.; Kifer, Y.; Rubshtein, B.-Z. Boundaries and harmonic functions for random walks with random transition probabilities. J. Theoret. Probab. 17 (2004), no. 3, 605--646. MR2091553
  • Kaimanovich, Vadim A.; Sobieczky, Florian. Stochastic homogenization of horospheric tree products. Probabilistic approach to geometry, 199--229, Adv. Stud. Pure Math., 57, Math. Soc. Japan, Tokyo, 2010. MR2648261
  • Ka?manovich, V. A.; Vershik, A. M. Random walks on discrete groups: boundary and entropy. Ann. Probab. 11 (1983), no. 3, 457--490. MR0704539
  • Kaimanovich, Vadim A.; Woess, Wolfgang. Boundary and entropy of space homogeneous Markov chains. Ann. Probab. 30 (2002), no. 1, 323--363. MR1894110
  • Kesten, Harry. Subdiffusive behavior of random walk on a random cluster. Ann. Inst. H. Poincaré Probab. Statist. 22 (1986), no. 4, 425--487. MR0871905
  • M. Krikun. Local structure of random quadrangulations. arXiv:0512304.
  • Le Gall, Jean-François. Large random planar maps and their scaling limits. European Congress of Mathematics, 253--276, Eur. Math. Soc., Zürich, 2010. MR2648329
  • Lyons, Russell; Pemantle, Robin; Peres, Yuval. Ergodic theory on Galton-Watson trees: speed of random walk and dimension of harmonic measure. Ergodic Theory Dynam. Systems 15 (1995), no. 3, 593--619. MR1336708
  • R. Lyons and Y. Peres. Probability on Trees and Networks. Current version available at http://mypage.iu.edu/~rdlyons/, In preparation.
  • Ménard, Laurent. The two uniform infinite quadrangulations of the plane have the same law. Ann. Inst. Henri Poincaré Probab. Stat. 46 (2010), no. 1, 190--208. MR2641776
  • Paulin, F. Propriétés asymptotiques des relations d'équivalences mesurées discrètes. (French) [Asymptotic properties of discrete measured equivalence relations] Markov Process. Related Fields 5 (1999), no. 2, 163--200. MR1762172
  • Soardi, Paolo M.; Woess, Wolfgang. Amenability, unimodularity, and the spectral radius of random walks on infinite graphs. Math. Z. 205 (1990), no. 3, 471--486. MR1082868
Bookmark and Share


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