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.

Available for download on Tuesday, May 11, 2021

Included in

Mathematics Commons

Share

COinS