×

Applications of the Harary-Sachs theorem for hypergraphs. (English) Zbl 1492.05105

Summary: 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.

MSC:

05C65 Hypergraphs
05C31 Graph polynomials

Software:

OEIS

References:

[1] Biggs, Norman, Algebraic Graph Theory, Cambridge Mathematical Library (1993), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0797.05032
[2] Chung, F. R.K.; Graham, R. L.; Wilson, R. M., Quasi-random graphs, Combinatorica, 9, 4, 345-362 (1989) · Zbl 0715.05057
[3] Clark, Gregory J.; Cooper, Joshua N., Stably computing the multiplicity of known roots given leading coefficients, Numer. Linear Algebra Appl., 27, 2, Article e2275 pp. (2020) · Zbl 1513.12004
[4] Clark, Gregory J.; Cooper, Joshua N., A Harary-Sachs theorem for hypergraphs, J. Comb. Theory, Ser. B, 149, 1-15 (2021) · Zbl 1466.05146
[5] Cooper, Joshua; Dutle, Aaron, Spectra of uniform hypergraphs, Linear Algebra Appl., 436, 9, 3268-3292 (2012) · Zbl 1238.05183
[6] Harary, Frank, The determinant of the adjacency matrix of a graph, SIAM Rev., 4, 202-210 (1962) · Zbl 0113.17406
[7] Hu, Shenglong; Huang, Zheng-Hai; Ling, Chen; Qi, Liqun, On determinants and eigenvalue theory of tensors, J. Symb. Comput., 50, 508-531 (2013) · Zbl 1259.15038
[8] Über Teiler, Horst Sachs, Faktoren und charakteristiche Polynome von Graphen, Teil I, 12, 7-12 (1966) · Zbl 0138.19503
[9] Shao, Jia-Yu; Qi, Liqun; Hu, Shenglong, Some new trace formulas of tensors with applications in spectral hypergraph theory, Linear Multilinear Algebra, 63, 5, 971-992 (2015) · Zbl 1310.15042
[10] Sloane, N. J.A., The on-line encyclopedia of integer sequences (2018), published electronically at · Zbl 1439.11001
[11] van Aardenne-Ehrenfest, T.; de Bruijn, N. G., Circuits and Trees in Oriented Linear Graphs, 149-163 (1987), Birkhäuser Boston: Birkhäuser Boston Boston, MA
[12] Veblen, Oswald, An application of modular equations in analysis situs, Ann. Math. (2), 14, 1-4, 86-94 (1912/1913) · JFM 43.0574.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.