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:
We will also mention a few results from the following book:
Another new book about graph theory is the following book (we will not use it directly):
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 Kr minor | Diestel Lemma 3.5.1 |
| 10-13 | High girth implies a Kr minor | 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.
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...