Video details loaded
HomeMIT 18.217 Graph Theory and Additive Combinatorics, Fall 2019Lecture 5: Forbidding a Subgraph IV: Dependent Random Choice
MIT 18.217 Graph Theory and Additive Combinatorics, Fall 2019

Video 5 of 10

Previous: Lecture 4: Forbidding a Subgraph III: Algebraic ConstructionsNext: Lecture 6: Szemerédi’s Graph Regularity Lemma I: Statement and Proof

Lecture 5: Forbidding a Subgraph IV: Dependent Random Choice

1:20:00

Up Next

Lecture 6: Szemerédi’s Graph Regularity Lemma I: Statement and Proof

Continue

Description: Professor Zhao discusses in this lecture the dependent random choice method in probabilistic combinatorics and its application to upper bounding the number of edges in an H-free graph, where H is a sparse bipartite graph. Also discussed in this lecture are the problems of forbidding an even cycle, and forbidding a clique 1-subdivision.

(The video is unfortunately cut off near the end due to technical issues with the recording. Students can refer to the notes for details.)

Instructor: Prof. Yufei Zhao