Click here for all the material that was covered in the course and what you are responsible for

This course is for mathematics, mathematical statistics and computer science graduate students (and of course interested faculty are always welcome).

The course will meet two times a week (2x45 each time) for the second reading period and perhaps part of the third reading period.

The course will give 5 graduate points.

Book: Graph Theory by R. Diestel


This course will give an overview of a number of different topics in modern graph theory; some of the topics will be the following.
1. Matchings
2. Connectivity and Menger's theorem
3. Some planarity theory including Euler's Formula, triangulations, Kuratowski's Theorem.
4. Chromatic number, graph colorings including Thomassen's proof that all planar graphs are 5 list colorable.
5. Ramsey theory.

Three high points of the course are
(i) Introducing the probabilistic method in order to prove Erdos' famous theorem that there exist graphs with arbitrarily large chromatic number and girth (this demonstates the fact that the chromatic number can be greatly affected by "global" rather than "local" behavior).
(ii) Introducing the Szemeredi regularity lemma (a very powerful tool in modern combinatorics) in order to prove the Erdos-Stone theorem. The latter has as a corollary a beautiful theorem in extremal graph theory which tells what edge density in large graphs is required in order to be guaranteed that one contains a fixed given subgraph H (the amazing formula is (f(H)-2)/(f(H)-1) where f(H) is the chromatic number of H).
(iii) We will also apply the Szemeredi lemma to prove Roth's theorem on the existence of arithmetic progressions of length 3 in any set of integers of positive upper density (this was later extended by Szemeredi to arithmetic progressions of any finite length, a conjecture originally due to Erdos and Turan).