Video details loadedContinue
HomeMIT 18.217 Graph Theory and Additive Combinatorics, Fall 2019Lecture 8: Szemerédi’s Graph Regularity Lemma III: Further Applications
Lecture 8: Szemerédi’s Graph Regularity Lemma III: Further Applications
1:21:21
Up Next
Lecture 9: Szemerédi’s Graph Regularity Lemma IV: Induced Removal Lemma
Description: After proving Roth’s theorem last lecture, Professor Zhao explains Behrend’s construction of large sets of integers without 3-term arithmetic progressions, as well as another application of the triangle removal lemma to subsets of a 2-dimensional lattice without corners.
The second half of the lecture discusses further applications of the regularity method within graph theory: graph embedding, counting, and removal lemmas, as well as a proof of the Erdős–Stone–Simonovits theorem on H-free graphs.
Instructor: Prof. Yufei Zhao
