In extremal graph theory one tries to understand how global properties
of a graph influence its local substructures. For instance, a
classical result by Turan answers the following question: How many
edges can a graph on *n* vertices have without containing a complete
subgraph on *k* vertices? Another classical topic of extremal graph
theory is Ramsey theory. One of the main goals of this course will be
to cover the Szemeredi regularity lemma, an important tool in modern
discrete mathematics, and to study some of its applications in
combinatorics and computer science. Other topics that will be
introduced are Hadwiger's conjecture, random graphs, and the
probabilistic method.

The course is cross-listed and offered as both CS492 (Special Topics in Computer Science) and MAS480 (Special Topics in Mathematics).

The related course Introduction to Graph Theory (MAS477) is taught in the fall semester by Sangil Oum. We have organized the courses so that taking both courses at the same time would be interesting. Both courses use the same textbook (but cover different parts of it).

The class meets Monday, Wednesday, and Friday from 14:00 to 14:50 in room 3435 in the Natural Sciences Building (E6-1). Lectures are given in English.

Students will be graded based on homeworks (40%), a final exam (40%), and participation (20%). There will be no midterm exam.

There will be a final exam.

The final exam is on December 19, from 14:00 to 16:00, in our usual classroom (room 3435).

We will use the following textbook:

- Reinhard Diestel. Graph theory. 3rd edition, Springer-Verlag 2006. The book is available on-line.

We will also mention a few results from the following book:

- Béla Bollobás. Modern Graph Theory. Springer-Verlag, 1998.

Another new book about graph theory is the following book (we will not use it directly):

- J. A. Bondy, U. S. R. Murty. Graph theory., Springer-Verlag 2008. The book is available on-line as well.

Here is a rough list of what we will cover in each week of the semester. This schedule is somewhat ambitious--don't panic, we will adapt it to the speed of the class!

Week 1 | Introduction and basic concepts |

Week 2 | Subgraphs |

Week 3 | Minors |

Week 4 | Hadwiger's conjecture |

Week 5 | Szemeredi's regularity lemma |

Week 6 | Applications of the regularity lemma |

Week 7 | Ramsey's theorem and Ramsey numbers |

Week 8 | Midterm exam week |

Week 9 | Induced Ramsey theorems |

Week 10 | Ramsey properties and connectivity |

Week 11 | Hamiltonian cycles and degree sequence |

Week 12 | Random graphs |

Week 13 | The probabilistic method |

Week 14 | Properties of almost all graphs |

Week 15 | Review/Reserve |

Week 16 | Final Exam week |

The material covered in the lectures so far:

09-01 | Graphs and degrees | Diestel 1.1, 1.2, Bollobás Lemma IV.21 |

09-03 | Degrees, paths | Bollobás Lemma IV.21, Bollobás Theorem I.2, Diestel 1.3 |

09-05 | Connectivity | Diestel 1.4, Theorem 1.4.3 |

09-08 | Turan's theorem | Diestel 7.1 |

09-10 | A second proof of Turan's theorem | Diestel page 167 |

09-12 | Introduction to the Erdös Stone theorem | Diestel Theorems 7.1.2, 7.1.3, 7.1.4 |

09-15 | Chuseok Holiday | |

09-17 | Review of Homework 1 | |

09-19 | Erdös-Stone Theorem | Bollobás IV.20, Bollobás IV.22 |

09-22 | Hamiltonian graphs, Ore (Posa) Theorem | Diestel Theorem 10.1.1, Bollobás IV.2 |

09-24 | Hamiltonian graphs | Diestel Theorem 10.1.2 |

09-26 | Chvatal's Theorem | Diestel Theorem 10.2.1 |

09-29 | Graph constructions, Disjointness graph | |

10-01 | Review of Homework 2 | |

10-03 | Holiday | |

10-06 | No class | |

10-08 | Minors and topological minors | Diestel 1.7 |

10-10 | High average degree implies a K minor
_{r} | Diestel Lemma 3.5.1 |

10-13 | High girth implies a K minor
_{r} | Diestel Lemma 7.2.3 |

10-15 | No class | |

10-17 | No class | |

10-20 ~ 10-24 Midterm week (no classes) | ||

10-27 | Hadwiger's conjecture for r <= 4 | Diestel Lemmas 4.4.4, 7.3.1, 7.3.3 |

10-29 | Introduction to Ramsey theory and Szemeredi's regularity lemma | |

10-31 | Review of midterm | |

11-03 | Review of midterm, Szemeredi's regularity lemma | |

11-05 | Proof idea of Szemeredi's regularity lemma | |

11-07 | Application of Szemeredi's regularity lemma | |

11-10 | Summary of Chapter 7 | |

11-12 | Introduction to Ramsey theory | |

11-14 | No class | |

11-17 | Review of homework 4 | |

11-19 | König's infinity lemma, Ramsey's original theorem | Diestel Theorems 8.1.2 and 9.1.1 |

11-21 | General Ramsey theorems, Erdös-Szekeres | Diestel Theorems 9.1.2 and 9.1.3 |

11-24 | Ramsey number for graphs with bounded degree | Diestel Theorem 9.2.2 |

11-26 | Induced Ramsey Theorem for bipartite graphs | |

11-28 | Induced Ramsey Theorem | Diestel Theorem 9.3.1 |

12-01 | Random graphs | Diestel Section 12.1 |

12-03 | Review of homework 5 | |

12-05 | Basic notions of probability | Diestel Section 12.1 |

12-08 | The probabilistic method | Diestel Lemma 12.2.1, Theorem 12.2.2 |

12-10 | No class | |

12-12 | No class | |

12-19 | Final exam: 14:00 - 16:00 |

There will be several homework assignments in this course. You will
have about *one week* to complete an assignment. Homeworks must
be submitted *on paper* and must be handed in at the
beginning of class.

- Homework 1: Diestel Chapter 1, problems 2, 9, 11 (only kappa(G), not lambda(G)), and 23. Bonus: Problem 3. Due September 12.
- Homework 2: Diestel Chapter 7, problems 2, 3, 4, 7, 10. Bonus: Problem 13. Due September 29.
- Homework 3 will be a take-home exam. We will post it on October 15, the due date is October 29.
- Homework 4: Diestel Chapter 7, do four out of problems 15, 16, 17, 20, 37. Due November 12.
- Homework 5: Diestel Chapter 9, do four out of problems 5, 6, 8, 9, 10. Due December 1.

We have a bulletin board for announcements and discussions. You can also post your questions there. It would be best to use English on the BBS...

Otfried Cheong