Spectra of uniform hypergraphs

2011/06/23 by Joshua Cooper, Aaron Dutle, Cooper, Joshua +1 · 20 citations
Computer Science · Mathematics · #Adjacency list #Algebra over a field #Algebra representation #Combinatorics #Context (archaeology) #Discrete mathematics #Eigenvalues and eigenvectors #Graph #Graph theory #Hypergraph #Jordan algebra #Line graph #Mathematics #Matrix Theory and Algorithms #Multilinear algebra #Multilinear map #Physics #Polynomial and algebraic computation #Pure mathematics #Spectral graph theory #Spectral theory #Tensor decomposition and applications #Voltage graph #math.AC #math.CO #math.SP #msc:05C65 #msc:15A18 #msc:15A69

paper · pdf · doi:10.1016/j.laa.2011.11.018

published in Linear Algebra and its Applications 436(9), 3268-3292 (Elsevier BV) · 32 pages, no figures

arxiv created 2011/10/26 · arxiv updated 2011/10/27 · openalex publication_date 2011/12/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We present a spectral theory of hypergraphs that closely parallels Spectral Graph Theory. A number of recent developments building upon classical work has led to a rich understanding of "hyperdeterminants" of hypermatrices, a.k.a. multidimensional arrays. Hyperdeterminants share many properties with determinants, but the context of multilinear algebra is substantially more complicated than the linear algebra required to address Spectral Graph Theory (i.e., ordinary matrices). Nonetheless, it is possible to define eigenvalues of a hypermatrix via its characteristic polynomial as well as variationally. We apply this notion to the "adjacency hypermatrix" of a uniform hypergraph, and prove a number of natural analogues of basic results in Spectral Graph Theory. Open problems abound, and we present a number of directions for further study.

Citations

• Spectra of Hypergraphs and Applications
• Perron–Frobenius theorem for nonnegative multilinear forms and extensions

Cited by

• Line Multigraphs of General Hypergraphs
• On spectral hypergraph theory of the adjacency tensor
• The Spectral Theory of Tensors (Rough Version)
• Tensor Spectral Stability for Uniform Hypergraphs with Bounded Matching Number
• The k-core of a graph and its high-order spectra
• New linear invariants of hypergraphs
• Quantum hypergraph states: a review
• Spectral characterizations of local structures of graphs and hypergraphs
• Non-Markovian heat flows on directed hypergraphs
• Perron-Frobenius theorem for dual tensors and its applications
• On the Estrada Index and Spectral Properties of k-Uniform Hypergraphs
• The ordering of hypertrees and unicyclic hypergraphs by the traces of A_α-tensor
• The characteristic polynomial of sunflowers
• An α-triangle eigenvector centrality of graphs
• Lexicographical ordering by spectral moments of bicyclic hypergraphs
• Spectral radius and Hamiltonicity of uniform hypergraphs
• Quasi-Irreducibility of Nonnegative Biquadratic Tensors
• Re-imagining Spectral Graph Theory
• The characteristic polynomials of r-uniform hypercycles with length l
• Perfect Clustering in Nonuniform Hypergraphs

Related

• Spectral Theory of Hypergraphs: A Survey
• New matrices for spectral hypergraph theory, I
• Adjacency Spectra of Random and Uniform Hypergraphs
• New matrices for spectral hypergraph theory, II
• Analytic methods for uniform hypergraphs