Algèbre et géométrie

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 […]

I will discuss recent work in collaboration with Edward Bierstone on transformation of a mapping to monomial form (with respect to local coordinates) by simple modifications of the source and target. Our techniques apply in a uniform way to the algebraic and analytic categories, as well as to classes of infinitely differentiable real functions that are quasianalytic or definable in an o-minimal structure. Our results in the real cases are best possible. The talk will focus on real phenomena and on an application to quantifier elimination of certain o-minimal polynomially […]