## Coding invariant processes on infinite trees

Take the infinite 3-regular rooted tree and attach IID Uniform[0,1] random variables to vertices to get a random labeling. Take a measurable function f from the space of possible labelings to {-1,+1} such that f is invariant (deterministically invariant) under root-preserving automorphisms of the tree. We can now define a random {-1,+1}-valued process (X_v) indexed by the vertices v of the tree, as follows.

Given v, take an automorphism that maps v to root, inducing a map on labelings, and let Xv be f applied to the induced labelings.

The process (Xv) is statistically invariant under automorphisms. Consider p = P(Xv = Xw) for an edge vw.

Problem: What is the smallest value p* that p can be, over all possible f which have P(Xv = +1)= 1/2?

It is know indirectly that p* > 0 . This is because we can modify f into a function g whose associated process (Yv) has
P(Yv = 1, Yw = -1 for all 3 neighbors w of v) > q = (1 - 3p*)/2.
Now consider the random n-vertex 3-regular graph. Because as n \to \infty te random graph is locally like the 3-regular tree, we can use the function g to define an independent set (anti-clique) In of relative size In/n asymptotic to q. But it is known in this context that the best possible q is at most 0.4591....

Update (6/17). This item is now very outdated. For current related work see Russ Lyons Factors of IID on Trees.