Oriented hypergraphs and generalizing the Harary-Sachs theorem to integer matrices.

Blake Dvarishkis, Josephine Reynes, Lucas J. Rusnak · 2025

Read Oriented hypergraphs and generalizing the Harary-Sachs theorem to integer matrices. by Blake Dvarishkis, Josephine Reynes, Lucas J. Rusnak (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-12271.txt.

Introduction

Blake Dvarishkis and co-authors extend a classic graph theorem to oriented hypergraphs and integer matrices in this 2025 paper. The Harary-Sachs theorem reads a graph's spectrum from its cycle covers. Hypergraphs allow edges that join many vertices at once, widening the stage.

Their incidence-based objects, called contributors, stand in for cycle covers. With them, all minors of a Laplacian-type matrix gain a combinatorial reading. The coefficients of a total-minor polynomial come out of a small set of contributors. The team also prove that grouping contributors by tail type must cancel in set ways. A fresh proof on spectral sameness caps the work. The results link combinatorics to matrix spectra more tightly.

Catalog record

CREATORBlake Dvarishkis, Josephine Reynes, Lucas J. Rusnak
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE43 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-12271

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Oriented hypergraphs and generalizing the Harary-Sachs theorem to integer matrices. Blake Dvarishkis, Josephine Reynes, Lucas J. Rusnak Abstract Incidence-based generalizations of cycle covers, called contributors, extend the Harary-Sachs coefficient theorem for characteristic polynomials of the adjacency matrix of graphs. All minors of the Laplacian resulting from an integer matrix are characterized using their associated oriented hypergraph through a new minimal collection of contributors to produce the coefficients of the total-minor polynomial. We prove that the natural grouping of contributors via tail-equivalence is necessarily cancellative for any contributor family that reuses an edge. We then provide a new combinatorial proof on the non- 0 0 isospectrality of the traditional characteristic polynomials of the Laplacian and its dual. 2020 MSC 05C50 , 05C65 , 05C22 , 05B20 , 15A15 1 Introduction and Background The Harary-Sachs Theorem determines the coefficients for the characteristic polynomial of adjacency matrices of graphs through signed weighted sums of certain subgraphs [ 8 , 13 , 25 ] . A uniform hypergraph generalization by Clark and Cooper appears in [ 4 ] , while a signed graph version for the Laplacian appears in [ 1 ] by Belardo and Simić. These results have since been shown to have a unifying context using oriented hypergraphs associated to any integer matrix using a finer approach needing only signed configurations. An oriented hypergraphic characterization of both the adjacency and Laplacian matrices appears in [ 3 ] , the connection to reclaiming the matrix-tree theorem for both graphs and signed graphs appears in [ 21 ] , generalizing Chaiken from [ 2 ] . Finally, a complete oriented hypergraphic classification of all minors of the adjacency and Laplacian matrices arising from integer matrices appeared in [ 12 ] with the creation of the total-minor polynomial. We prove an improved version of the total-minor polynomial by exhibiting a new smallest class of hypergraphic mapping families necessary to determine all ordered cofactors of the Laplacian. This is accomplished by adapting the techniques from [ 24 ] , which produced a new formula for Hadamard’s Maximum Determinant Problem for \{\pm 1\} -matrices, to the total minor polynomial introduced in [ 12 ] . We also introduce the concept of dual mapping families which allows for a new combinatorial proof that the spectrum for any Laplacian and its dual agree up to non-zero eigenvalues. Moreover, this indicates that similar results do not hold for off-diagonal minors. 1.1 Oriented Hypergraphs The connection between integer matrices and oriented hypergraphs was introduced in [ 17 , 22 ] where signed graphic techniques were applied locally between adjacencies to study the matrix structure through hypergraphic families. This was done by adapting the bidirected graph interpretation of orientations of signed graphs [ 10 , 26 , 27 ] to multi-directed hypergraphs and building on the the concept of balanced matrices [ 5 , 6 , 7 ] to provide new techniques to bridge graph theory and matrix theory. A generalized algebraic hypergraphic theory has since emerged for signed adjacency and Laplacian matrices, including spectral properties [ 9 , 14 , 15 , 16 , 18 ] , characteristic polynomials and minors [ 3 , 12 ] , matrix-tree-type theorems [ 21 , 23 ] , and Hadamard matrices [ 19 , 20 , 24 ] . An oriented hypergraph is a sextuple G=(V,E,I,\varsigma,\omega,\sigma) where V , E and I are the sets of vertices, edges, and incidences, respectively; while \varsigma:I\rightarrow V , \omega:I\rightarrow E , and \sigma:I\rightarrow\{+1,-1\} are the incidence port, attachment, and signing functions, respectively. A value of \sigma(i)=+1 is indicated by an arrow at incidence i entering the vertex, while a value of \sigma(i)=-1 is indicated by an arrow at incidence i exiting the vertex. The incidence dual of an oriented hypergraph G=(V,E,I,\varsigma,\omega,\sigma) is the oriented hypergraph G^{*}=(E,V,I,\omega,\varsigma,\sigma) . Incidence duality is the primary duality for incidence hypergraphs and replaces the line graph. The need for this level of specificity for graph-like objects has been addressed in [ 11 , 12 ] where the categorical deficiencies in both graph and set-system hypergraphs were shown to not be robust enough to examine integer matrices. An oriented hypergraph in which each edge has exactly two attachments is called a bidirected graph . A bidirected graph can be regarded as an orientation of a signed graph where edge e is signed -\sigma(i)\sigma(j) where incidences i and j are the edge-ends of edge e , see [ 10 , 26 , 27 ] for the connection between signed graphs and bidirected graphs. Figure 1 depicts a bidirected graph G_{1} and a “multi-directed” oriented hypergraph G_{2} . Figure 1: Two oriented hypergraphs. Many oriented hypergraphic definitions coincide with their locally-signed-graphic embedding [ 17 , 22 ] . This notion of treating hypergraphs locally as signed graphs was formalized in [ 11 , 12 ] and locally-signed-graphic simply means the oriented hypergraph is studied via the signed adjacencies of a hyperedge. A directed path of length n/2 is a sequence of distinct vertices, edges, and their intermediary incidences \overrightarrow{P}_{n/2}=(a_{0},i_{1},a_{1},i_{2},a_{2},i_{3},a_{3},...,a_{n-1},i_{n},a_{n}) where \{a_{k}\} is an alternating sequence of vertices and edges, and i_{k} is an incidence between a_{k-1} and a_{k} . A path of length n/2 is the set on the directed path of length n/2 sequence. A directed circle is a closed directed path, while a circle will be the set on the directed circle. A directed adjacency of G is an incidence-monic map of \overrightarrow{P}_{1} into G ; that is, it does not reuse an incidence. Due to the nature of the incidence-maps, it is possible for \overrightarrow{P}_{1} to fold back on itself creating a backstep of the form v,i,e,i,v — the number of backsteps correspond to the degree of v . The adjacency sign of a path P is asgn(P)=(-1)^{\lfloor n/2\rfloor}\prod_{k=1}^{n}\sigma(i_{k})\text{,} which is equivalent to taking the product of the signed adjacencies if P is a vertex-path. Returning to Figure 1 we see that every adjacency (edge) in G_{1} is positive as the arrows in a given edge have opposite signs thus -\sigma(i)\sigma(j) is positive — this is most easily seen as the arrows travel coherently through the edge. Signed graphs with all adjacencies positive are indistinguishable from ordinary graphs. An adjacency is negative if the arrows represent the same sign, so they are visually opposing each other in the oriented hypergraph — in G_{2} the (v_{1},v_{3}) -adjacency using edge e_{3} and the (v_{1},v_{2}) -adjacency using edge e_{1} are both negative. The incidence matrix of an oriented hypergraph G is the V\times E matrix \mathbf{H}_{G} where the (v,e) -entry is the sum of \sigma(i) for each i\in I with \varsigma(i)=v and \omega(i)=e . A bidirected graph in which every edge/adjacency is positive is regarded as an orientation of an ordinary graph as they have indistinguishable incidence matrices. The Laplacian matrix of G is defined as \mathbf{L}_{G}:=\mathbf{H}_{G}\mathbf{H}_{G}^{T}=\mathbf{D}_{G}-\mathbf{A}_{G} for all oriented hypergraphs [ 17 ] . Example 1.1.1 The incidence and Laplacian matrices for G_{1} and G_{2} from Figure 1 are as follows: \displaystyle\mathbf{H}_{G_{1}}=\left[\begin{array}[]{ccccc}-1&0&0&-1&-1\\ 1&-1&0&0&0\\ 0&1&1&0&1\\ 0&0&-1&1&0\\ \end{array}\right] \displaystyle\mathbf{H}_{G_{2}}=\left[\begin{array}[]{ccccc}-1&0&1\\ -1&-1&0\\ 1&1&1\\ \end{array}\right] \displaystyle\mathbf{L}_{G_{1}}=\left[\begin{array}[]{ccccc}3&-1&-1&-1\\ -1&2&-1&0\\ -1&-1&3&-1\\ -1&0&-1&2\end{array}\right] \displaystyle\mathbf{L}_{G_{2}}=\left[\begin{array}[]{ccccc}2&1&0\\ 1&2&-2\\ 0&-2&3\end{array}\right] Note that any integer matrix can be regarded as the incidence matrix of an oriented hypergraph with the inclusion of multiple arrows at vertices. It is a

Read the complete text