CS3330: Combinatorics

Shanghai Jiao Tong University, Fall 2024

Teaching Staff

	name	email	office hour
Instructor	Shuai Li	shuaili8@sjtu.edu.cn	Mon 1-2 PM Rm 1406-2, Software College
Chief TA	Zilong Wang	wangzilong@sjtu.edu.cn	Wed 7-9 PM Rm 1119, Software College
TA	Zhijie Wang	violetevergarden@sjtu.edu.cn	Thur 7-9 PM Rm 1119, Software College
	Haitong Ma	mahaitong@sjtu.edu.cn	Fri 7-9 PM Rm 1119, Software College

Course Information

Lecture times

• Mon 10:00-11:40 at Dong Zhong Yuan 4-404 (Week 1-16)
• Thu 8:00-9:40 at Dong Zhong Yuan 4-404 (Week 1-8)

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

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 19	1 Introduction and basics	pdf
2	Sep 23	2 Girth, connectivity and bipartite graphs	pdf
	Sep 26
	Sep 29	3 Trees	pdf
3	Sep 30
4	Oct 10	4 Circuits	pdf
5	Oct 17	5 Matchings	pdf
	Oct 19
6	Oct 21
	Oct 24
7	Oct 28	6 More on Connectivity	pdf
	Oct 31
8	Nov 4	Midterm Exam
	Nov 7
9	Nov 11
10	Nov 18	7 Coloring	pdf
11	Nov 25
12	Dec 2	8 Planarity	pdf
13	Dec 9	9 Ramsey Theory	pdf
14	Dec 16	Guest Lecture of "Sperner's Lemma, Its Applications, and the Complexity Class PPAD" by Prof. Biaoshuai Tao	pdf
16	Dec 23	Presentation
16	Dec 30	Final Exam