Local algorithms for independent sets are half-optimal

Rahman, Mustazee; Virág, Bálint

doi:10.1214/16-aop1094

Local algorithms for independent sets are half-optimal

Rahman, Mustazee; Virág, Bálint

Authors

Dr Mustazee Rahman mustazee.rahman@durham.ac.uk
Associate Professor

Bálint Virág

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.

Citation

Rahman, M., & Virág, B. (2017). Local algorithms for independent sets are half-optimal. Annals of Probability, 45(3), 1543-1577. https://doi.org/10.1214/16-aop1094

Journal Article Type	Article
Acceptance Date	Jan 11, 2016
Online Publication Date	May 15, 2017
Publication Date	2017
Deposit Date	Sep 25, 2019
Publicly Available Date	Oct 4, 2021
Journal	Annals of Probability
Print ISSN	0091-1798
Publisher	Institute of Mathematical Statistics
Peer Reviewed	Peer Reviewed
Volume	45
Issue	3
Pages	1543-1577
DOI	https://doi.org/10.1214/16-aop1094