252-1409-00L  Graph Theory: Advanced Topics

SemesterAutumn Semester 2014
Periodicityyearly recurring course
CourseDoes not take place this semester.
Language of instructionEnglish

AbstractThe course presents advanced techniques in graph theory, giving a mixture of classical and very recent methods. Topics may include
- random graphs: threshold functions and the evolution of random graphs, Achlioptas processes
- regularity lemma
- container method
- expanders
- separators in planar graphs and subexponential algorithms
- tree width
- property testing
ObjectiveUpon successful completion of the course, the students are expected to be familiar with some of the central open problems of modern graph theory and with some of the main tools that were developed in order to tackle these problems. Their understanding of the learned tools is expected to be deep enough for them to apply these tools independently.
Prerequisites / NoticeThis course requires "Graphs and Algorithms" or a similar lecture.

Attending the course without a preceding course on graph theory is possible if the student is willing to do some extra reading and to accept some standard theorems on graphs without proofs.