Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs
Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs
Over 50 years ago, Lovász proved that two graphs are isomorphic if and only if they admit the same number of homomorphisms from any graph. Other equivalence relations on graphs, such as cospectrality or fractional isomorphism, can be characterized by equality of homomorphism counts from an appropriately chosen class of …