565.09

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.