Ordered graphs of bounded twin-width

Prelegent(ci)

Szymon Toruńczyk

Afiliacja

MIM UW

Termin

3 marca 2021 14:15

Informacje na temat wydarzenia

online

Seminarium

Seminarium „Teoria automatów”

---

We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twin-width. In particular, we prove that those are exactly the classes which avoid certain large grid-like structures as induced substructures. From this we derive that the model-checking problem for first-order logic is fixed-parameter tractable over a hereditary class of ordered graphs if, and -- under common complexity-theoretic assumptions -- only if the class has bounded twin-width. We also show that bounded twin-width is equivalent to the NIP property from model theory, as well as the smallness condition from enumerative combinatorics. We prove the existence of a gap in the growth of hereditary classes of ordered graphs. This is joint work with Pierre Simon. Essentially the same results have been obtained independently by Édouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and Stéphan Thomassé.

---