A model-theoretic characterization of bounded twin-width

Speaker(s)

Szymon Toruńczyk

Affiliation

Uniwersytet Warszawski (MIMUW)

Date

Oct. 21, 2020, 2:15 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

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.

---