
Independent Sets and Turán's Theorem
Yufei Zhao continues MIT's 18.226 Probabilistic Methods in Combinatorics with a lecture on independent sets and cliques in graphs, building toward a proof of Turán's theorem. He shows how the probabilistic method, rather than direct combinatorial construction, can establish lower bounds on the size of an independent set a graph must contain given its edge density. The argument proceeds by assigning a random ordering to the vertices and analyzing the expected size of the set this ordering produces, turning an existence question into a calculation about averages. The lecture fits into the course's broader project of using randomness as a proof technique in extremal graph theory. It assumes familiarity with basic graph theory and probability, and works through the argument on the board with minimal digression, typical of the course's dense, proof-driven style.