Independent sets in random regular graphs

Type: 
PhD Student Seminar
Audience: 
CEU Community + Invited Guests
Building: 
Zrinyi u. 14
Room: 
310/A
Wednesday, January 15, 2014 - 2:00pm
Add to Calendar
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.