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 ...
What is the maximum number of edges in a graph forbidding a cycle of length four? What about forbidding a complete bipartite graph of a fixed size? Prof. Zhao discusses the Kővári-Sós-Turán theorem, which gives an upper bound. In the case of 4-cycles, a matching algebraic construction of a C4-free graph is also demonstrated.
License: Creative Commons BY-NC-SA
More information at https://ocw.mit.edu/terms
More courses at https://ocw.mit.edu/
6 Comments