Sebastian Siebertz gave a talk on recent approaches to combine model theoretic and graph theoretic tools to derive structural and algorithmic results for classes of (finite) graphs at the Virtual Discrete Math Colloquium

On September 10, 2020, Sebastian Siebertz from University of Bremen gave an online talk about recent attempts to combine the model theory to the theory of dense graphs at the Virtual Discrete Math Colloquium. The title of his talk was “Rank-width meets stability“.

Sebastian Siebertz, Rank-width meets stability

Forbidden graph characterizations provide a convenient way of specifying graph classes, which often exhibit a rich combinatorial and algorithmic theory. A prime example in graph theory are classes of bounded tree-width, which are characterized as those classes that exclude some planar graph as a minor. Similarly, in model theory, classes of structures are characterized by configurations that are forbidden as logical interpretations or transductions. Two notions from classical model theory are (monadic) stability and (monadic) dependence, which correspond to the impossibility of interpreting with first-order logic (after a vertex coloring step) arbitrary long linear orders and all graphs, respectively.  Examples of monadically stable classes of graphs are nowhere dense graph classes, and examples of monadically dependent classes are classes of bounded rank-width (or equivalently, bounded clique-width), which can be seen as a dense analog of classes of bounded tree-width.

I will give an overview over recent approaches to combine model theoretic and graph theoretic tools to derive structural and algorithmic results for classes of (finite) graphs. I assume no background from logic.