IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

On the Computation of the Characteristic Polynomial of a Hypergraph

  • Sept. 7, 2018
  • 2:30 p.m.
  • LeConte 317R

Abstract

The characteristic polynomial of a k-uniform hypergraph is the resultant of a system of homogeneous equations of degree $k-1$. When $k=2$, the resultant is simply the determinant and this computation can be performed in polynomial time. However, when $k>2$ the resultant is known to be NP-hard to compute in general. We provide an alternative way to determine the characteristic polynomial of a hypergraph by proving that a polynomial is uniquely determined by its roots (with unknown multiplicities) and a particular set of coefficients. This proof can be translated into an algorithm and we further prove that said algorithm is stable for monic polynomials with integer coefficients. We then discuss how the spectrum (without multiplicity) of a hypergraph can be computed using a method of Lu and Man. We further provide a combinatorial formula for the coefficients of the characteristic polynomial of a hypergraph. We demonstrate how these methods, when combined, can determine the characteristic polynomial of the Rowling hypergraph when traditional solvers have failed to do so. We conclude by discussing the software and computational resources used to perform such computations and the current state of computing the characteristic polynomial of the Fano plane. Special thanks will be given to the University of South Carolina Research Cyberinfrastructure program (RCI) for their assistance with high performance computing resources.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC