Time: 15:00-
Abstract: Let C be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Los-Tarski Theorem from classical model theory implies that
(*) C is definable in first-order logic (FO) if and only if C has a finite set of forbidden induced subgraphs.
In this talk I will discuss some applications of (*) and its limitations. Among others:
- Any class of graphs of bounded tree-depth can be characterized by a finite set of forbidden subgraphs. Our proof differs from the original proof of [Ding, 1992] by circumventing the machinery of well-quasi ordering.
- The forbidden subgraphs can be arbitrarily complex (e.g., not computable) compared to the FO-sentence defining the class C.
This is joint work with Joerg Flum.