Probabilistic Methods 12-2: Dependent Random Choice
In the second video of Week 12, we state and prove the Dependent Random Choice Lemma. We then apply it to upper bound the Turan number of bipartite graphs.
For a proof of Turan's Theorem, see my other video: • Graph Theory 9-1: Turan's Theorem
For a proof of the Erdos-Stone Theorem, see my other video: • Graph Theory 10-2: Erdos Stone Theorem
Typo: the Theorem of Turan should have .5 n^2 instead of n choose 2.