On monadically stable and monadically NIP classes of graphs

Speaker(s)

Szymon Toruńczyk

Affiliation

MIM UW

Date

Oct. 19, 2022, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

Sparsity theory, initiated by Ossona de Mendez and Nesetril, identifies those classes of sparse graphs that are tractable in various ways (e.g. from the perspective of the model checking problem for first order logic) as exactly the nowhere dense classes. There is an ongoing effort aimed at generalizing sparsity theory to classes of graphs that are not necessarily sparse. It is conjectured that the relevant notion characterising dense graph classes that are tractable, generalising nowhere denseness, is the notion of monadically NIP classes, introduced by Shelah in model theory. I will survey some recent progress in the understanding of those classes, and of the related monadically stable classes. In particular, monadically NIP classes are a common generalization of the notions of nowhere denseness and of twin-width, introduced recently by Bonnet, Thomasse, and coauthors.

---