Twin-width: theory and applications – TWIN-WIDTH

We aim to explore algorithmic and structural questions related to twin-width, a novel graph and matrix invariant, introduced and developed by the team. Twin-width has already led to progress for questions in algorithmic graph theory (such as the complexity of first-order model checking on hereditary classes of binary structures) and combinatorics (for instance, on the growth of hereditary classes of ordered graphs).
Classes with bounded twin-width are rather "orthogonal" to the current organization of graph theory.
They include classes excluding a fixed minor but not bounded-degree graphs, unit interval graphs but not all the interval graphs, as well as some expander classes whereas random cubic graphs almost surely have large twin-width.
The main questions that we will tackle comprise the existence of an approximation algorithm for twin-width, the generalization of the notion to other mathematical objects, fast computations on matrices with bounded twin-width, and revisiting classical problems in combinatorics through the lens of twin-width.