Invariance, quasi-invariance and unimodularity for random graphs

V. A. Kaimanovich

Zapiski Nauchnykh Seminarov POMI, Probability and statistics. Part 22, Tome 441 (2015), pp. 210-238

Résumé

We interpret the probabilistic notion of unimodularity for measures on the space of rooted locally finite connected graphs in terms of the theory of measured equivalence relations. It turns out that the right framework for this consists in considering quasi-invariant (rather than just invariant) measures with respect to the root moving equivalence relation. We define a natural modular cocycle of this equivalence relation, and show that unimodular measures are precisely those quasi-invariant measures whose Radon–Nikodym cocycle coincides with the modular cocycle. This embeds the notion of unimodularity into the very general dynamical scheme of constructing and studying measures with a prescribed Radon–Nikodym cocycle.

Bibliographie

[1] D. Aldous, R. Lyons, “Processes on unimodular random networks”, Electron. J. Probab., 12:54 (2007), 1454–1508, (electronic) | MR | Zbl

[2] D. Aldous, J. M. Steele, “The objective method: probabilistic combinatorial optimization and local weak convergence”, Probability on discrete structures, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004, 1–72 | MR | Zbl

[3] M. Aizenman, S. Warzel, “The canopy graph and level statistics for random operators on trees”, Math. Phys. Anal. Geom., 9:4 (2006), 291–333 (2007) | DOI | MR | Zbl

[4] I. Benjamini, N. Curien, “Ergodic theory on stationary random graphs”, Electron. J. Probab., 17:93 (2012), 20 pp., (electronic) | MR

[5] H. Bass, A. Lubotzky, Tree Lattices, With appendices by H. Bass, L. Carbone, A. Lubotzky, G. Rosenberg and J. Tits, Progress in Mathematics, 176, Birkhäuser Boston, Inc., Boston, MA, 2001 | MR | Zbl

[6] I. Benjamini, R. Lyons, Y. Peres, O. Schramm, “Group-invariant percolation on graphs”, Geom. Funct. Anal., 9:1 (1999), 29–66 | DOI | MR | Zbl

[7] I. Benjamini, R. Lyons, O. Schramm, “Unimodular random trees”, Ergodic Theory Dynam. Systems, 35:2 (2015), 359–373 | DOI | MR | Zbl

[8] R. Bowen, Equilibrium states and the ergodic theory of Anosov diffeomorphisms, Lecture Notes in Mathematics, 470, Springer, Berlin–New York, 1975 | MR | Zbl

[9] I. Benjamini, O. Schramm, “Recurrence of distributional limits of finite planar graphs”, Electron. J. Probab., 6:23 (2001), 13 pp., (electronic) | MR | Zbl

[10] L. Carbone, Non-uniform lattices on uniform trees, Mem. Amer. Math. Soc., 152, no. 724, 2001, xii+127 pp. | MR

[11] D. I. Cartwright, V. A. Kaimanovich, W. Woess, “Random walks on the affine group of local fields and of homogeneous trees”, Ann. Inst. Fourier (Grenoble), 44:4 (1994), 1243–1288 | DOI | MR | Zbl

[12] L. Carbone, G. Rosenberg, “Lattices on nonuniform trees”, Geom. Dedicata, 98 (2003), 161–188 | DOI | MR | Zbl

[13] J. Feldman, C. C. Moore, “Ergodic equivalence relations, cohomology, and von Neumann algebras I”, Trans. Amer. Math. Soc., 234:2 (1977), 289–324 | DOI | MR | Zbl

[14] L. Garnett, “Foliations, the ergodic theorem and Brownian motion”, J. Funct. Anal., 51:3 (1983), 285–311 | DOI | MR | Zbl

[15] O. Häggström, “Infinite clusters in dependent automorphism invariant percolation on trees”, Ann. Probab., 25:3 (1997), 1423–1436 | DOI | MR | Zbl

[16] F. Harary, “Methods of destroying the symmetries of a graph”, Bull. Malays. Math. Sci. Soc. (2), 24:2 (2001), 183–191 (2002) | MR | Zbl

[17] F. Harary D. Ranjan, “Breaking symmetry in complete graphs by orienting edges: asymptotic bounds”, Inform. Process. Lett., 67:5 (1998), 227–230 | DOI | MR

[18] V. A. Kaimanovich, “Brounovskoe dvizhenie na sloeniyakh: entropiya, invariantnye mery, peremeshivanie”, Funkts. analiz i ego pril., 22:4 (1988), 82–83 | MR | Zbl

