On the Expressive Power of Homomorphism Counts

Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu

A classical result by Lovász asserts that two graphs $G$ and $H$ are isomorphic if and only if they have the same left profile, that is, for every graph $F$, the number of homomorp…