Return to Colloquia & Seminar listing
Maximum independent sets in random d-regular graphsMathematical Physics & Probability
|Speaker: ||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.