| Week 1: |
Reading: Notes
on Stable Marriages by Kevin Wayne |
|
| Wednesday, January 10th |
Introduction. Stable
marriages.
|
|
| Friday, January 12th |
Stable marriages continued.
Review of basics of Graph Theory. Notes
|
|
| Week 2: |
Reading: Notes
on Hall's theorem and some applications by Allen Van
Gelder |
|
| Wednesday, January 17th |
Matchings in bipartite
graphs. Hall's theorem. |
|
| Friday, January
19th |
Edge
coloring bipartite graphs.
|
|
| Week 3: |
Reading: Notes
on Matching markets by David Easley and Jon
Kleinberg |
|
| Wednesday,
January 24th |
Vertex covers, Konig's
theorem
|
|
| Friday, January
26th |
Matching
markets.
|
|
| Week 4: |
Reading: For planar
graphs: Matousek and Nesetril, Chapter 5. For the art
gallery problem: Aigner and Ziegler, Chapter 26. |
|
| Wednesday, January
31st |
Planar graphs: Euler's
Formula, platonic solids.
|
|
| Friday, February
2nd |
The 5-color theorem; the
Art Gallery problem.
|
|
| Week 5: |
Reading: Notes
on Fary's theorem by Will Evans. For Graph minors
and Kuratowksi's theorem see pages 35, 40-43 of these
notes. |
|
Wednesday,
February 7th
|
Fary's theorem, Graph
Minors, Hadwiger's conjecture.
|
|
Friday, February
9th
|
Kuratowski's theorem,
Menger's Theorem.
|
|
| Week 6: |
|
|
| Wednesday, February
14th |
Discrete probability: quiz;
introduction.
|
|
| Friday,
February 16th |
MIDTERM |
|