School

The school consists of four series of lectures:

• Twin-width (by Édouard Bonnet, ENS Lyon)

• Algorithms for H-free graphs (by Marcin Pilipczuk & Paweł Rzążewski, Warsaw)

• Erdős-Hajnal conjecture (by Matija Bucić, Princeton)

• Structurally sparse graphs (by Rose McCarty, Princeton)

Abstracts

Twin-width. 

We will first introduce the graph and matrix parameter twin-width, go through several examples of classes with bounded or unbounded twin-width, and present some useful characterizations of bounded twin-width. We will then survey some algorithmic applications for, and structural properties shared by, graphs of bounded twin-width. Finally we will see that contraction sequences (introduced to define twin-width) can be interesting in their own right, for instance in redefining classic width parameters. The course will be filled with open questions on this still recent topic, as well as easier exercises. 

Algorithms for H-free graphs.

Let H be a fixed path on at least five vertices. The graphs that exclude H as an induces subgraph, i.e., H-fre graphs, admit some strong structural properties that we still do not understand. It has been observed long time ago that we do not know any hardness reduction for the Maximum Independent Set problem (MIS) that does not produce long induced paths, thus MIS could be as well polynomial-time solvable in H-free graphs, for every path H. We actually now conjecture that this is indeed the case thanks to recent progress, including a quasi-polynomial-time algorithm and a QPTAS in a wider class of graphs excluding a fixed tree with three leaves. The tutorial will cover (a) surprisingly simple branching algorithms for MIS, giving quasi-polynomial running time bound in discussed graph classes, (b) approaches to turn these algorithms into polynomial-time algorithms with the help of Potential Maximal Cliques framework, (c) algorithms in wider classes of H-free graphs, where H is a tree with three leaves, using the celebrated three-in-a-tree theorem of Chudnovsky and Seymour.

Erdős-Hajnal conjecture.

The Erdős-Hajnal conjecture is one of the most classical and well-known problems in extremal and structural combinatorics dating back to 1977. It asserts that in stark contrast to the case of a general n-vertex graph if one imposes even a little bit of structure on the graph, namely by forbidding a fixed graph H as an induced subgraph, instead of only being able to find a polylogarithmic size clique or an independent set one can find one of polynomial size. Despite being the focus of considerable attention over the years the conjecture remains widely open. In this tutorial we will go through what is known about this conjecture, in particular we will focus on three recent results: 

1. The proof of the conjecture when H is a cycle on five vertices, 

2. The improvement of the best known lower bound for any H

3. A much more substantial improvement in the smallest open case of H being a path on five vertices.

Structurally sparse graphs.

Structural graph theory has traditionally focused on graph classes that are closed under both vertex- and edge-deletion (such as, for each surface Σ, the class of all graphs which embed in Σ). It is a relatively recent trend to require only closure under vertex-deletion. This is needed to handle graphs with geometric, rather than topological, representations. More generally, it is also the right approach for classes that are dense, rather than sparse (that is, contain graphs with quadratically many edges).

We discuss this paradigm at a broad level. Particular topics include flipping, vertex-minors, and structural sparsity.

Boarding

The organizers provide coffee breaks, but meals and accommodation are not covered. Warsaw is a lively city with many options of housing within various price ranges.

Registration

Participation in the school is free of charge but it requires earlier registration. The registration form can be found here. The number of participants is limited. After filling the registration form, please wait for the confirmation of acceptance.