[19] V. A. Kaimanovich, “Measure-theoretic boundaries of Markov chains, $0$-$2$ laws and entropy”, Harmonic analysis and discrete potential theory (Frascati, 1991), Plenum, New York, 1992, 145–180 | DOI | MR

[20] V. A. Kaimanovich, “Hausdorff dimension of the harmonic measure on trees”, Ergodic Theory Dynam. Systems, 18:3 (1998), 631–660 | DOI | MR | Zbl

[21] V. A. Kaimanovich, “Random walks on Sierpiński graphs: hyperbolicity and stochastic homogenization”, Fractals in Graz 2001, Trends Math., Birkhäuser, Basel, 2003, 145–183 | MR | Zbl

[22] V. A. Kaimanovich, “Amenability and the Liouville property”, Israel J. Math., 149 (2005), 45–85 | DOI | MR | Zbl

[23] V. A. Kaimanovich, “Hopf decomposition and horospheric limit sets”, Ann. Acad. Sci. Fenn. Math., 35:2 (2010), 335–350 | DOI | MR | Zbl

[24] V. A. Kaimanovich, M. Lyubich, Conformal and harmonic measures on laminations associated with rational maps, Mem. Amer. Math. Soc., 173, no. 820, 2005, vi+119 pp. | MR

[25] V. A. Kaimanovich, W. Woess, “Construction of discrete, non-unimodular hypergroups”, Probability measures on groups and related structures, XI (Oberwolfach, 1994), World Sci. Publ., River Edge, NJ, 1995, 196–209 | MR | Zbl

[26] V. A. Kaimanovich, W. Woess, “Boundary and entropy of space homogeneous Markov chains”, Ann. Probab., 30:1 (2002), 323–363 | DOI | MR | Zbl

[27] R. Lyons, R. Pemantle, Yu. Peres, “Ergodic theory on Galton–Watson trees: speed of random walk and dimension of harmonic measure”, Ergodic Theory Dynam. Systems, 15:3 (1995), 593–619 | DOI | MR

[28] J. R. Norris, Markov Chains, Cambridge Series in Statistical and Probabilistic Mathematics, 2, Cambridge University Press, Cambridge, 1998, Reprint of 1997 original | MR | Zbl

[29] F. Paulin, “Propriétés asymptotiques des relations d'équivalences mesurées discrètes”, Markov Process. Related Fields, 5:2 (1999), 163–200 | MR | Zbl

[30] M. Rosenblatt, Markov Processes. Structure and Asymptotic Behavior, Die Grundlehren der mathematischen Wissenschaften, 184, Springer-Verlag, New York, 1971 | MR | Zbl

[31] M. A. Ronan, J. Tits, “Twin trees. II. Local structure and a universal construction”, Israel J. Math., 109 (1999), 349–377 | DOI | MR | Zbl

[32] G. Schlichting, “Polynomidentitäten und Permutationsdarstellungen lokalkompakter Gruppen”, Invent. Math., 55:2 (1979), 97–106 | DOI | MR | Zbl

[33] Ya. G. Sinai, “Gibbsovskie mery v ergodicheskoi teorii”, Uspekhi matem. nauk, 27:4(166) (1972), 21–64 | MR | Zbl

[34] D. Sullivan, “The density at infinity of a discrete group of hyperbolic motions”, Inst. Hautes Études Sci. Publ. Math., 50 (1979), 171–202 | DOI | MR | Zbl

[35] P. M. Soardi, W. Woess, “Amenability, unimodularity, and the spectral radius of random walks on infinite graphs”, Math. Z., 205:3 (1990), 471–486 | DOI | MR | Zbl

[36] V. I. Trofimov, “Gruppy avtomorfizmov grafov kak topologicheskie gruppy”, Matem. zametki, 38:3 (1985), 378–385 | MR | Zbl

[37] W. T. Tutte, “A census of planar triangulations”, Canad. J. Math., 14 (1962), 21–38 | DOI | MR | Zbl

[38] W. T. Tutte, “On the enumeration of convex polyhedra”, J. Combin. Theory Ser. B, 28:2 (1980), 105–126 | DOI | MR | Zbl

[39] W. Woess, “Topological groups and recurrence of quasitransitive graphs”, Rend. Sem. Mat. Fis. Milano, 64 (1994), 185–213 | DOI | MR

[40] W. Woess, Random Walks on Infinite Graphs and Groups, Cambridge Tracts in Mathematics, 138, Cambridge University Press, Cambridge, 2000 | MR | Zbl