# Independent sets in random regular graphs

Date:

Wednesday, January 15, 2014 - 2:00pm to 3:30pm

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.