Extremal and Probabilistic Graph Theory, 2020 Spring, USTC

Instructor: 马杰, Email: jiema@ustc.edu.cn, School of Math

Teaching assistant: 杨天驰, Email: ytc@mail.ustc.edu.cn, School of Math

Lecture time: Monday 15:55-18:20pm; Wednesday 14:00-15:35pm.

Lectures:

[Attention: during the coronavirus epidemic, there will be online lectures via Classin.]

Lecture 1: Turan's Theorem, Kovari-Sos-Turan Theorem. [videos] [notes]

Lecture 2: Hypergraph KST, Supersaturation Lemma. [videos] [writings] [notes]

Lecture 3: Blowup Lemma, Erdos-Stone-Simonovits Theorem. [videos] [writings] [notes]

Lecture 4: Szemeredi's Regularity Lemma. [videos] [writings] [notes]

Lecture 5: Triangle Removal Lemma, Roth's Theorem. [videos] [writings] [notes]

Lecture 6: Graph Embedding Lemma, Erdos-Stone-Simonovits Theorem (second proof). [videos] [writings] [notes]

Lecture 7: Graph Counting Lemma, Graph Removal Lemma. [videos] [writings] [notes]

Lecture 8: Erdos-Simonovits Stability Theorem. [videos] [writings] [notes]

Lecture 9: Induced Embedding Lemma, Induced Ramsey Theorem. [videos] [writings] [notes]

Lecture 10: Induced Graph Removal Lemma. [videos] [writings] [notes]

Lecture 11: Tao's Spectral Proof of Regularity Lemma. [videos] [writings] [notes]

Lecture 12: Extremal Bounds on Paths, Posa's Rotation. [videos] [writings] [notes]

Lecture 13: Extremal Bounds on Cycles. [videos] [writings] [notes]

Lecture 14: Bondy-Simonovits Theorem on even cycles. [videos] [writings] [notes]

Lecture 15: Applications of Posa's Rotation. [videos] [writings] [notes]

Lecture 16: Randomized Constructions and Erdos-Renyi Polarity. [videos] [writings] [notes]

Lecture 17: Algebraic Constructions. [videos] [writings] [notes]

Lecture 18: Random Algebraic Constructions. [videos] [writings] [notes]

Lecture 19: Dependent Random Choice. [videos] [writings] [notes]

Lecture 20: Bipartite graphs with bounded degree in one side. [videos] [writings] [notes]

Lecture 21: Bipartite graphs with bounded degree in one side - continued. [video1] [writing1] [video2] [writing2] [notes]

Homeworks:

HW1

HW2

HW3

HW4

HW5

总阅读量次