A highly successful mathematical research program in model theory (mathematical logic), initiated by Shelah in the 1970s, developed around the classification of theories of infinite structures. It identified properties of theories that make them well-behaved, such as stability and dependence (NIP), and established sharp demarcation lines between such tame theories and wild ones. For many years this line of work was largely concerned with infinite structures as the model theory of individual finite structures is rather trivial. In recent years, however, the model-theoretic notions developed in the context of stability theory have been mined for insight into combinatorial and algorithmic properties of classes of finite structures. Several distinct research communities working in theoretical computer science and in combinatorics have converged on similar notions of tameness of classes of structures. For example,

• strong bounds on Szemeredi's regularity lemma have been established for stable classes of graphs;
• the tractability of the model-checking problem for first-order logic has been tied to stable and dependent classes of finite structures;
• the tractability of the constraint satisfaction problem on infinite templates has been investigated through model-theoretic classification; and
• the behavior of graph limits and other combinatorial limits has been studied for tame classes of finite structures.

The aim of this Dagstuhl Seminar is to bring together members of these distinct research communities to help establish a common language, to exchange ideas on the core notions of tame classes of finite structures, and to develop a common theory to benefit all these communities. A common thread that runs through the variety of notions of tameness introduced in these areas is that a class of structures is tame if it is unable to “encode” arbitrary finite structures. The precise notion of encoding yields different notions of tameness and this encoding generally involves transformation by means of logical formulas, whether they be first-order interpretations, monadic transductions or primitive-positive constructions.

This seminar will feature invited tutorials, contributed talks, a problem session, and a closing session to formulate future research directions. The schedule of the seminar will be developed in such a way that sufficient time will be allowed for informal discussions and the exchange of ideas between participants.

Creative Commons BY 4.0

Anuj Dawar, Phokion G. Kolaitis, Maryanthe Malliaris, and Sebastian Siebertz