Forbidden Induced Subgraphs and the Łoś–Tarski Theorem
Yijia Chen, Jörg Flum · 2021
LetCbe a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Łoś-Tarski Theorem from classical model theory implies thatCis definable in first-order logic (FO) by a sentence φ if and only ifChas a finite set of forbidden induced finite subgraphs. It provides a powerful tool to show nontrivial characterizations of graphs of small vertex cover, of bounded tree-depth, of bounded shrub-depth, etc. in terms of forbidden induced finite subgraphs. Furthermore, by the Completeness Theorem, we can compute from φ the corresponding forbidden induced subgraphs. Our results (a) and (b) show that this machinery fails on finite graphs. (a)There is a class of finite graphs that is definable in FO and closed under induced subgraphs but has no finite set of forbidden induced subgraphs. (b)Even if we only consider classesCof finite graphs that can be characterized by a finite set of forbidden induced subgraphs such a characterization cannot be computed from an FO-sentence φ that definesCand the size of the characterization cannot be bounded by f(|φ|) for any computable function f.Besides their importance in graph theory, our results also significantly strengthen similar known theorems for arbitrary structures.