Special Topics in Mathematics (MAS480)

Special Topics in Computer Science (CS492)

Extremal graph theory

Fall Semester 2008

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).


Andreas Holmsen (Office: E3-1 3439, Phone: 3582) and Otfried Cheong (Office: E3-1 3434, Phone: 3542).


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.

Grading policy

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:

This book is available in the library. There are also two copies in the reading room (room 1505) in the Natural Sciences Building.

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

Course progress

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.

Bulletin board

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