A model-theoretic characterization of bounded twin-width

Prelegent(ci)

Szymon Toruńczyk

Afiliacja

Uniwersytet Warszawski (MIMUW)

Termin

21 października 2020 14:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium „Teoria automatów”

---

Twin-width is a graph parameter introduced recently in a series of papers by Bonnet, Geniet, Kim, Thomassé, and Watrigant. Among others, classes of bounded twin-width include all proper minor-closed classes, all classes of bounded tree-width or rank-width. We give a model-theoretic characterization of classes of bounded twin-width: a class of finite structures has bounded twin-width if and only if it is a reduct of a class of totally ordered structures which is monadically NIP. No knowledge of model theory will be assumed. In the process of proving the stated equivalence, we show equivalences with several other definitions, some more combinatorial in nature. This is ongoing work with Pierre Simon.

---