Return to Colloquia & Seminar listing
Maximum independent sets in random d-regular graphs
ProbabilitySpeaker: | Allan Sly, UC Berkeley |
Location: | 2112 MSB |
Start time: | Wed, May 8 2013, 4:10PM |
Satisfaction and optimization problems subject to random constraints are a well-studied area in the theory of computation, combinatorics, statistical physics and probability theory. While the values of limiting thresholds have been predicted using non-rigorous heuristics from statistical physics for many such models, few have been rigorously established on sparse random graphs. In this context we study the size of maximum independent sets in random d-regular graphs. We show that for d exceeding a constant d(0), there exist explicit constants A, C depending on d such that the maximum size has constant fluctuations around A*n-C*(log n). This is joint work with Jian Ding and Nike Sun.