565.09 - pylyavskyy

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.

"Lectures on discrete and polyhedral geometry" by Pak

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.