On a theorem of Lovász that (, H) determines the isomorphism type of H

DOI10.1145/3448641MaRDI QIDQ5065633zbMATH OpenOpenAlexFDO

Authors Jin-Yi Cai, Artem Govorov

Publication date 22 March 2022

Published in ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3448641

zbMATH Keywords

tensorsgraph homomorphismpartition functioncomplexity dichotomyconnection matrices

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Recommendations

• Graph homomorphisms with complex values: a dichotomy theorem (extended abstract)
• A decidable dichotomy theorem on directed graph homomorphisms with non-negative weights
• On recognizing graphs by numbers of homomorphisms
• Counting homomorphisms and partition functions
• Graph homomorphisms with complex values: a dichotomy theorem

Cited in

(6)

• Undecidability of polynomial inequalities in weighted graph homomorphism densities
• On recognizing graphs by numbers of homomorphisms
• Planar \#CSP equality corresponds to quantum isomorphism -- a Holant viewpoint
• Perfect matchings, rank of connection tensors and graph homomorphisms
• Equality on all \#CSP instances yields constraint function isomorphism via interpolation and intertwiners
• scientific article; zbMATH DE number 1124068 (Why is no real title available?)

This page was built for publication: On a theorem of Lovász that \((\cdot, H)\) determines the isomorphism type of \(H\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5065633)