Date of Award
Open Access Dissertation
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.
Clark, G. J.(2019). On the Characteristic Polynomial of a Hypergraph. (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/5132
Available for download on Tuesday, May 11, 2021