Probabilistic Combinatorics

12 units · Graduate

Intermittent: 12 units This course covers the probabilistic method for combinatorics in detail and introduces randomized algorithms and the theory of random graphs. Methods covered include the second moment method, the R and #246;dl nibble, the Lov and #225;sz local lemma, correlation inequalities, martingale's and tight concentration, Janson's inequality, branching processes, coupling and the differential equations method for discrete random processes. Objects studied include the configuration model for random regular graphs, Markov chains, the phase transition in the Erd and #246;s-R and #233;nyi random graph, and the Barab and #225;si-Albert preferential attachment model. (Three 50 minute lectures) Prerequisites: ( 21-301 or 21-701 Min. grade B) and ( 21-325 or 36-225 or 15-259 or 36-218 )