论文标题
由禁止同态定义的类的渐近理论
Asymptotic Theories of Classes Defined by Forbidden Homomorphisms
论文作者
论文摘要
我们研究了有限结构的一组$ \ MATHCAL {F} $的一组有限结构类别的一阶理论。如果$ \ MATHCAL {F} $由无方向的图组成，则可以从Kolaitis-Prömel-Rothschild定理中得出这些理论的完整描述，该理论可将其视为特殊情况，其中$ \ Mathcal {f} = \ \ {k_n \} $。有限有限图的有限集$ \ MATHCAL {F} $的相应问题是开放的。我们介绍了由同型禁止有限的$ \ Mathcal {f} $的定向树的$ \ Mathcal {f} $所描述的几乎纯粹的课程理论的完整描述；它们都是$ω$ - 分类。在我们的证明中，我们确定了独立兴趣的结果，即有限挖掘的每个约束满意度问题具有一阶收敛，并且相应的渐近理论可以描述为$ω$ - 分类理论的有限线性组合。
We study the first-order almost-sure theories for classes of finite structures that are specified by homomorphically forbidding a set $\mathcal{F}$ of finite structures. If $\mathcal{F}$ consists of undirected graphs, a full description of these theories can be derived from the Kolaitis-Prömel-Rothschild theorem, which treats the special case where $\mathcal{F} = \{K_n\}$. The corresponding question for finite sets $\mathcal{F}$ of finite directed graphs is wide open. We present a full description of the almost-sure theories of classes described by homomorphically forbidding finite sets $\mathcal{F}$ of oriented trees; all of them are $ω$-categorical. In our proof, we establish a result of independent interest, namely that every constraint satisfaction problem for a finite digraph has first-order convergence, and that the corresponding asymptotic theory can be described as a finite linear combination of $ω$-categorical theories.
