English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Over 50 years ago, Lov\'{a}sz proved that two graphs are isomorphic if andonly if they admit the same number of homomorphisms from any graph [Acta Math.Hungar. 18 (1967), pp. 321--328]. In this work we prove that two graphs arequantum isomorphic (in the commuting operator framework) if and only if theyadmit the same number of homomorphisms from any planar graph. As there existpairs of non-isomorphic graphs that are quantum isomorphic, this implies thathomomorphism counts from planar graphs do not determine a graph up toisomorphism. Another immediate consequence is that determining whether thereexists some planar graph that has a different number of homomorphisms to twogiven graphs is an undecidable problem, since quantum isomorphism is known tobe undecidable. Our characterization of quantum isomorphism is proven via acombinatorial characterization of the intertwiner spaces of the quantumautomorphism group of a graph based on counting homomorphisms from planargraphs. This result inspires the definition of "graph categories" which areanalogous to, and a generalization of, partition categories that are the basisof the definition of easy quantum groups. Thus we introduce a new class of"graph-theoretic quantum groups" whose intertwiner spaces are spanned by mapsassociated to (bi-labeled) graphs. Finally, we use our result on quantumisomorphism to prove an interesting reformulation of the Four Color Theorem:that any planar graph is 4-colorable if and only if it has a homomorphism to aspecific Cayley graph on the symmetric group $S_4$ which contains a completesubgraph on four vertices but is not 4-colorable.

Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs