Non-isomorphic graphs with cospectral symmetric powers (Q2380284)

Summary: The symmetric \(m\)-th power of a graph is the graph whose vertices are \(m\)-subsets of vertices and in which two \(m\)-subsets are adjacent if and only if their symmetric difference is an edge of the original graph. It was conjectured that there exists a fixed \(m\) such that any two graphs are isomorphic if and only if their \(m\)-th symmetric powers are cospectral. In this paper we show that given a positive integer \(m\) there exist infinitely many pairs of non-isomorphic graphs with cospectral \(m\)-th symmetric powers. Our construction is based on theory of multidimensional extensions of coherent configurations.