
Crossing Number Inequality
Yufei Zhao teaches this lecture from MIT's 18.226 Probabilistic Methods in Combinatorics, proving the crossing number inequality for graph drawings. The lecture shows how the probabilistic method, a tool for proving existence results by analyzing random constructions, can be applied inside graph theory to bound the minimum number of edge crossings in any drawing of a graph with many edges relative to its vertices. Zhao builds the proof step by step, starting from the basic crossing number bound derived from Euler's formula and then strengthening it through a random sampling argument on vertex subsets. The lecture is tightly focused on a single theorem and its proof technique, aimed at students already familiar with basic graph theory and probability, and runs about eighteen minutes as part of the fall 2024 course sequence.