CS445: Combinatorics

Shanghai Jiao Tong University, Fall 2021

Teaching Staff

	name	email	office hour
Instructor	Shuai Li	shuaili8@sjtu.edu.cn	Mon 7-9 PM Rm 1406-2, Software College
TA	Fang Kong	fangkong@sjtu.edu.cn	Thu 7-9 PM Rm 1119, Software College
TA	Ruofeng Yang	wanshuiyin@sjtu.edu.cn	Tue 7-9 PM Activity Room of No.30 Dormitory Building, West District

News

• HW10 is out and is due on Dec 18. Solution 10 is out.
• HW9 is out and is due on Dec 2. Solution 9 is out.
• The reading project is out and is due on Jan 2.
• The project on entry editing is out and is due on Dec 19.

Course Information

Lecture times

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

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

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 13	1 Introduction and basics	pdf
	Sep 16	2 Girth, connectivity and bipartite graphs	pdf
	Sep 18
2		Mid-Autumn Festival
	Sep 23	3 Trees	pdf
3	Sep 27
	Sep 30	4 Circuits	pdf
4		National Day Holiday
	Oct 9	5 Matchings	pdf
5	Oct 11		Gale-Shapley.gif
	Oct 14
6	Oct 18
	Oct 21	6 Connectivity	pdf
7	Oct 25
	Oct 28	7 Coloring	pdf (updated on Nov 28)
8	Nov 1	Midterm Review	pdf
	Nov 4	Midterm Exam
9	Nov 8
10	Nov 15
11	Nov 22	8 Planarity	pdf (updated on Dec 5)
12	Nov 29
13	Dec 6	9 Ramsey Theory	pdf
14	Dec 13	Final Exam Review	pdf
15	Dec 20	Guest Lecture: Prof. Biaoshuai Tao
16	Dec 27	Final Exam