一句话:提出一个范畴化 Lovász 定理,统一 Weisfeiler-Leman、计数逻辑与树深度等同态计数刻画,并给出模态逻辑新应用。
Lovász 曾证明有限关系结构的同构可由任意有限结构的同态计数刻画,Pultr 随后给出范畴推广。本文提出一种新的范畴表述,适用于具有 pushout 与合适因子分解系统的局部有限范畴。借助 Abramsky 等人的博弈余单子,该定理可导出两类 Lovász 型结果:Dvořák 用树宽不超过 k 的图的同态计数刻画 k 维 Weisfeiler-Leman 等价,以及 Grohe 用树深不超过 k 的图的同态计数刻画带计数一阶逻辑且量词深度为 k 的等价。作者还将该框架应用于模态逻辑中的同态计数,展示其统一性与扩展性。
Lovász (1967) showed that two finite relational structures A and B are isomorphic if, and only if, the number of homomorphisms from C to A is the same as the number of homomorphisms from C to B for any finite structure C. Soon after, Pultr (1973) proved a categorical generalisation of this fact. We propose a new categorical formulation, which applies to any locally finite category with pushouts and a proper factorisation system. As special cases of this general theorem, we obtain two variants of Lovász' theorem: the result by Dvořák (2010) that characterises equivalence of graphs in the k-dimensional Weisfeiler-Leman equivalence by homomorphism counts from graphs of tree-width at most k, and the result of Grohe (2020) characterising equivalence with respect to first-order logic with counting and quantifier depth k in terms of homomorphism counts from graphs of tree-depth at most k. The connection of our categorical formulation with these results is obtained by means of the game comonads of Abramsky et al. We also present a novel application to homomorphism counts in modal logic.