# 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.

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 16^{n}/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.