Alladi Ramakrishnan Hall

Classifying Graphs by Counting Homomorphisms

Gaurav Rattan

RWTH, Germany

There exist a wide variety of equivalence relations on graphs, the strictest being graph isomorphism, arising from diverse disciplines such as algebraic graph theory, finite model theory, and spectral graph theory. Each such equivalence induces a classification of graphs based on some discipline-specific notion of structural similarity. The recent work on graph learning, in particular supervised graph classification, has motivated the need for a systematic study of this landscape.

Lovász (1967) showed that two graphs G and H are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e., for every pattern graph F, the number of homomorphisms from F to G equals the number of homomorphisms from F to H. Homomorphism indistinguishability over restricted classes of pattern graphs has recently emerged as a surprisingly powerful framework for capturing diverse range of equivalence relations on graphs.

In this talk, we present a unified algebraic framework for proving such Lovasz-type theorems for restricted classes of pattern graphs. This is based on joint work with Martin Grohe and Tim Seppelt (ICALP 2022 and SODA 2023).