We investigate structural implications arising from the condition that a given directed graph does not interpret, in the sense of primitive positive interpretation with parameters or orbits, every finite structure. Our results generalize several theorems from the literature and yield further algebraic invariance properties that must be satisfied in every such graph. Algebraic properties of this kind are tightly connected to the tractability of constraint satisfaction problems, and we obtain new such properties even for infinite countably categorical graphs. We balance these positive results by showing the existence of a countably categorical hypergraph that fails to interpret some finite structure, while still lacking some of the most essential algebraic invariance properties known to hold for finite structures.
翻译:我们调查某一定向图表不以参数或轨道的原始正面解释来解释每一有限结构所产生的结构影响。我们的结果概括了文献中的若干理论,并产生了在每个此类图表中必须满足的更多代数变异性。这种代数特性与制约满足问题的可感性紧密相连,我们甚至获得无限可数的绝对图形,也获得了新的此类特性。我们对这些积极结果进行了平衡,我们通过显示存在一个可以计算明确的高音无法解释某些限定结构,同时仍然缺乏已知用于限定结构的一些最基本的代数变异性。