Local algorithms for independent sets are half-optimal

Mustazee Rahman, Balint Virag

We show that the largest density of factor of i.i.d. independent sets on the d-regular tree is asymptotically at most (log d)/d as d tends to infinity. This matches the lower bound…