Probabilistic Methods in Combinatorics
This MIT OpenCourseWare graduate course teaches the probabilistic method, a technique for proving that combinatorial objects exist by showing a random construction succeeds with positive probability. The material covers core methodology including the first and second moment methods, the Lovasz Local Lemma, correlation inequalities, martingales and concentration of measure, and applications to graph coloring, Ramsey-type problems, and random graphs. Materials include lecture notes and problem sets drawn from the instructor's teaching of the subject, following the approach of Alon and Spencer's textbook on the topic. The course is aimed at graduate students already comfortable with combinatorics and probability who want to see how randomness becomes a constructive proof tool rather than just a modeling assumption. As with all MIT OCW offerings, all materials are free to access with no certificate offered.