Ordered graphs of bounded twin-width

Speaker(s)

Szymon Toruńczyk

Affiliation

MIM UW

Date

March 3, 2021, 2:15 p.m.

Information about the event

online

Seminar

Seminar Automata Theory

---

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é.

---