一句话：研究图与结构在无法pp解释所有有限结构时被迫满足的代数对称性，推广CSP可解性相关定理并构造无限反例。
本文研究有向图在带参数或轨道的原始正解释（primitive positive interpretation）下不能解释每个有限结构这一条件带来的结构后果。作者证明，此类图必须满足若干代数不变性，推广了文献中已有定理，并把这些性质与约束满足问题（CSP）的可易处理性联系起来；即使对无限可数范畴图，也给出新的代数不变性。作为平衡，作者构造了一个可数范畴超图：它不能解释某个有限结构，却仍缺乏有限结构已知具备的一些最核心代数不变性。这表明有限与无限情形之间存在本质差异。
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.
@inproceedings{BartoBKMP23,
title = {Symmetries of Graphs and Structures that Fail to Interpret a Finite Thing},
author = {Libor Barto and Bertalan Bodor and Marcin Kozik and Antoine Mottet and Michael Pinsker},
booktitle = {LICS},
year = {2023},
doi = {10.1109/lics56636.2023.10175732}
}