Graph theory

Course Description: 


Level:  Doctoral 
Course Status:  Elective

Full description: 

Brief introduction to the course:

More advanced concepts, methods and results of combinatorics and graph theory. Main topics: (linear) algebraic, probabilistic methods in discrete mathematics; relation of graphs and hypergraphs; special constructions of graphs and hypergraphs; extremal set families; Ramsey type problems in different structures; Regularity Lemma.

The goals of the course:

The main goal is to study advanced methods of discrete mathematics, and advanced methods applied to discrete mathematics. Problem solving is more important than in other courses!

The learning outcomes of the course:

By the end of the course, students are enabled to do independent study and research in fields touching on the topics of the course. In addition, they develop some special expertise in the topics covered, which they can use efficiently in other mathematical fields, and in applications, as well. They also learn how the topic of the course is interconnected to various other fields in mathematics, and in science, in general.

More detailed display of contents:

Week 1. Colorings of graphs, Brooks’ theorem

Week 2. Triangle-free graphs with high chromatic number  (constructions of Zykov, Myczielski, shift graph)

Week 3. Famous graphs with high chromatic number (Kneser, Tutte), Erdos’ probabilistic proof for existenceof graphs with large girth and large chromatic number

Week 4. Perfect graphs, important examples, weak perfect graph theorem (linear algebraic proof), strong perfect graph theorem without proof

Week 5. Probabilistic and constructive lower bounds on Ramsey numbers

Week 6. Van der Waerden theorem, Hales Jewett theorem, threshold numbers

Week 7. Extremal graphs, Turan’s theorem, graphs with no 4-cycles

Week 8. Bondy-Simonovits theorem on graphs with no 2k-cycle, regularity lemma and its applications

Week 9. Extremal set family problems (basic problems, Sperner theorem, Erdos-Ko-Rado theorem)

Week 10. More advanced probabilistic methods, Lovasz Local Lemma

Week 11. The dimension bound (Fisher’s inequality, 2-distance sets, etc.)

Week 12. Eigenvalues, minimal size regular graphs of girth 5


Reinhard Diestel, Graph Theory, Springer, 1997 or later editions +


Prerequisites: linear algebra