Skip to main content

Research Repository

Advanced Search

Local algorithms for independent sets are half-optimal

Rahman, Mustazee; Virág, Bálint

Local algorithms for independent sets are half-optimal Thumbnail


Bálint Virág


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.


Rahman, M., & Virág, B. (2017). Local algorithms for independent sets are half-optimal. Annals of Probability, 45(3), 1543-1577.

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


Published Journal Article (313 Kb)

Copyright Statement
Copyright © 2017 Institute of Mathematical Statistics

You might also like

Downloadable Citations