On the Characteristic Polynomial of a Hypergraph

We consider the computation of the adjacency characteristic polynomial of a uniform hypergraph. Computing the aforementioned polynomial is intractable, in general; however, we present two mechanisms for computing partial information about the spectrum of a hypergraph as well as a methodology (and in particular, an algo- rithm) for combining this information to determine complete information about said spectrum. The first mechanism is a generalization of the Harary-Sachs Theorem for hypergraphs which yields an explicit formula for each coefficient of the characteristic polynomial of a hypergraph as a weighted sum over a special family of its subgraphs. The second is a mechanism to obtain the eigenvalues of a hypergraph in terms of certain induced subgraphs. We further provide an efficient and numerically stable algorithm which combines this information, the set-spectrum of a hypergraph and its leading coefficients, to determine the multi-set spectrum of the hypergraph. We demonstrate our algorithm by computing the characteristic polynomial of numerous hypergraphs which could not be computed using previous methods