Algebraic Graph Theory Seminar - David Roberson

Title: What do graph planarity and homomorphism counts have to do with quantum mechanics?

Abstract:

I will introduce the notion of quantum isomorphisms of graphs. These are defined in terms of a game in which two cooperating players attempt to convince a referee that two given graphs are isomorphic. Classically, the players can achieve this with probability 1 if and only if the graphs are indeed isomorphic. However, if the players are allowed to perform local quantum measurements on a shared entangled state, then for some pairs of non-isomorphic graphs they are still able to convince the referee with probability 1. We say that such graphs are quantum isomorphic. After introducing this notion I will discuss the recent result of myself and Mancinska where we show that two graphs are quantum isomorphic if and only if they admit the same number of homomorphisms from any *planar* graph. This can be seen as a quantum analog of Lovasz' result from 1967 saying that two graphs are isomorphic if and only if they admit the same number of homomorphisms from any graph.