论文标题
禁止引起的子图和-tarski定理
Forbidden Induced Subgraphs and the Łoś-Tarski Theorem
论文作者
论文摘要
令$ \ Mathscr C $为一类有限和无限图，在诱导子图下关闭。经典模型理论的众所周知的loś-tarski定理意味着，$ \ mathscr c $在一阶逻辑（fo）中由句子$φ$在一阶逻辑（fo）中可以定义，并且仅当$ \ mathscr c $具有有限的有限诱导的有限有限的有限有限的有限的有限量。它提供了一个强大的工具，可以在禁止诱导的有限子图表方面显示小顶点盖的非平地表征，有限的树深度，有限的灌木深度等。此外，根据完整定理，我们可以从$φ$计算相应的禁止诱导子图。我们表明，这种机械在有限图上失败。 - 有一个有限图的类$ \ Mathscr c $在FO中可以定义，并在诱导子图下关闭，但没有有限的禁止诱导子图。 - 即使我们仅考虑有限图的$ \ mathscr c $，这些图表以有限的诱导子图的特征，也不能从fo-sendence $φ$中计算出这种表征，该$ \ \ m m i \ mathscr c $定义了$ f（|φ）$ for $ f（|φ|）$ forcom $ f $ f（|φ|）$ f $ f。 除了它们在图理论中的重要性外，上述结果还显着增强了任意结构的相似已知结果。
Let $\mathscr C$ be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known Łoś-Tarski Theorem from classical model theory implies that $\mathscr C$ is definable in first-order logic (FO) by a sentence $φ$ if and only if $\mathscr C$ has 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. We show that this machinery fails on finite graphs. - There is a class $\mathscr C$ of finite graphs which is definable in FO and closed under induced subgraphs but has no finite set of forbidden induced subgraphs. - Even if we only consider classes $\mathscr C$ of finite graphs which can be characterized by a finite set of forbidden induced subgraphs, such a characterization cannot be computed from an FO-sentence $φ$, which defines $\mathscr C$, and the size of the characterization cannot be bounded by $f(|φ|)$ for any computable function $f$. Besides their importance in graph theory, the above results also significantly strengthen similar known results for arbitrary structures.
