Dreier, J. N. (2024, September 9). The combinatorics of monadic stability, monadic dependence, and related notions [Presentation]. Algomanet - fall 2024, Warschau, Poland. http://hdl.handle.net/20.500.12708/207970
Algorithmic Meta-Theorems are results that solve whole families of algorithmic problems on well-behaved classes of instances. The tractable instances are usually described using graph theory, and the families of algorithmic problems are typically described in terms of logic. In this context, we say a graph class is "tractable" if the first-order model-checking problem is FPT (fixed-parameter tractable) on this class. More precisely, a graph class C is "tractable" if there is an algorithm that decides for a given graph G from C and a sentence ɸ of first-order logic, in time f(ɸ)⋅|G|c if ɸ holds on G (where c is a small constant independent of G and ɸ). Landmark results show that nowhere dense graph classes, hereditary stable classes, and classes of ordered graphs of bounded twin-width are tractable.
The central conjecture in the field is that for hereditary graph classes (those closed under induced subgraphs), a graph class is tractable if and only if it is "dependent". Here, "dependence" refers to a very general notion originating from model theory, where it is usually considered in the infinite. In this course, I will introduce an ongoing program that aims to prove the central conjecture by first rediscovering dependence (and related notions) as purely combinatorial, finitary, graph-theoretic concepts, and then using these concepts to develop a model-checking algorithm.
In this context, most relevant approaches were originally developed for nowhere dense graph classes, then generalized to stable graph classes, and finally extended to dependent classes. Similarly, we start this course by exploring nowhere dense classes, then stable classes, and finally dependent classes.