
Lower Bounds to Ramsey Numbers
Yufei Zhao teaches this session from MIT's 18.226 Probabilistic Methods in Combinatorics, covering how the probabilistic method produces lower bounds for Ramsey numbers. He develops the basic random coloring argument before refining it with the alteration (deletion) method, which removes problematic vertices or edges from a random construction to sharpen the bound. The lecture then turns to the Lovász Local Lemma, showing how it handles dependencies between bad events that the simple union bound cannot, and applies it to push Ramsey number lower bounds further than elementary counting allows. Zhao works through the arguments on the board step by step, connecting each technique back to the central question of how large a graph can be while avoiding both a clique and an independent set of a given size. The lecture assumes familiarity with basic probability and graph theory from earlier sessions in the course.