# Characteristic Polynomials of Hypergraphs

## Program and Instructions

Aaron Dutle 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.

• Download the file TensorCharpolyPackage.sage (right-click and select "save as"). The from either the SAGE command line or inside a worksheet, type

 load('/pathtofile/TensorCharpolyPackage.sage')

where /pathtofile/ is the directory where you saved the .sage file. After loading, SAGE should print the list of (most of) the available functions with their input paramaters and standard outputs. If you want to know more about what they are actually doing, open up the .sage file in a text editor, and you can read the actual algorithm.

• Download the worksheet Hypergraph Spectra.sws which has the functions typed into the first cell. Open the file with SAGE and execute the first cell, and all of the functions will be available.

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

We 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 Hypergraphs). The data we obtained, as well as some of the run times for computations, are available in spectraresults.pdf.