Local algorithms for independent sets are half-optimal (Q2012245)

This paper considers independent sets in a random \(d\)-regular graph for large \(d\). In particular, it considers the size of independent sets that can be the output of a local algorithm that constructs independent sets. The term ``local'' refers to the assumption that the algorithm takes decisions about a vertex of the input graph based on the neighbourhood around this vertex within some bounded distance \(r\). The authors show several results about the sizes of the independent sets that can be produced by such an algorithm. Among other results, they show that such an independent set cannot be larger than \((1+ \varepsilon) d/ \log d\). Note that this is approximately half the independence number, which has been shown to be asymptotic to \(2 d /\log d\), by independent works of \textit{B. Bollobás} [Random graphs. 2nd ed. Cambridge: Cambridge University Press (2001; Zbl 0979.05003)], \textit{B. D. McKay} [Ars Comb. 23A, 179--185 (1987; Zbl 0644.05028)] as well as \textit{A. M. Frieze} and \textit{T. Łuczak} [J. Comb. Theory, Ser. B 54, No. 1, 123--132 (1992; Zbl 0771.05088)]. This result is proved through another key inequality that is also proved in the paper regarding the sizes of the intersections of such independent sets. Similar results are deduced for \(G(n,\lambda/n)\) random graphs, considering algorithms that act locally on a Galton-Watson tree whose offspring distribution is Poisson with parameter \(\lambda>0\).