기초과학연구원 이산수학그룹
On May 25, 2022, Sebastian Siebertz from the University of Bremen gave an online talk at the Virtual Discrete Math Colloquim on producing a long path by a first-order transduction from a class of graphs of unbounded shrubdepth. The title of his talk was “Transducing paths in graph classes with unbounded shrubdepth“.
Transductions are a general formalism for expressing transformations of graphs (and more generally, of relational structures) in logic. We prove that a graph class C can be FO-transduced from a class of bounded-height trees (that is, has bounded shrubdepth) if, and only if, from C one cannot FO-transduce the class of all paths. This establishes one of the three remaining open questions posed by Blumensath and Courcelle about the MSO-transduction quasi-order, even in the stronger form that concerns FO-transductions instead of MSO-transductions.
The backbone of our proof is a graph-theoretic statement that says the following: If a graph G excludes a path, the bipartite complement of a path, and a half-graph as semi-induced subgraphs, then the vertex set of G can be partitioned into a bounded number of parts so that every part induces a cograph of bounded height, and every pair of parts semi-induce a bi-cograph of bounded height. This statement may be of independent interest; for instance, it implies that the graphs in question form a class that is linearly chi-bounded.
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“.
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.