一句话：证明无限域 CSP 的两个二分猜想等价，并用轨道增长、Ramsey 性质与线性恒等式给出新结果。
本文研究有限有界齐次结构归约的 CSP 的两个二分猜想：一个断言模型完全核的 CSP 可解性等价于多态克隆在外嵌入下满足非平凡线性恒等式；另一个要求多态克隆连同自然一致性满足非平凡线性恒等式。作者证明多态克隆中的恒等式能约束自同构群的轨道增长，从而证明两猜想等价，并给出仅靠 ω-范畴性不足的反例。进一步，利用齐次结构的 Ramsey 性质在另一条件下得到类似等价，并证明足够大元数且模外嵌入全对称的多态可生成非平凡线性恒等式系统。由此对有理序、随机图与随机偏序的可解归约获得非平凡线性恒等式。最后用幺半群语言给出 ω-范畴结构同态等价于模型完全核的简短新证明。
There exist two conjectures for constraint satisfaction problems (CSPs) of reducts of finitely bounded homogeneous structures: the first one states that tractability of the CSP of such a structure is, when the structure is a model-complete core, equivalent to its polymorphism clone satisfying a certain non-trivial linear identity modulo outer embeddings. The second conjecture, challenging the approach via model-complete cores by reflections, states that tractability is equivalent to the linear identities (without outer embeddings) satisfied by its polymorphisms clone, together with the natural uniformity on it, being non-trivial. We prove that the identities satisfied in the polymorphism clone of a structure allow for conclusions about the orbit growth of its automorphism group, and apply this to show that the two conjectures are equivalent. We contrast this with a counterexample showing that ω-categoricity alone is insufficient to imply the equivalence of the two conditions above in a model-complete core. Taking a different approach, we then show how the Ramsey property of a homogeneous structure can be utilized for obtaining a similar equivalence under different conditions. We then prove that any polymorphism of sufficiently large arity which is totally symmetric modulo outer embeddings of a finitely bounded structure can be turned into a non-trivial system of linear identities, and obtain non-trivial linear identities for all tractable cases of reducts of the rational order, the random graph, and the random poset. Finally, we provide a new and short proof, in the language of monoids, of the theorem stating that every ω-categorical structure is homomorphically equivalent to a model-complete core.
@inproceedings{BartoKOPP17,
title = {The equivalence of two dichotomy conjectures for infinite domain constraint satisfaction problems},
author = {Libor Barto and Michael Kompatscher and Miroslav Olsak and Trung Van Pham and Michael Pinsker},
booktitle = {LICS},
year = {2017},
doi = {10.1109/lics.2017.8005128}
}