LOCAL ALGORITHMS FOR INDEPENDENT SETS ARE HALF-OPTIMAL

• 成果类型: Article
• 署名作者: Rahman, Mustazee; Virag, Balint
• 署名单位: University of Toronto
• 刊物名称: ANNALS OF PROBABILITY
• ISSN/ISSBN: 0091-1798
• DOI: 10.1214/16-AOP1094
• 发表日期: 2017
• 页码: 1543-1577
• 关键词: regular graphs; matchings; number; LIMITS

摘要

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 -> infinity. 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 Erdos-Renyi graphs.