Document Type
Article
Abstract
The Harary-Sachs theorem for k-uniform hypergraphs equates the codegree-d coefficient of the adjacency characteristic polynomial of a uniform hypergraph with a weighted sum of subgraph counts over certain multi-hypergraphs with d edges. We begin by showing that the classical Harary-Sachs theorem for graphs is indeed a special case of this general theorem. To this end we apply the generalized Harary-Sachs theorem to the leading coefficients of the characteristic polynomial of various hypergraphs. In particular, we provide explicit and asymptotic formulas for the contribution of the k-uniform simplex to the codegree-d coefficient. Moreover, we provide an explicit formula for the leading terms of the characteristic polynomial of a 3-uniform hypergraph and further show how this can be used to determine the complete spectrum of a hypergraph. We conclude with a conjecture concerning the multiplicity of the zero-eigenvalue of a hypergraph.
Digital Object Identifier (DOI)
Publication Info
Published in Linear Algebra and Its Applications, Volume 649, 2022, pages 354-374.
APA Citation
Clark, G. J., & Cooper, J. N. (2022). Applications of the Harary-Sachs theorem for hypergraphs. Linear Algebra and Its Applications, 649, 354–374.https://doi.org/10.1016/j.laa.2022.05.012
Rights
© 2022 The Author(s). Published by Elsevier Inc. This is an open access article under the CC BY license (http://creativecommons.org/licenses/by/4.0/).