Home | Contents | Submissions, editors, etc. | Login | Search | ECP
 Electronic Journal of Probability > Vol. 12 (2007) > Paper 54 open journal systems 


Processes on Unimodular Random Networks

David J. Aldous, University of California, Berkeley
Russell Lyons, Indiana University


Abstract
We investigate unimodular random networks. Our motivations include their characterization via reversibility of an associated random walk and their similarities to unimodular quasi-transitive graphs. We extend various theorems concerning random walks, percolation, spanning forests, and amenability from the known context of unimodular quasi-transitive graphs to the more general context of unimodular random networks. We give properties of a trace associated to unimodular random networks with applications to stochastic comparison of continuous-time random walk.


Full text: PDF

Pages: 1454-1508

Published on: November 21, 2007
Bibliography
  1. Adams, Scot; Lyons, Russell. Amenability, Kazhdan's property and percolation for trees, groups and equivalence relations. Israel J. Math. 75 (1991), no. 2-3, 341--370. MR1164598 (93j:43001)
  2. Aldous, David. Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab. 1 (1991), no. 2, 228--266. MR1102319 (92j:60009)
  3. Aldous, David. Asymptotics in the random assignment problem. Probab. Theory Related Fields 93 (1992), no. 4, 507--534. MR1183889 (94b:60013)
  4. Aldous, David; Percus, Allon G. Scaling and universality in continuous length combinatorial optimization. Proc. Natl. Acad. Sci. USA 100 (2003), no. 20, 11211--11215 (electronic). MR2007286 (2004g:90088)
  5. Aldous, David; Steele, J. Michael. The objective method: probabilistic combinatorial optimization and local weak convergence. Probability on discrete structures, 1--72, Encyclopaedia Math. Sci., 110, Springer, Berlin, 2004. MR2023650 (2005e:60018)
  6. Alexander, Kenneth S. Percolation and minimal spanning forests in infinite graphs. Ann. Probab. 23 (1995), no. 1, 87--104. MR1330762 (96c:60114)
  7. Angel, O. Growth and percolation on the uniform infinite planar triangulation. Geom. Funct. Anal. 13 (2003), no. 5, 935--974. MR2024412 (2005b:60015)
  8. Angel, Omer; Schramm, Oded. Uniform infinite planar triangulations. Comm. Math. Phys. 241 (2003), no. 2-3, 191--213. MR2013797 (2005b:60021)
  9. Bak, Per; Tang, Chao; Wiesenfeld, Kurt. Self-organized criticality. Phys. Rev. A (3) 38 (1988), no. 1, 364--374. MR0949160 (89g:58126)
  10. Becker, Howard; Kechris, Alexander S.. The Descriptive Set Theory of Polish Group Actions. London Mathematical Society Lecture Note Series, 232. Cambridge University Press, Cambridge. MR1425877 (MR98d:54068)
  11. Benjamini, Itai; Lyons, Russell; Peres, Yuval; Schramm, Oded. Critical percolation on any nonamenable group has no infinite clusters. Ann. Probab. 27 (1999), no. 3, 1347--1356. MR1733151 (2000k:60197)
  12. Benjamini, I.; Lyons, R.; Peres, Y.; Schramm, O. Group-invariant percolation on graphs. Geom. Funct. Anal. 9 (1999), no. 1, 29--66. MR1675890 (99m:60149)
  13. Benjamini, Itai; Lyons, Russell; Peres, Yuval; Schramm, Oded. Uniform spanning forests. Ann. Probab. 29 (2001), no. 1, 1--65. MR1825141 (2003a:60015)
  14. Benjamini, Itai; Lyons, Russell; Schramm, Oded. Percolation perturbations in potential theory and random walks. Random walks and discrete potential theory (Cortona, 1997), 56--84, Sympos. Math., XXXIX, Cambridge Univ. Press, Cambridge, 1999. MR1802426 (2002f:60185)
  15. Benjamini, Itai; Schramm, Oded. Percolation in the hyperbolic plane. J. Amer. Math. Soc. 14 (2001), no. 2, 487--507 (electronic). MR1815220 (2002h:82049)
  16. Benjamini, Itai; Schramm, Oded. Recurrence of distributional limits of finite planar graphs. Electron. J. Probab. 6 (2001), no. 23, 13 pp. (electronic). MR1873300 (2002m:82025)
  17. Biggs, Norman. Algebraic potential theory on graphs. Bull. London Math. Soc. 29 (1997), no. 6, 641--682. MR1468054 (98m:05120)
  18. Bollobás, Béla. Random graphs. Second edition. Cambridge Studies in Advanced Mathematics, 73. Cambridge University Press, Cambridge, 2001. xviii+498 pp. ISBN: 0-521-80920-7; 0-521-79722-5 MR1864966 (2002j:05132)
  19. Bowen, Lewis. Periodicity and circle packings of the hyperbolic plane. Geom. Dedicata 102 (2003), 213--236. MR2026846 (2005a:52014)
  20. Bowen, Lewis. Couplings of uniform spanning forests. Proc. Amer. Math. Soc. 132 (2004), no. 7, 2151--2158 (electronic). MR2053989 (2005e:60017)
  21. Bowen, Lewis; Radin, Charles. Densest packing of equal spheres in hyperbolic space. Discrete Comput. Geom. 29 (2003), no. 1, 23--39. MR1946792 (2003m:52023)
  22. Brown, Lawrence G.; Kosaki, Hideki. Jensen's inequality in semi-finite von Neumann algebras. J. Operator Theory 23 (1990), no. 1, 3--19. MR1054812 (92g:46078)
  23. Chen, Dayue; Peres, Yuval. Anchored expansion, percolation and speed. With an appendix by Gábor Pete. Ann. Probab. 32 (2004), no. 4, 2978--2995. MR2094436 (2005g:60022)
  24. Connes, A. Classification of injective factors. Cases $IIsb{1},$ $IIsb{infty },$ $IIIsb{lambda },$ $lambda not=1$. Ann. of Math. (2) 104 (1976), no. 1, 73--115. MR0454659 (56 #12908)
  25. Connes, A.; Feldman, J.; Weiss, B. An amenable equivalence relation is generated by a single transformation. Ergodic Theory Dynamical Systems 1 (1981), no. 4, 431--450 (1982). MR0662736 (84h:46090)
  26. Dhar, D. Studying self-organized criticality with exactly solved models. Preprint, 1999. arXiv:cond-mat/9909009.
  27. Doyle, Peter G.; Snell, J. Laurie. Random walks and electric networks. Carus Mathematical Monographs, 22. Mathematical Association of America, Washington, DC, 1984. xiv+159 pp. ISBN: 0-88385-024-9 MR0920811 (89a:94023)
  28. Elek, Gábor; Szabó, Endre. Sofic groups and direct finiteness. J. Algebra 280 (2004), no. 2, 426--434. MR2089244 (2005d:16041)
  29. Elek, Gábor; Szabó, Endre. Hyperlinearity, essentially free actions and $Lsp 2$-invariants. The sofic property. Math. Ann. 332 (2005), no. 2, 421--441. MR2178069 (2007i:43002)
  30. Feldman, Jacob; Hahn, Peter; Moore, Calvin C. Orbit structure and countable sections for actions of continuous groups. Adv. in Math. 28 (1978), no. 3, 186--230. MR0492061 (58 #11217)
  31. 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(58 #28261a)
  32. Feldman, Jacob; Moore, Calvin C. Ergodic equivalence relations, cohomology, and von Neumann algebras. II. Trans. Amer. Math. Soc. 234 (1977), no. 2, 325--359. MR0578730(58 #28261b)
  33. 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)
  34. Fontes, L. R. G.; Mathieu, P. On symmetric random walks with random conductances on ${Bbb Z}sp d$. Probab. Theory Related Fields 134 (2006), no. 4, 565--602. MR2214905 (2006m:60142)
  35. Frieze, Alan; Suen, Stephen. On the independence number of random cubic graphs. Random Structures Algorithms 5 (1994), no. 5, 649--664. MR1300593 (96e:05150)
  36. Furman, Alex. Gromov's measure equivalence and rigidity of higher rank lattices. Ann. of Math.(2) 150 (1999), no. 3, 1059--1081. MR1740986 (2001a:22017)
  37. Furman, Alex. Orbit equivalence rigidity. Ann. of Math. (2) 150 (1999), no. 3, 1083--1108. MR1740985 (2001a:22018)
  38. Gaboriau, Damien. Coût des relations d'équivalence et des groupes. (French) [Cost of equivalence relations and of groups] Invent. Math. 139 (2000), no. 1, 41--98. MR1728876 (2001f:28030)
  39. Gaboriau, Damien. Invariants $lsp 2$ de relations d'équivalence et de groupes. (French) [$lsp 2$-invariants of equivalence relations and groups] Publ. Math. Inst. Hautes Études Sci. No. 95 (2002), 93--150. MR1953191 (2004b:22009)
  40. Gandolfi, A.; Keane, M. S.; Newman, C. M. Uniqueness of the infinite component in a random graph with applications to percolation and spin glasses. Probab. Theory Related Fields 92 (1992), no. 4, 511--527. MR1169017 (93f:60149)
  41. Gottschalk, Walter. Some general dynamical notions. Recent advances in topological dynamics (Proc. Conf. Topological Dynamics, Yale Univ., New Haven, Conn., 1972; in honor of Gustav Arnold Hedlund), pp. 120--125. Lecture Notes in Math., Vol. 318, Springer, Berlin, 1973. MR0407821 (53 #11591)
  42. Grimmett, G. R. Random labelled trees and their branching networks. J. Austral. Math. Soc. Ser. A 30 (1980/81), no. 2, 229--237. MR0607933 (82g:05042)
  43. Grimmett, G. R.; Kesten, H.; Zhang, Y. Random walk on the infinite cluster of the percolation model. Probab. Theory Related Fields 96 (1993), no. 1, 33--44. MR1222363 (94i:60078)
  44. Gromov, M. Endomorphisms of symbolic algebraic varieties. J. Eur. Math. Soc. (JEMS) 1 (1999), no. 2, 109--197. MR1694588 (2000f:14003)
  45. Häggström, Olle. Random-cluster measures and uniform spanning trees. Stochastic Process. Appl. 59 (1995), no. 2, 267--275. MR1357655 (97b:60170)
  46. Häggström, Olle. Infinite clusters in dependent automorphism invariant percolation on trees. Ann. Probab. 25 (1997), no. 3, 1423--1436. MR1457624 (98f:60207)
  47. Häggström, Olle. Uniform and minimal essential spanning forests on trees. Random Structures Algorithms 12 (1998), no. 1, 27--50. MR1637387 (99i:05186)
  48. Häggström, Olle; Peres, Yuval. Monotonicity of uniqueness for percolation on Cayley graphs: all infinite clusters are born simultaneously. Probab. Theory Related Fields 113 (1999), no. 2, 273--285. MR1676835 (99k:60253)
  49. Heicklen, Deborah; Hoffman, Christopher. Return probabilities of a simple random walk on percolation clusters. Electron. J. Probab. 10 (2005), no. 8, 250--302 (electronic). MR2120245 (2005j:60182)
  50. Holroyd, Alexander E.; Peres, Yuval. Trees and matchings from point processes. Electron. Comm. Probab. 8 (2003), 17--27 (electronic). MR1961286 (2004b:60127)
  51. Kadison, Richard V.; Ringrose, John R. Fundamentals of the theory of operator algebras. Vol. II. Advanced theory. Corrected reprint of the 1986 original. Graduate Studies in Mathematics, 16. American Mathematical Society, Providence, RI, 1997. pp. i--xxii and 399--1074. ISBN: 0-8218-0820-6 MR1468230 (98f:46001b)
  52. Kaimanovich, Vadim A. Amenability, hyperfiniteness, and isoperimetric inequalities. C. R. Acad. Sci. Paris Sér. I Math. 325 (1997), no. 9, 999--1004. MR1485618 (98j:28014)
  53. Kaimanovich, Vadim A. Hausdorff dimension of the harmonic measure on trees. Ergodic Theory Dynam. Systems 18 (1998), no. 3, 631--660. MR1631732 (99g:60123)
  54. Kaplansky, Irving. Fields and rings. The University of Chicago Press, Chicago, Ill.-London 1969 ix+198 pp. MR0269449 (42 #4345)
  55. Kechris, Alexander S. Amenable equivalence relations and Turing degrees. J. Symbolic Logic 56 (1991), no. 1, 182--194. MR1131739 (93c:03061)
  56. Kechris, Alexander S.; Miller, Benjamin D. Topics in orbit equivalence. Lecture Notes in Mathematics, 1852. Springer-Verlag, Berlin, 2004. x+134 pp. ISBN: 3-540-22603-6 MR2095154 (2005f:37010)
  57. Levitt, Gilbert. On the cost of generating an equivalence relation. Ergodic Theory Dynam. Systems 15 (1995), no. 6, 1173--1181. MR1366313 (96i:58091)
  58. Lubotzky, Alexander. Discrete groups, expanding graphs and invariant measures. With an appendix by Jonathan D. Rogawski. Progress in Mathematics, 125. Birkhäuser Verlag, Basel, 1994. xii+195 pp. ISBN: 3-7643-5075-X MR1308046 (96g:22018)
  59. Lück, Wolfgang. $Lsp 2$-torsion and $3$-manifolds. Low-dimensional topology (Knoxville, TN, 1992), 75--107, Conf. Proc. Lecture Notes Geom. Topology, III, Int. Press, Cambridge, MA, 1994. MR1316175 (96g:57019)
  60. Lück, Wolfgang. $Lsp 2$-invariants: theory and applications to geometry and $K$-theory. Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics], 44. Springer-Verlag, Berlin, 2002. xvi+595 pp. ISBN: 3-540-43566-2 MR1926649 (2003m:58033)
  61. Lyons, Russell. Random walks and percolation on trees. Ann. Probab. 18 (1990), no. 3, 931--958. MR1062053 (91i:60179)
  62. Lyons, Russell. A bird's-eye view of uniform spanning trees and forests. Microsurveys in discrete probability (Princeton, NJ, 1997), 135--162, DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 41, Amer. Math. Soc., Providence, RI, 1998. MR1630412 (99e:60029)
  63. Lyons, Russell. Asymptotic enumeration of spanning trees. Combin. Probab. Comput. 14 (2005), no. 4, 491--522. MR2160416 (2006j:05048)
  64. Lyons, Russell; Morris, Benjamin J.; Schramm, Oded. Ends in uniform spanning forests. Preprint, 2007. arXiv:0706.0358
  65. 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 (96e:60125)
  66. Lyons, Russell; Peres, Yuval. Probability on Trees and Networks. Cambridge University Press. In preparation. http://mypage.iu.edu/~rdlyons/
  67. Lyons, Russell; Peres, Yuval; Schramm, Oded. Minimal spanning forests. Ann. Probab. 34 (2006), no. 5, 1665--1692. MR2271476 (2007m:60299)
  68. Lyons, Russell; Schramm, Oded. Indistinguishability of percolation clusters. Ann. Probab. 27 (1999), no. 4, 1809--1836. MR1742889 (2000m:60114)
  69. Lyons, Russell; Schramm, Oded. Stationary measures for random walks in a random environment with random scenery. New York J. Math. 5 (1999), 107--113 (electronic). MR1703207 (2000m:60115)
  70. Meester, R.; Redig, F.; Znamenski, D. The abelian sandpile: a mathematical introduction. Markov Process. Related Fields 7 (2001), no. 4, 509--523. MR1893138 (2003f:60175)
  71. Molloy, Michael; Reed, Bruce. A critical point for random graphs with a given degree sequence. Proceedings of the Sixth International Seminar on Random Graphs and Probabilistic Methods in Combinatorics and Computer Science, "Random Graphs '93" (Pozna'n, 1993). Random Structures Algorithms 6 (1995), no. 2-3, 161--179. MR1370952 (97a:05191)
  72. Newman, C. M.; Schulman, L. S. Infinite clusters in percolation models. J. Statist. Phys. 26 (1981), no. 3, 613--628. MR0648202 (83e:82038)
  73. Nielsen, Ole A. Direct integral theory. Lecture Notes in Pure and Applied Mathematics, 61. Marcel Dekker, Inc., New York, 1980. ix+165 pp. ISBN: 0-8247-6971-6 MR0591683 (82e:46081)
  74. Orey, Steven. An ergodic theorem for Markov chains. Z. Wahrscheinlichkeitstheorie Verw. Gebiete 1 1962 174--176. MR0145587 (26 #3117)
  75. 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 (2001m:37010)
  76. Pemantle, Robin. Choosing a spanning tree for the integer lattice uniformly. Ann. Probab. 19 (1991), no. 4, 1559--1574. MR1127715 (92g:60014)
  77. Pittet, Ch.; Saloff-Coste, L. On the stability of the behavior of random walks on groups. J. Geom. Anal. 10 (2000), no. 4, 713--737. MR1817783 (2002m:60012)
  78. Radin, Charles. Aperiodic tilings, ergodic theory, and rotations. The mathematics of long-range aperiodic order (Waterloo, ON, 1995), 499--519, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 489, Kluwer Acad. Publ., Dordrecht, 1997. MR1460035 (98f:52027)
  79. Radin, Charles. Miles of tiles. Student Mathematical Library, 1. American Mathematical Society, Providence, RI, 1999. xii+120 pp. ISBN: 0-8218-1933-X MR1707270 (2000f:52026)
  80. Robinson, E. Arthur, Jr. The dynamical theory of tilings and quasicrystallography. Ergodic theory of $Zsp d$ actions (Warwick, 1993--1994), 451--473, London Math. Soc. Lecture Note Ser., 228, Cambridge Univ. Press, Cambridge, 1996. MR1411233 (97i:52023)
  81. Royden, H. L. Real analysis. Third edition. Macmillan Publishing Company, New York, 1988. xx+444 pp. ISBN: 0-02-404151-3 MR1013117 (90g:00004)
  82. Salvatori, Maura. On the norms of group-invariant transition operators on graphs. J. Theoret. Probab. 5 (1992), no. 3, 563--576. MR1176438 (93h:60113)
  83. Schick, Thomas. $Lsp 2$-determinant class and approximation of $Lsp 2$-Betti numbers. Trans. Amer. Math. Soc. 353 (2001), no. 8, 3247--3265 (electronic). MR1828605 (2002f:58056)
  84. Schlichting, Günter. Polynomidentitäten und Permutationsdarstellungen lokalkompakter Gruppen. (German) Invent. Math. 55 (1979), no. 2, 97--106. MR0553703 (81d:22006)
  85. 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 (91m:43002)
  86. Solomyak, Boris. Dynamics of self-similar tilings. Ergodic Theory Dynam. Systems 17 (1997), no. 3, 695--738. MR1452190 (98f:52030)
  87. Timár, Ádám. Tree and grid factors for general point processes. Electron. Comm. Probab. 9 (2004), 53--59 (electronic). MR2081459 (2005h:60145)
  88. Trofimov, V. I. Groups of automorphisms of graphs as topological groups. (Russian) Mat. Zametki 38 (1985), no. 3, 378--385, 476. MR0811571 (87d:05091)
  89. Weiss, Benjamin. Sofic groups and dynamical systems. Ergodic theory and harmonic analysis (Mumbai, 1999). Sankhy=a Ser. A 62 (2000), no. 3, 350--359. MR1803462 (2001j:37022)
  90. Zimmer, Robert J. Ergodic theory and semisimple groups. Monographs in Mathematics, 81. Birkhäuser Verlag, Basel, 1984. x+209 pp. ISBN: 3-7643-3184-4 MR0776417 (86j:22014)
















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