Extremal graph theory

elective monographs

Discrete mathematics 1000-212bMD

The course gives an introduction to extremal graph theory, a branch of graph theory which studies how global parameters of a graph, such as its edge density or chromatic number, can influence its local substructures (for instance, how many edges can a graph on n vertices have without containing a triangle).

After introducing the basic results and tools of the subject, the course will focus on the celebrated Szeméredi regularity lemma and its applications, and in the last part of the lecture we will introduce modern and interesting theory of graph limits.

Note: Course is given in English.

Basic results, such as Mantel’s theorem, Turán’s theorem, König’s theorem, Dirac’s theorem (2 lectures).

Erdös-Stone-Simonovits theorem (1 lecture).

Probabilistic tools in extremal graph theory (2 lectures).

Szeméredi regularity lemma: statement and proof, basic applications, Counting lemma, Triangle removal lemma, Roth’s theorem, basic application in property

testing, other regularity lemmas (4-5 lectures).

Graph limits: introduction and motivation, convergence of graphs, necessary tools from mathematical analysis, graphons, compactness of the space of graphons, relationship to extremal problems (4-5 lectures).

Lecture notes provided by the lecturer

“Graph theory”, Chapter 7, Reinhard Diestel

“Extremal graph theory”, Béla Bollobás

“Large networks and graph limits”, László Lovász

Research articles provided by the lecturer

Besides acquiring the knowledge of standard results and tools of extremal theory, the student knows the regularity lemma and its applications and has basic working knowledge of graph limits.

Oral exam.

The course can provide credit for doctoral students as a "methodological course". In that case, there is an additional requirement for passing the course: the student should correctly solve at least one of the selected problems given by the lecturer, or study and present a research paper assigned by the lecturer.