Independent sets in random regular graphs
Abstract: An independent set in a graph is a set of vertices such that
there are no edges between them. How large can an independent set be
in a random d-regular graph? How large can it be if we are to
construct it using a (possibly randomized) algorithm that is local in
nature? We will discuss a recently introduced notion of local
algorithms for combinatorial optimization problems on large, random
d-regular graphs. We will then explain why, for asymptotically large
d, local algorithms can only produce independent sets of size at most
half of the largest ones. The factor of 1/2 turns out to be optimal.
Joint work with Balint Virag.