LOCAL ALGORITHMS FOR INDEPENDENT SETS ARE HALF-OPTIMAL
LOCAL ALGORITHMS FOR INDEPENDENT SETS ARE HALF-OPTIMAL
复制标题
DOI：
10.1214/16-aop1094
复制
发表时间：
2017-05-01
影响因子：
2.3
通讯作者：
Virag, Balint
中科院分区：
文献类型：
--
作者：
Rahman, Mustazee;Virag, Balint
我们表明，在\(d\) - 正则树上独立同分布（i.i.d.）独立集的最大密度在\(d \to \infty\)时渐近至多为\(\frac{\log d}{d}\)。这与先前构造所给出的下界相匹配。由此可知，在随机\(d\) - 正则图上由局部算法给出的最大独立集具有相同的渐近密度。相比之下，这些图中最大独立集的密度渐近为\(\frac{2\log d}{d}\)。我们对泊松 - 高尔顿 - 沃森树证明了类似的结果，这为稀疏埃尔德什 - 仁伊（Erdős - Rényi）图上的局部算法给出了界限。
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.