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