CS445: Combinatorics

Shanghai Jiao Tong University, Fall 2020

Teaching Staff

	name	email	office hour
Instructor	Shuai Li	shuaili8@sjtu.edu.cn	Mon 10-11:30 Rm 1406-2, Software College
TA	Yueran Yang	yangyr99@sjtu.edu.cn	Friday 13:00-15:00 EE 1-406

News

Course Information

Lecture times

• Mon 8:00-9:40 at Dong Shang Yuan 407 (Week 1-16)
• Thu 10:00-11:40 at Dong Shang Yuan 407 (Week 1-8)

Grading Your grade will be determined from a final exam (30%), a midterm exam (20%), a project (10%), assignments (35%) and participance (5%).

Textbook and References

• Graph Theory, by Reinhard Diestel [Preview link]
• Introduction to Graph Theory, by Douglas West
• Combinatorics and Graph Theory, by Harris, Hirst and Mossinghoff
• Graph Theory, by Bondy and Murty
• A Course in Combinatorics, by J. H. Van Lint

Schedule

week	date	topic	materials
1	Sep 7	1 Introduction and basics	pdf
	Sep 10	2 Girth, Connectivity, Bipartite graphs	pdf
2	Sep 14	3 Trees	pdf
	Sep 17
3	Sep 21	4 Circuits	pdf
	Sep 24
4	Sep 28
5	Oct 10	5 Matching	pdf
6	Oct 12		Gale-Shapley.gif
	Oct 15
7	Oct 19	6 Coloring	pdf
	Oct 22
8	Oct 26	Midterm Review	pdf
	Oct 29	Midterm Exam
9	Nov 2
10	Nov 9	7 Planarity	pdf
11	Nov 16	8 Ramsey Theory	pdf
12	Nov 23
13	Nov 30	9 Connectivity Revisited	pdf
14	Dec 7		pdf
15	Dec 14		final review
16	Dec 21	Final Exam