Designed and built with care, filled with creative elements

Image Alt

Monadically NIP ordered graphs and bounded twin-width

  /  Évènements
Chargement Évènements
  • Cet évènement est passé



Monadically NIP ordered graphs and bounded twin-width

An open problem in theoretical computer science asks to characterize tameness for hereditary classes of finite structures. The notion of bounded twin-width was proposed and studied recently by Bonnet, Geniet, Kim, Thommasé and Watrignant. Classes of graphs of bounded twin-width have many desirable properties. In particular, they are monadically NIP (remain NIP after naming arbitrary unary predicates). In joint work with Szymon Torunczyk we show the converse for classes of ordered graphs. We then obtain a very clear dichotomy between tame (slow growth, monadically NIP, algorithmically simple …) and wild hereditary classes of ordered graphs. Those results were also obtained by Bonnet, Giocanti, Ossona de Mendez and Thomassé. In this talk, I will focus on the model theoretic input.

- Séminaire Géométrie et théorie des modèles

Détails :

Orateur / Oratrice : Pierre Simon
Date : 18 juin 2021
Horaire : 15h00 - 16h20
Lieu : Zoom