The next seminar is on June 11th 2021 at 14:00 (Warsaw time zone) given by Michał Pilipczuk.
| Time | Session |
|---|---|
| 14:00 — 14:05 | — Introduction — |
| 14:05 — 15:20 | Michał Pilipczuk: Introduction to twin-width (part 1) |
| 15:20 — 15:30 | — Discussion — |
| 15:30 — 15:50 | — Break — |
| 15:50 — 17:05 | Michał Pilipczuk: Introduction to twin-width (part 2) |
| 17:05 — 17:25 | — Discussion — |
Abstract
An on-going program in descriptive complexity theory is to understand classes of finite structures that can be considered simple from the point of view of the first order logic FO. Here, simplicity can be understood both in terms of expressive power, and in terms of efficient tractability of the corresponding model-checking problem. This program has been so far understood well in the context of sparse structures, where the notion of nowhere denseness has been identified as the main dividing line. However, we are yet to understand the corresponding notions in the setting of classes of dense, but well-organized structures.
Very recently, Bonnet, Kim, Thomassé, and Watrigant introduced a new parameter called twin-width, which seems to be an important piece of the puzzle. Intuitively, a structure has bounded twin-width if it can be gradually constructed by merging larger and larger pieces so that at every point, every piece has a non-trivial interaction with only a bounded number of other pieces. On one hand, twin-width generalizes the usual notion of tree-likeness for dense structures: cliquewidth. On the other hand, many typical examples of well-behaved classes of sparse, but not tree-like structures, like planar graphs or graphs excluding a fixed minor, have bounded twin-width. Finally, the model-checking problem for FO can be solved in linear fixed-parameter time on every class of bounded twin-width. This convinces us that the new parameter provides a notion of being well-organized for dense structure that is robust with respect to FO.
During the seminar we will give an introduction to the combinatorics of twin-width. After presenting the basic definitions, facts, and connections, we will concentrate on the model-theoretic aspects. In particular we will give an exposition of the linear-time fixed-parameter algorithm for FO model-checking alternative to that given in the work of Bonnet et al.