5. Forbidding a subgraph IV: dependent random choice

Описание: MIT 18.217 Graph Theory and Additive Combinatorics, Fall 2019
Instructor: Yufei Zhao
View the complete course: https://ocw.mit.edu/18-217F19
YouTube Playlist:    • MIT 18.217 Graph Theory and Additive Combi...  

Prof. 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. (Note: The video is unfortunately cut off near the end due to technical issues with the recording. Students can refer to the notes for details.)

License: Creative Commons BY-NC-SA
More information at https://ocw.mit.edu/terms
More courses at https://ocw.mit.edu