# 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.