Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIncidence Hypergraphs: Injectivity, Uniformity, and Matrix-tree Theorems
81
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic 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.
rate research
Read More
The box product and its associated box exponential are characterized for the categories of quivers (directed graphs), multigraphs, set system hypergraphs, and incidence hypergraphs. It is shown that only the quiver case of the box exponential can be characterized via homs entirely within their own category. An asymmetry in the incidence hypergraphic box product is rectified via an incidence dual-closed generalization that effectively treats vertices and edges as real and imaginary parts of a complex number, respectively. This new hypergraphic box product is shown to have a natural interpretation as the canonical box product for graphs via the bipartite representation functor, and its associated box exponential is represented as homs entirely in the category of incidence hypergraphs; with incidences determined by incidence-prism mapping. The evaluation of the box exponential at paths is shown to correspond to the entries in half-powers of the oriented hypergraphic signless Laplacian matrix.
This paper considers the difficulty in the set-system approach to generalizing graph theory. These difficulties arise categorically as the category of set-system hypergraphs is shown not to be cartesian closed and lacks enough projective objects, unlike the category of directed multigraphs (i.e. quivers). The category of incidence hypergraphs is introduced as a graph-like remedy for the set-system issues so that hypergraphs may be studied by their locally graphic behavior via homomorphisms that allow an edge of the domain to be mapped into a subset of an edge in the codomain. Moreover, it is shown that the category of quivers embeds into the category of incidence hypergraphs via a logical functor that is the inverse image of an essential geometric morphism between the topoi. Consequently, the quiver exponential is shown to be simply represented using incidence hypergraph homomorphisms.
A $d$-partite hypergraph is called fractionally balanced if there exists a non-negative function on its edge set that has constant degrees in each vertex side. Using a topological version of Halls theorem we prove lower bounds on the matching number of such hypergraphs. These, in turn, yield results on mulitple-cake division problems and rainbow matchings in families of $d$-intervals.
Restrictions of incidence-preserving path maps produce an oriented hypergraphic All Minors Matrix-tree Theorems for Laplacian and adjacency matrices. The images of these maps produce a locally signed graphic, incidence generalization, of cycle covers and basic figures that correspond to incidence-k-forests. When restricted to bidirected graphs the natural partial ordering of maps results in disjoint signed boolean lattices whose minor calculations correspond to principal order ideals. As an application, (1) the determinant formula of a signed graphic Laplacian is reclaimed and shown to be determined by the maximal positive-circle-free elements, and (2) spanning trees are equivalent to single-element order ideals.
We prove the well-known Brown-ErdH{o}s-Sos Conjecture for hypergraphs of large uniformity in the following form: any dense linear $r$-graph $G$ has $k$ edges spanning at most $(r-2)k+3$ vertices, provided the uniformity $r$ of $G$ is large enough given the linear density of $G$, and the number of vertices of $G$ is large enough given $r$ and $k$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
