Regularity Lemma
by Daniela Kühn et Deryk Osthus (7 hours)
Lecture notes:
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.
- Caccetta-Häggkvist Conjecture
- Directed path of length twice the minimum outdegree
- Decomposing an even tournament in directed paths
- Linial-Berge path partition duality
- Stable set meeting all longest directed paths
- Arc-disjoint out-branching and in-branching
- Bermond-Thomassen Conjecture
- Arc-disjoint directed cycles in regular directed graphs
- Partitioning planar digraphs into acyclic digraphs
- Woodall's Conjecture
- Alon's Splitting Conjecture
- Seymour's Second Neighbourhood Conjecture
- Monochromatic reachability in edge-colored tournaments
- Burr's conjecture
- Directed analogue of Erdös-Sos Conjecture
- Large acyclic induced subdigraph in a planar oriented graph
- Erdös-Posa property for long directed cycles