Lecture 3: Forbidding a Subgraph II: Complete Bipartite Subgraph

Name: Lecture 3: Forbidding a Subgraph II: Complete Bipartite Subgraph
Uploaded: 2020-05-12T18:00:04Z
Duration: 1 h 16 min 37 s
Description: 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

1:16:37

Up Next

Lecture 4: Forbidding a Subgraph III: Algebraic Constructions

Continue

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