Homomorphism Tensors and Linear Equations
From MaRDI portal
Publication:6507663
DOI10.4230/LIPICS.ICALP.2022.70arXiv2111.11313MaRDI QIDQ6507663FDOQ6507663
Authors: Martin Grohe, Gaurav Rattan, Tim Seppelt 
Abstract: Lov'asz (1967) showed that two graphs and are isomorphic if and only if they are homomorphism indistinguishable over the class of all graphs, i.e. for every graph , the number of homomorphisms from to equals the number of homomorphisms from to . 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 equivalence and algebraic equation systems. In this paper, we provide a unified algebraic framework for such results by examining the linear-algebraic and representation-theoretic structure of tensors counting homomorphisms from labelled graphs. The existence of certain linear transformations between such homomorphism tensor subspaces can be interpreted both as homomorphism indistinguishability over a graph class and as feasibility of an equational system. Following this framework, we obtain characterisations of homomorphism indistinguishability over two natural graph classes, namely trees of bounded degree and graphs of bounded pathwidth, answering a question of Dell et al. (2018).
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Combinatorial aspects of representation theory (05E10) Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76) Algebraic monoids (20M32)
This page was built for publication: Homomorphism Tensors and Linear Equations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507663)
