Séminaires : Géométrie et Théorie des Modèles

Equipe(s) : lm,
Responsables :Zoé Chatzidakis, Raf Cluckers, Georges Comte
Email des responsables : zoe.chatzidakis@imj-prg.fr
Salle :
Adresse :
Description

http://gtm.imj-prg.fr/

 

Pour recevoir le programme par e-mail, écrivez à : zoe.chatzidakis@imj-prg.fr
Pour les personnes ne connaissant pas du tout de théorie des modèles, des notes introduisant les notions de base (formules, ensembles définissables, théorème de compacité, etc.) sont disponibles ici : https://webusers.imj-prg.fr/~zoe.chatzidakis/papiers/MTluminy.dvi/MTluminy.dvi. Ces personnes peuvent aussi consulter les premiers chapitres du livre Model Theory and Algebraic Geometry, E. Bouscaren ed., Springer Verlag, Lecture Notes in Mathematics 1696, Berlin 1998.Retour ligne automatique
Les notes de quelques-uns des exposés sont disponibles.

Orateur(s) Pierre Simon - Berkeley,
Titre Monadically NIP ordered graphs and bounded twin-width
Date18/06/2021
Horaire15:00 à 16:30
Diffusion
RésumeAn 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.
Salle
Adresse
© IMJ-PRG