*********************************** * Princeton Discrete Math Seminar * *********************************** Date: Thursday 15th December, 3:00 in Fine Hall 224. Speaker: Mustazee Rahman (MIT) Title: Independent sets, local algorithms and random regular graphs An ``independent set'' in a graph is a set of vertices that have 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? I will discuss a notion of local algorithms for combinatorial optimization problems on large, random d-regular graphs. Then I will 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. ----------- Next week: winter break Anyone wishing to be added to or removed from this mailing list should contact Paul Seymour (pds@math.princeton.edu)