You are not logged in | Log in

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.