565
TuTh 11:30AM - 1:00PM, 224 Denn
Homework:
problem set 1, due 9/17
problem set 2, due 9/24
problem set 3, due 10/1
problem set 4, due 10/8
problem set 5, due 10/22
problem set 6, due 10/29
problem set 7, due 11/12
problem set 8, due 11/24
problem set 9, optional
Links: "Random walks and electrical networks", by Doyle and Snell.
A tentative syllabus:
Graphs:
- Kuratowski's lemma
- graph colorings
- spanning trees
- electrical networks
Computation:
- basics of NP-hardness
Flows and posets:
- MINCUT-MAXFLOW
- Menger and Dilworth theorems
- Sperner theorem
Matchings:
- Hall marriage theorem
- stable marriage problem
Probabilistic method:
- Ramsey theory
- linearity of expectation
Random processes:
- coupon collector's problem
- basics of Markov chains
Text:
B. Bollobas, Modern graph theory, Springer, 2002.