Prerequisites: none.
Synopsis: The course is built to provide students with background in combinatorics. The emphasis is on topics related to other areas, such as optimization, statistical mechanics and computer science. In particular, the course will elaborate on some aspects of graph theory, computational complexity, network flows, matroids, random walks, electrical networks, etc.
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
- Greene-Kleitman invariants
Matchings:
- Hall marriage theorem
- stable marriage problem
- dimer models
Probabilistic method:
- Ramsey theory
- linearity of expectation
- percolation
Matroids:
- optimization and greedy algorithm
Random processes:
- coupon collector's problem
- basics of Markov chains
- random walks on graphs
- sandpile model
Two texts have large overlap with covered topics:
J.H. van Lint and R.M.Wilson, A course in combinatorics, Cambridge University Press, 2001.
B. Bollobas, Modern graph theory, Springer, 2002.
Both are recommended but not required.