Édouard Bonnet, Twin-width and ordered binary structures

The twin-width of a graph G can be defined as the least integer d such that there is a sequence of length |V(G)| of (strictly) coarser and coarser partitions of its vertex set V(G), and every part X of every partition P of the sequence has at most d other parts Y of P with both at least one edge and at least one non-edge between X and Y.  Twin-width is closely tied to total orders on the vertices, and can be extended to general binary structures. We will thus consider the twin-width of ordered binary structures, or if you prefer, matrices on a finite alphabet. This turns out to be key in understanding combinatorial, algorithmic, and model-theoretic properties of (hereditary) classes of those objects. We will see several characterizations of bounded twin-width for these classes. The main consequences in the three domains read as follows.

• Enumerative combinatorics: All the classes of 0,1-matrices with superexponential growth have growth at least n! (in turn resolving a conjecture of Balogh, Bollobás, and Morris on the growth of hereditary classes of ordered graphs).
• Algorithms: First-order model checking of ordered binary structures is tractable exactly when the twin-width is bounded.
• Finite model theory: Monadically-dependent and dependent hereditary classes of ordered binary structures are the same.

In addition we get a fixed-parameter algorithm approximating matrix twin-width within a function of the optimum, which is still missing for unordered graphs.

Joint work with Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé. Similar results have been obtained independently by Pierre Simon and Szymon Toruńczyk.