Non-Isomorphic Graphs with Cospectral Symmetric Powers

Abstract

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.