UnRAVeL-Ringvorlesung: Martin Grohe: Graph Representations Based on Homomorphisms
Dienstag, 10.05.2022
UnRAVeL- Ringvorlesung: Martin Grohe: Graph Representations Based on Homomorphisms
- Dr. rer. nat., Universitätsprofessor Martin Grohe – Lehrstuhl Informatik 7
Abstract
Representations in terms of homomorphism counts provide a surprisingly rich view on graphs with applications ranging from logic to machine learning. 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 graph F, the number of homomorphisms from F to G equals the number of homomorphisms from F to H. Recently, homomorphism indistinguishability over restricted classes of graphs such as bounded treewidth, bounded treedepth and planar graphs, has emerged as a surprisingly powerful framework for capturing diverse equivalence relations on graphs arising from logical equivalences and algebraic equation systems. In this talk, I will introduce an algebraic framework for such results drawing from linear algebra and representation theory. The talk is based on recent joint work with Gaurav Rattan and Tim Seppelt (to appear in ICALP 2022).