Characteristic Polynomials of Hypergraphs

Program and Instructions


I wrote a suite of functions for the free and open source SAGE mathematics program to compute the characteristic polynomial of a k-uniform hypergraph.

To use the functions, you must have SAGE installed. From there you have two options.

A note of warning: The characteristic polynomial of a hypergraph is a high degree polynomial (exponential in size of the hyergraph), and the functions for computing it run in exponential time (and space) in the number of vertices. For instance, computing the characteristic polynomial for a 3-uniform hypergraph involves finding the characteristic polynomial of a matrix with about 16n/n entries, which our function stores in memory. So unless you have more than 8 gigabytes of memory, and lots of time to spare, don't try to compute anything on 10 or more vertices. Also, although the functions will take any Hypermatrix as input, they are specially designed for those corresponding to hypergraphs, and so won't compute the characteristic polynomial correctly for anything other than (weighted, non-normalized) adjacency hypermatrices.

Computational Results


I used the functions in the package above to compute the characteristic polynomial for a number of types of hypergraphs (on a small numbers of vertices). This data led to the characterization of the characteristic polynomial for a few classes of hypergraphs (see the paper Spectra of Uniform Hypergraphs). The data we obtained, as well as some of the run times for computations, are available in spectraresults.pdf.