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
TO ORDER THE BOOK SEE
http://www.springer-ny.com/supplements/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).