Incidence Hypergraphs: Injectivity, Uniformity, and Matrix-tree Theorems

Abstract

An oriented hypergraph is an oriented incidence structure that allows for the generalization of graph theoretic concepts to integer matrices through its locally signed graphic substructure. The locally graphic behaviors are formalized in the subobject classifier of incidence hypergraphs. Moreover, the injective envelope is calculated and shown to contain the class of uniform hypergraphs -- providing a combinatorial framework for the entries of incidence matrices. A multivariable all-minors characteristic polynomial is obtained for both the determinant and permanent of the oriented hypergraphic Laplacian and adjacency matrices arising from any integer incidence matrix. The coefficients of each polynomial are shown to be submonic maps from the same family into the injective envelope limited by the subobject classifier. These results provide a unifying theorem for oriented hypergraphic matrix-tree-type and Sachs-coefficient-type theorems. Finally, by specializing to bidirected graphs, the trivial subclasses for the degree-$k$ monomials of the Laplacian are shown to be in one-to-one correspondence with $k$-arborescences.

arXiv comment27 pages, 10 figures

References in corpus (6)

• An Oriented Hypergraphic Approach to Algebraic Graph Theory
• Spectral Properties of Oriented Hypergraphs
• A Characterization of Oriented Hypergraphic Laplacian and Adjacency Matrix Coefficients
• On Blow-Ups and Injectivity of Quivers
• Oriented Hypergraphic Matrix-tree Type Theorems and Bidirected Minors via Boolean Order Ideals
• Injective Envelopes and Projective Covers of Quivers

Cited by in corpus (6)

• Spectral Theory of Laplace Operators on Oriented Hypergraphs
• Coloring the normalized Laplacian for oriented hypergraphs
• Spectra of hyperstars on public transportation networks
• Incidence Hypergraphs: Box Products & the Laplacian
• Generalizing Kirchhoff laws for Signed Graphs
• Simplification for Graph-like Objects