Date of Award
Spring 2019
Document Type
Open Access Dissertation
Department
Mathematics
First Advisor
Joshua Cooper
Abstract
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.
Rights
© 2019, Gregory J. Clark
Recommended Citation
Clark, G. J.(2019). On the Characteristic Polynomial of a Hypergraph. (Doctoral dissertation). Retrieved from https://scholarcommons.sc.edu/etd/5132