Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIncidence hypergraphs: The categorical inconsistency of set-systems and a characterization of quiver exponentials
69
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
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.
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.
When working with distant collaborators on the same documents, one often uses a version control system, which is a program tracking the history of files and helping importing modifications brought by others as patches. The implementation of such a system requires to handle lots of situations depending on the operations performed by users on files, and it is thus difficult to ensure that all the corner cases have been correctly addressed. Here, instead of verifying the implementation of such a system, we adopt a complementary approach: we introduce a theoretical model, which is defined abstractly by the universal property that it should satisfy, and work out a concrete description of it. We begin by defining a category of files and patches, where the operation of merging the effect of two coinitial patches is defined by pushout. Since two patches can be incompatible, such a pushout does not necessarily exist in the category, which raises the question of which is the correct category to represent and manipulate files in conflicting state. We provide an answer by investigating the free completion of the category of files under finite colimits, and give an explicit description of this category: its objects are finite sets labeled by lines equipped with a transitive relation and morphisms are partial functions respecting labeling and relations.
We propose a categorical foundation for the connection between pure and mixed states in quantum information and quantum computation. The foundation is based on distributive monoidal categories. First, we prove that the category of all quantum channels is a canonical completion of the category of pure quantum operations (with ancilla preparations). More precisely, we prove that the category of completely positive trace-preserving maps between finite-dimensional C*-algebras is a canonical completion of the category of finite-dimensional vector spaces and isometries. Second, we extend our result to give a foundation to the topological relationships between quantum channels. We do this by generalizing our categorical foundation to the topologically-enriched setting. In particular, we show that the operator norm topology on quantum channels is the canonical topology induced by the norm topology on isometries.
A family ${A_{0},ldots,A_{d}}$ of $k$-element subsets of $[n]={1,2,ldots,n}$ is called a simplex-cluster if $A_{0}capcdotscap A_{d}=varnothing$, $|A_{0}cupcdotscup A_{d}|le2k$, and the intersection of any $d$ of the sets in ${A_{0},ldots,A_{d}}$ is nonempty. In 2006, Keevash and Mubayi conjectured that for any $d+1le klefrac{d}{d+1}n$, the largest family of $k$-element subsets of $[n]$ that does not contain a simplex-cluster is the family of all $k$-subsets that contain a given element. We prove the conjecture for all $kgezeta n$ for an arbitrarily small $zeta>0$, provided that $nge n_{0}(zeta,d)$. We call a family ${A_{0},ldots,A_{d}}$ of $k$-element subsets of $[n]$ a $(d,k,s)$-cluster if $A_{0}capcdotscap A_{d}=varnothing$ and $|A_{0}cupcdotscup A_{d}|le s$. We also show that for any $zeta nle klefrac{d}{d+1}n$ the largest family of $k$-element subsets of $[n]$ that does not contain a $(d,k,(frac{d+1}{d}+zeta)k)$-cluster is again the family of all $k$-subsets that contain a given element, provided that $nge n_{0}(zeta,d)$. Our proof is based on the junta method for extremal combinatorics initiated by Dinur and Friedgut and further developed by Ellis, Keller, and the author.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
