Lovasz-type theorems and game comonads

Conference item

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.

Authors: Dawar, A; Jakl, T; Reggio, L

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: IEEE
• Host title: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
• Publication date: 2021-07-07
• Acceptance date: 2021-04-01
• Event title: 36th Annual Symposium on Logic in Computer Science
• Event location: Virtual Event
• Event website: http://easyconferences.eu/lics2021/
• Event start date: 2021-06-29
• Event end date: 2021-07-02
• DOI: 10.1109/LICS52264.2021.9470609
• EISBN: 978-1-6654-4895-6
• ISBN: 978-1-6654-4896-3
• Language: English
• Keywords: FFR