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.