## 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 X_{v} be f applied to the induced labelings.

The process (X_{v}) is statistically invariant under automorphisms. Consider p =
P(X_{v} = X_{w}) for an edge vw.

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

It is know indirectly that p_{*} > 0 .
This is because we can modify f into a function g whose associated process (Y_{v}) has

P(Y_{v} = 1, Y_{w} = -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) I_{n} of relative
size I_{n}/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.