Hostname: page-component-745bb68f8f-b95js Total loading time: 0 Render date: 2025-01-11T00:01:04.679Z Has data issue: false hasContentIssue false
  • English
  • Français

Factors of IID on Trees

Published online by Cambridge University Press:  06 December 2016

RUSSELL LYONS
RUSSELL LYONS*
Affiliation:
Department of Mathematics, Indiana University, Rawles Hall, 831 East 3rd Street, Bloomington, IN 47405, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

Classical ergodic theory for integer-group actions uses entropy as a complete invariant for isomorphism of IID (independent, identically distributed) processes (a.k.a. product measures). This theory holds for amenable groups as well. Despite recent spectacular progress of Bowen, the situation for non-amenable groups, including free groups, is still largely mysterious. We present some illustrative results and open questions on free groups, which are particularly interesting in combinatorics, statistical physics and probability. Our results include bounds on minimum and maximum bisection for random cubic graphs that improve on all past bounds.

Keywords

Primary 05C3005C7005C8037A3537A5060G10Secondary 60G15
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 2 , March 2017 , pp. 285 - 300
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Abért, M. and Weiss, B. (2013) Bernoulli actions are weakly contained in any free action. Ergodic Theory Dynam. Systems 33 323–333.Google Scholar
[2] Adams, S. (1992) Very weak Bernoulli for amenable groups. Israel J. Math. 78 145–176.Google Scholar
[3] Alon, N. (1997) On the edge-expansion of graphs. Combin. Probab. Comput. 6 145–152.Google Scholar
[4] Angel, O., Benjamini, I., Gurel-Gurevich, O., Meyerovitch, T. and Peled, R. (2012) Stationary map coloring. Ann. Inst. Henri Poincaré Probab. Stat. 48 327–342.Google Scholar
[5] Backhausz, Á., Szegedy, B. and Virág, B. (2015) Ramanujan graphings and correlation decay in local algorithms. Random Struct. Alg. 47 424–435.Google Scholar
[6] Ball, K. (2005) Factors of independent and identically distributed processes with non-amenable group actions. Ergodic Theory Dynam. Systems 25 711–730.Google Scholar
[7] Ball, K. (2005) Poisson thinning by monotone factors. Electron. Comm. Probab. 10 60–69.Google Scholar
[8] Bollobás, B. (1988) The isoperimetric number of random regular graphs. European J. Combin. 9 241–244.Google Scholar
[9] Bowen, L. P. (2010) A measure-conjugacy invariant for free group actions. Ann. of Math. (2) 171 1387–1400.Google Scholar
[10] Bowen, L. P. (2013) Personal communication.Google Scholar
[11] Burton, R. M., Denker, M. and Smorodinsky, M. (1996) Finite state bilaterally deterministic strongly mixing processes. Israel J. Math. 95 115–133.Google Scholar
[12] Burton, R. M. and Steif, J. E. (1997) Coupling surfaces and weak Bernoulli in one and higher dimensions. Adv. Math. 132 1–23.Google Scholar
[13] Chatterjee, S., Peled, R., Peres, Y. and Romik, D. (2010) Gravitational allocation to Poisson points. Ann. of Math. (2) 172 617–671.Google Scholar
[14] Chifan, I. and Ioana, A. (2010) Ergodic subequivalence relations induced by a Bernoulli action. Geom. Funct. Anal. 20 53–67.Google Scholar
[15] Conley, C. T. (2013) Brooks' theorem for Bernoulli shifts. Preprint. www.math.cmu.edu/~clintonc/onlinepapers/bernoullibrooks.pdf Google Scholar
[16] Csóka, E., Gerencsér, B., Harangi, V. and Virág, B. (2015) Invariant Gaussian processes and independent sets on regular graphs of large girth. Random Struct. Alg. 47 284–303.Google Scholar
[17] Csóka, E. and Lippner, G. (2012) Invariant random matchings in Cayley graphs. arXiv:1211.2374 Google Scholar
[18] Dembo, A., Montanari, A. and Sen, S. (2015) Extremal cuts of sparse random graphs. arXiv:1503.03923 Google Scholar
[19] Díaz, J., Do, N., Serna, M. J. and Wormald, N. C. (2003) Bounds on the max and min bisection of random cubic and random 4-regular graphs. Theoret. Comput. Sci. 307 531–547.Google Scholar
[20] Díaz, J., Serna, M. J. and Wormald, N. C. (2007) Bounds on the bisection width for random d-regular graphs. Theoret. Comput. Sci. 382 120–130.Google Scholar
[21] Evans, W., Kenyon, C., Peres, Y. and Schulman, L. J. (2000) Broadcasting on trees and the Ising model. Ann. Appl. Probab. 10 410–433.Google Scholar
[22] Gamarnik, D. and Sudan, M. (2013) Limits of local algorithms over sparse random graphs. arXiv:1304.1831 Google Scholar
[23] Gurel-Gurevich, O. and Peled, R. (2013) Poisson thickening. Israel J. Math. 196 215–234.Google Scholar
[24] Harangi, V. and Virág, B. (2015) Independence ratio and random eigenvectors in transitive graphs. Ann. Probab. 43 2810–2840.Google Scholar
[25] Holroyd, A. E. (2011) Geometric properties of Poisson matchings. Probab. Theory Rel. Fields 150 511–527.Google Scholar
[26] Holroyd, A. E., Lyons, R. and Soo, T. (2011) Poisson splitting by factors. Ann. Probab. 39 1938–1982.Google Scholar
[27] Holroyd, A. E., Pemantle, R., Peres, Y. and Schramm, O. (2009) Poisson matching. Ann. Inst. Henri Poincaré Probab. Stat. 45 266–287.Google Scholar
[28] Holroyd, A. E. and Peres, Y. (2003) Trees and matchings from point processes. Electron. Comm. Probab. 8 17–27.Google Scholar
[29] Houdayer, C. (2012) Invariant percolation and measured theory of nonamenable groups [after Gaboriau-Lyons, Ioana, Epstein]. Astérisque 348, exp. no. 1039. Séminaire Bourbaki, Vol. 2010/2011.Google Scholar
[30] Kalikow, S. A. (1982) T, T −1 transformation is not loosely Bernoulli. Ann. of Math. (2) 115 393–409.Google Scholar
[31] Kardoş, F., Král', D. and Volec, J. (2012) Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs. Random Struct. Alg. 41 506–520.Google Scholar
[32] Kesten, H. (1959) Symmetric random walks on groups. Trans. Amer. Math. Soc. 92 336–354.Google Scholar
[33] Kolmogorov, A. N. (1958) A new metric invariant of transient dynamical systems and automorphisms in Lebesgue spaces. Dokl. Akad. Nauk SSSR (NS) 119 861–864.Google Scholar
[34] Kolmogorov, A. N. (1959) Entropy per unit time as a metric invariant of automorphisms. Dokl. Akad. Nauk SSSR 124 754–755.Google Scholar
[35] Kun, G. (2013) Expanders have a spanning Lipschitz subgraph with large girth. arXiv:1303.4982 Google Scholar
[36] Lyons, R. (2013) Fixed price of groups and percolation. Ergodic Theory Dynam. Systems 33 183–185.Google Scholar
[37] Lyons, R. and Nazarov, F. (2011) Perfect matchings as IID factors on non-amenable groups. European J. Combin. 32 1115–1125.Google Scholar
[38] Mester, P. (2011) A factor of i.i.d. with uniform marginals and infinite clusters spanned by equal labels. arXiv:1111.3067 Google Scholar
[39] Monien, B. and Preis, R. (2001) Upper bounds on the bisection width of 3- and 4-regular graphs. In Mathematical Foundations of Computer Science 2001 (Sgall, J., Pultr, A. and Kolman, P., eds), Vol. 2136 of Lecture Notes in Computer Science, Springer, pp. 524–536.Google Scholar
[40] Ornstein, D. S. (1970) Bernoulli shifts with the same entropy are isomorphic. Adv. Math. 4 337–352.Google Scholar
[41] Ornstein, D. S. (1970) Factors of Bernoulli shifts are Bernoulli shifts. Adv. Math. 5 349–364.Google Scholar
[42] Ornstein, D. S. (1973) An example of a Kolmogorov automorphism that is not a Bernoulli shift. Adv. Math. 10 49–62.Google Scholar
[43] Ornstein, D. S. (1974) Ergodic Theory, Randomness, and Dynamical Systems , Vol. 5 of Yale Mathematical Monographs, Yale University Press.Google Scholar
[44] Ornstein, D. S. and Weiss, B. (1975) Every transformation is bilaterally deterministic. Israel J. Math. 21 154–158.Google Scholar
[45] Ornstein, D. S. and Weiss, B. (1987) Entropy and isomorphism theorems for actions of amenable groups. J. Analyse Math. 48 1–141.Google Scholar
[46] Pemantle, R. (1992) Automorphism invariant measures on trees. Ann. Probab. 20 1549–1566.Google Scholar
[47] Popa, S. (2006) Some computations of 1-cohomology groups and construction of non-orbit-equivalent actions. J. Inst. Math. Jussieu 5 309–332.Google Scholar
[48] Quas, A. and Soo, T. (2016) A monotone Sinai theorem. Ann. Probab. 44 107–130.Google Scholar
[49] Rohlin, V. A. and Sinaĭ, J. G. (1961) The structure and properties of invariant measurable partitions. Dokl. Akad. Nauk SSSR 141 1038–1041.Google Scholar
[50] Sinaĭ, J. (1959) On the concept of entropy for a dynamic system. Dokl. Akad. Nauk SSSR 124 768–771.Google Scholar
[51] Sly, A. (2009) Personal communication.Google Scholar
[52] Smorodinsky, M. (1971) A partition on a Bernoulli shift which is not weakly Bernoulli. Math. Systems Theory 5 201–203.Google Scholar
[53] Soo, T. (2010) Translation-equivariant matchings of coin flips on ℤ d . Adv. Appl. Probab. 42 69–82.Google Scholar
[54] Timár, Á. (2004) Tree and grid factors for general point processes. Electron. Comm. Probab. 9 53–59.Google Scholar
[55] Timár, Á. (2011) Invariant colorings of random planar maps. Ergodic Theory Dynam. Systems 31 549–562.Google Scholar