Lecture 2: Forbidding a Subgraph I: Mantel’s Theorem and Turán’s Theorem

Name: Lecture 2: Forbidding a Subgraph I: Mantel’s Theorem and Turán’s Theorem
Uploaded: 2020-05-12T18:00:15Z
Duration: 1 h 12 min 41 s
Description: Description: Which triangle-free graph has the maximum number of edges given the number of vertices? Professor Zhao shows the class Mantel’s theorem, which says that the answer is a complete bipartite graph. He also discusses generalizations: Turán’s theorem (for cliques) and the Erdős-Stone-Simonovits theorem (for general subgraphs). Instructor: Prof. Yufei Zhao

1:12:41

Up Next

Lecture 3: Forbidding a Subgraph II: Complete Bipartite Subgraph

Continue

Description: Which triangle-free graph has the maximum number of edges given the number of vertices? Professor Zhao shows the class Mantel’s theorem, which says that the answer is a complete bipartite graph. He also discusses generalizations: Turán’s theorem (for cliques) and the Erdős-Stone-Simonovits theorem (for general subgraphs).

Instructor: Prof. Yufei Zhao