Total Minor Polynomials of Oriented Hypergraphs
MetadataShow full metadata
Concepts of graph theory can be generalized to integer matrices through the use of oriented hypergraphs. An oriented hypergraph is an incidence structure consisting of vertices, edges, and incidences, equipped with three functions: a vertex incidence function, an edge incidence function, and an incidence orientation function. This thesis provides a unifying generalization of Seth Chaiken’s All-Minors Matrix-Tree Theorem and Sachs’ Coefficient Theorem to all integer adjacency and Laplacian matrices – extending the results of Rusnak, Robinson et. al. – by introducing a polynomial in |V|2 indeterminants indexed by minor order whose monomial coefficients are the minors. The coefficients are determined by embedding the oriented hypergraph into the smallest uniform hypergraph that contains it and summing over a class of sub-monic mappings of paths of length one relative to the original oriented hypergraph. It is known that the non-cancellative mappings associated to each degree-1 monomials are in one-to-one correspondence with Tuttes Matrix-Tree Theorem. This is extended to Tuttes k-arborescence decomposition via the degree-k monomials.