time/place: Tu-Th 2:30-3:50
instuctor: Prof. Rich Schwartz
my office hours: W 11-12, Th 4-5
midterm: Wed 23 March, 6-9 PM (room TBA)
This is an upper level course on graph theory. The
class will cover some classic theorems in graph
theory and also discuss connections to other
areas of mathematics such as geometry,
topology, and probability.
text: Introduction to Graph Theory (2nd ed.)
by Douglas B. West
grading: Your grade is based on 3 components:
in-class midterm: 30%
in-class final exam: 40%
The exams will be somewhat unusual in that I
will reserve a lot of time for them, like 3-4
hours each, so as to give you plenty of
time to do it. I don't want give a take-home
exam with such a big class but on the
other hand I don't want there to be
time pressure on the exams.
homework: I will assign homework each
and collect it the following Tuesday. No late HW.
Click here for the assignments.
To some extent I will follow the book, but
not in order. When a topic is not covered
in the book, I'll write notes about it.
If the syllabus runs out before the end
of the class, I'll fill in with some of the
additional topics mentioned at the end.
Matching and Coloring
- 5-Color Theorem
- The Ramsey Theorem
- chromatic number of a graph
- Brooks' Theorem
- The Chromatic Polynomial
- Perfect and Maximum Matchings
- Hall's Marriage Theorem
Possible Additional Topics
- Max Flow Min Cut
- circle packings
- Frieze patterns
- mechanical linkages
- Kastelyn's Formula for perfect matchings