Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Local algorithms for independent sets are half-optimal

Rahman, Mustazee and Virág, Bálint (2017) 'Local algorithms for independent sets are half-optimal.', Annals of probability., 45 (3). pp. 1543-1577.

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.

Item Type:Article
Full text:(VoR) Version of Record
Download PDF
(306Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.1214/16-AOP1094
Publisher statement:Copyright © 2017 Institute of Mathematical Statistics
Date accepted:11 January 2016
Date deposited:04 October 2021
Date of first online publication:15 May 2017
Date first made open access:04 October 2021

Save or Share this output

Export:
Export
Look up in GoogleScholar