论文标题
平滑近似和CSP在有限界限的均匀结构上
Smooth approximations and CSPs over finitely bounded homogeneous structures
论文作者
论文摘要
我们开发了新型的光滑近似机制，并将其应用于确认随机锦标赛一阶还原的CSP二分法猜想，包括随机图在内的各种均匀图以及理由阶的扩展。除了获得这些二分法结果外，我们还展示了我们的新证明技术如何允许统一并显着简化文献中先前的结果。除了最后一个结构外，我们还表征了那些可以通过局部一致性方法解决的CSP，再次使用相同的机械来解决。
We develop the novel machinery of smooth approximations, and apply it to confirm the CSP dichotomy conjecture for first-order reducts of the random tournament, various homogeneous graphs including the random graph, and for expansions of the order of the rationals. Apart from obtaining these dichotomy results, we show how our new proof technique allows to unify and significantly simplify the previous results from the literature. For all but the last structure, we moreover characterize those CSPs which are solvable by local consistency methods, again using the same machinery.
