Lecture 3: Forbidding a Subgraph II: Complete Bipartite Subgraph

Om kurset

Description: 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? Professor 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. Instructor: Prof. Yufei Zhao