Regularity Lemma

by Daniela Kühn et Deryk Osthus (7 hours)

Lecture notes:

  1. Introduction to regularity
  2. Regularity for digraphs

Szemeredi’s regularity lemma guarantees a decomposition of an arbitrary dense graph into quasi-random subgraphs. This has turned out to be an invaluable tool in a wide range of areas. In the directed setting, it has been used recently to prove (approximate) versions of several long-standing Hamiltonicity problems, Sumner’s universal tournament conjecture and Kelly’s conjecture on Hamilton decompositions of regular tournaments. In addition to the regularity lemma, a crucial (and new) notion has been that of `robust expansion’.

The aim of the lecture series is to give:

  • An introduction to the Regularity lemma and to robust expansion
  • A fairly detailed account of how to find a Hamilton cycle in a robust expander (which implies best known results on several conjectures in the area)
  • a sketch of some further applications in combination with other tools, e.g. random walks to embed trees in tournaments
  • a brief survey of some outstanding open problems which might be approached in the above way

Flag Algebras

by Dan Kral' and Jean-Sébastien. Sereni (7 hours)

This minicourse will provide introduction to theory of limits of dense graphs and the related framework of flag algebras developed for proving results in extremal combinatorics. Though flag algebras can be applied in more general settings, we will focus on the case of graphs and only hint extensions to other combinatorial structures. We provide simple examples during the course (with additional ones being left as exercises) and survey successful applications to problems in extremal graph theory.

Orientations and colourings of graphs

by Frédéric Havet (5 hours)

Updated lecture notes for this minicourse are available here.

There are several known results that reveal the connection between the colourings of a graph and its orientations. However it seems that there are only the tip of the iceberg. In this course, we survey the most important links between these two notions. The course will also be an opportunity to discuss some useful techniques in graph theory: Combinatorial Nullstellensatz, median orders, Inclusion-Exclusion, ...

Problem sessions

conducted by Stéphane Bessy and Stéphan Thomassé

We list below some of the conjectures that were discussed during the school.

Blix theme adapted by David Gilbert, powered by PmWiki