On monadically stable and monadically NIP classes of graphs

Prelegent(ci)

Szymon Toruńczyk

Afiliacja

MIM UW

Termin

19 października 2022 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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.

---