Combinatorial and algorithmic applications of twin-width
In 2020, Kim, Thomassé, Watrigant, and myself introduced an invariant on graphs (and more generally, on binary structures) called twin-width, inspired by a parameter on permutations proposed by Guillemot and Marx on their way to efficiently detect small patterns in permutations. On the one hand, classes of bounded twin-width are quite general as they include, for example, proper minor-closed classes, classes of bounded rank-width, proper permutation classes, some classes of expanders, etc. On the other hand, they allow for a unified treatment in algorithm design (parameterized and approximation algorithms), stuctural properties (strong Erdős-Hajnal, chi-boundedness), enumerative combinatorics (these classes have single-exponential unlabeled growth), finite model theory (preserved by first-order transformations, and characterizations via first-order logic).
A large part of twin-width theory relies on the celebrated Marcus-Tardos theorem. After defining twin-width, and presenting some (non-)examples of classes of bounded_ twin-width, we will see how this theorem yields a characterization via grid-like divisions of the adjacency matrices. We will then detail (some of) the mentioned properties of classes of bounded twin-width. We will also observe that contraction sequences (involved in the definition of twin-width) can be interesting in their own right, as they can characterize classic graph widths, and bring along new ones.
Prerequisites
There are no prerequisites for the course outside basic knowledge in graph theory.
Tentative lecture plan
- Lecture 1: Contraction sequences, twin-width, Marcus-Tardos theorem, mixed minors.
- Lecture 2: Versatile twin-width, small classes, sparsity in classes of bounded twin-width
- Lecture 3: Parameterized and approximation algorithms on graphs of bounded twin-width, component twin-width, other reduced parameters.
- Lecture 4: First-order transductions, twin-decompositions, characterization via permutations and first-order logic.
- Lecture 5: Ordered graphs and matrices, growth jump.
