Local algorithms for independent sets are half-optimal

Abstract

We show that the largest density of factor of i.i.d. independent sets in the d -regular tree is asymptotically at most ( log d ) / d as d → ∞ . This matches the lower bound given by previous constructions. It follows that the largest independent sets given by local algorithms on random d -regular graphs have the same asymptotic density. In contrast, the density of the largest independent sets in these graphs is asymptotically 2 ( log d ) / d . We prove analogous results for Poisson–Galton–Watson trees, which yield bounds for local algorithms on sparse Erdős–Rényi graphs.