Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

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.