# Lov'asz-Type Theorems and Game Comonads

arXiv: https://arxiv.org/abs/2105.03274 · HTML: https://mlsanity.com/paper/2105.03274/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 May 2021.

## Built on by (most cited first, 1 of 1)

- [Structural Node Embeddings with Homomorphism Counts](https://mlsanity.com/paper/2308.15283/) (2023)

## Abstract (arXiv)

Lov'asz (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'asz' theorem: the result by Dvovr'ak (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.