| Week 1: |
Reading: Notes on Stable Marriages by
Kevin Wayne
|
|
| Tuesday, January 12th |
Introduction. Stable marriages.
|
|
| Thursday, January 14th |
Applications of stable marriages. Matchings in bipartite graphs. |
|
| Week 2: |
Reading: Notes on Hall's theorem and some applications by
Allen Van Gelder
|
|
| Tuesday, January 19th |
Hall's theorem.
|
|
| Thursday, January 21st |
Applications of Hall's theorem: Edge-coloring of bipartite graphs, Latin squares. |
|
| Friday, January 22nd |
Review of basics of Graph Theory. Notes |
|
| Week 3: |
Reading: Notes on Matching markets by
David Easley and Jon Kleinberg
|
|
| Tuesday, January 26th |
Systems of distinct representatives. Konig's theorem.
|
|
| Thursday, January 28th |
Matching markets. |
Assignment 1 assigned.
|
| Week 4: |
Reading: For planar graphs: Matousek and Nesetril, Chapter 5. For the art gallery problem: Aigner and Ziegler, Chapter 26.
|
|
| Tuesday, February 2nd |
Planar graphs: Euler's Formula, platonic solids.
|
|
| Thursday, February 4th |
The 5-color theorem; the Art Gallery problem. |
Assignment 1 due.
|
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.
|
|
| Tuesday, February 9th |
Fary's theorem, Graph Minors, Hadwiger's conjecture.
|
Assignment 2 assigned.
|
| Thursday, February 11th |
Kuratowski's theorem, Menger's Theorem. |
|
Week 6: |
|
|
| Tuesday, February 16th |
Discrete probability: quiz; introduction.
|
Assignment 2 due.
|
| Thursday, February 18th |
MIDTERM |
|