# Factors of IID on Trees

@article{Lyons2016FactorsOI, title={Factors of IID on Trees}, author={Russell Lyons}, journal={Combinatorics, Probability and Computing}, year={2016}, volume={26}, pages={285 - 300} }

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… Expand

#### Topics from this paper

#### 34 Citations

Entropy inequalities for factors of IID

- Mathematics
- 2017

This paper is concerned with certain invariant random processes (called factors of IID) on infinite trees. Given such a process, one can assign entropies to different finite subgraphs of the tree.… Expand

On large-girth regular graphs and random processes on trees

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2018

Using Glauber dynamics on processes to give a sufficient condition for a branching Markov chain to be factor of i.i.d. processes, this work proves a family of combinatorial statements about random $d-regular graphs. Expand

Factor of iid Schreier decoration of transitive graphs

- 2021

A Schreier decoration is a combinatorial coding of an action of the free group Fd on the vertex set of a 2d-regular graph. We investigate whether a Schreier decoration exists on various countably… Expand

Factor of IID Percolation on Trees

- Computer Science, Mathematics
- SIAM J. Discret. Math.
- 2016

It is shown that the density of any factor of iid site percolation process with finite clusters is asymptotically at most (log d)/d as d tends to infinity, which means there is a (1/2)-factor approximation gap, asymPTotically in d, for estimating thedensity of maximal induced forests in locally tree-like d-regular graphs via factor ofiid processes. Expand

Finitely dependent processes are finitary

- Mathematics
- 2019

We show that any finitely-dependent invariant process on a transitive amenable graph is a finitary factor of an i.i.d. process. With an additional assumption on the geometry of the graph, namely that… Expand

Factor-of-iid balanced orientation of non-amenable graphs

- Mathematics
- 2021

We show that if a non-amenable, quasi-transitive, unimodular graph G has all degrees even then it has a factor-of-iid balanced orientation, meaning each vertex has equal inand outdegree. This result… Expand

Independence ratio and random eigenvectors in transitive graphs

- Mathematics
- 2015

A theorem of Hoffman gives an upper bound on the independence ratio of regular graphs in terms of the minimum λmin of the spectrum of the adjacency matrix. To complement this result we use random… Expand

Factors of IID have trivial one-ended tails

- Mathematics
- 2016

We study factor of i.i.d. processes on the $d$-regular tree for $d \geq 3$. We show that if such a process is restricted to two distant connected subgraphs of the tree, then the two parts are… Expand

A note on internal partitions: the $5$-regular case and beyond

- Mathematics
- 2021

An internal or friendly partition of a graph is a partition of the vertex set into two nonempty sets so that every vertex has at least as many neighbours in its own class as in the other one. It has… Expand

Correlation Bounds for Distant Parts of Factor of IID Processes

- Mathematics, Computer Science
- Combinatorics, Probability and Computing
- 2017

If a process on the d-regular tree is restricted to two distant connected subgraphs of the tree, then the two parts are basically uncorrelated, and any functions of the two part have correlation at most $k(d-1) / (\sqrt{ d-1})^k$ , where k denotes the distance between the sub graphs. Expand

#### References

SHOWING 1-10 OF 76 REFERENCES

Amenability, Kazhdan's property T , strong ergodicity and invariant means for ergodic group-actions

- Mathematics
- 1981

This paper discusses the relations between the following properties o finite measure preserving ergodic actions of a countable group G: strong ergodicity (i.e. the non-existence of almost invariant… Expand

Factors of independent and identically distributed processes with non-amenable group actions

- Mathematics
- Ergodic Theory and Dynamical Systems
- 2005

Let X be a graph and let G be a subgroup of the automorphism group of X. We investigate the question of when the full 2-shift process on the vertices of X has a G-factor process on the same graph… Expand

Group-invariant Percolation on Graphs

- Mathematics
- 1999

Abstract. Let G be a closed group of automorphisms of a graph X. We relate geometric properties of G and X, such as amenability and unimodularity, to properties of G-invariant percolation processes… Expand

Perfect matchings as IID factors on non-amenable groups

- Computer Science, Mathematics
- Eur. J. Comb.
- 2011

We prove that in every bipartite Cayley graph of every non-amenable group, there is a perfect matching that is obtained as a factor of independent uniform random variables. We also discuss expansion… Expand

Invariant percolation and measured theory of nonamenable groups

- Mathematics
- 2011

Using percolation techniques, Gaboriau and Lyons recently proved that every countable, discrete, nonamenable group $\Gamma$ contains measurably the free group $\mathbf F_2$ on two generators: there… Expand

Tree and Grid factors of General Point processes

- Mathematics
- 2004

We study isomorphism invariant point processes of $R^d$ whose groups of symmetries are almost surely trivial. We define a 1-ended, locally finite tree factor on the points of the process, that is, a… Expand

A measure-conjugacy invariant for free group actions

- Mathematics
- 2008

This paper introduces a new measure-conjugacy invariant for actions of free groups. Using this invariant, it is shown that two Bernoulli shifts over a finitely generated free group are measurably… Expand

Invariant colorings of random planar maps

- Mathematics
- Ergodic Theory and Dynamical Systems
- 2010

Abstract We show that every locally finite random graph embedded in the plane with an isometry-invariant distribution can be five-colored in an invariant and deterministic way, under some… Expand

Ramanujan graphings and correlation decay in local algorithms

- Mathematics, Computer Science
- Random Struct. Algorithms
- 2015

The upper bound k+1-2k/d1d-1k for the absolute value of the correlation of values on pairs of vertices of distance k is proved and it is shown that this bound is optimal. Expand

Fixed price of groups and percolation

- Mathematics
- Ergodic Theory and Dynamical Systems
- 2012

Abstract We prove that for every finitely generated group Γ, at least one of the following holds: (1) Γ has fixed price; (2) each of its Cayley graphs G has infinitely many infinite clusters for some… Expand