Abstract
Graph homomorphism has been an important research topic since its introduction [László Lovász, 1967]. Stated in the language of binary relational structures in that paper [László Lovász, 1967], Lovász proved a fundamental theorem that the graph homomorphism function G ↦ hom(G, H) for 01 valued H (as the adjacency matrix of a graph) determines the isomorphism type of H. In the past 50 years various extensions have been proved by Lovász and others [László Lovász, 2006; Michael Freedman et al., 2007; Christian Borgs et al., 2008; Alexander Schrijver, 2009; László Lovász and Balázs Szegedy, 2009]. These extend the basic 01 case to admit vertex and edge weights; but always with some restrictions such as all vertex weights must be positive. In this paper we prove a general form of this theorem where H can have arbitrary vertex and edge weights. An innovative aspect is that we prove this by a surprisingly simple and unified argument. This bypasses various technical obstacles and unifies and extends all previous known versions of this theorem on graphs. The constructive proof of our theorem can be used to make various complexity dichotomy theorems for graph homomorphism effective, i.e., it provides an algorithm that for any H either outputs a Ptime algorithm solving hom(⋅, H) or a Ptime reduction from a canonical #Phard problem to hom(⋅, H).
BibTeX  Entry
@InProceedings{cai_et_al:LIPIcs:2020:11702,
author = {JinYi Cai and Artem Govorov},
title = {{On a Theorem of Lov{\'a}sz that hom(?, H) Determines the Isomorphism Type of H}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {17:117:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11702},
URN = {urn:nbn:de:0030drops117022},
doi = {10.4230/LIPIcs.ITCS.2020.17},
annote = {Keywords: Graph homomorphism, Partition function, Complexity dichotomy, Connection matrices and tensors}
}
Keywords: 

Graph homomorphism, Partition function, Complexity dichotomy, Connection matrices and tensors 
Seminar: 

11th Innovations in Theoretical Computer Science Conference (ITCS 2020) 
Issue Date: 

2020 
Date of publication: 

10.01.2020 