hypergraph category

Hypergraph categories


A hypergraph category is a monoidal category whose string diagrams are hypergraphs. Recall that in general the vertices of a string diagram correspond to morphisms in a category, and its edges to objects. An ordinary string diagram is a quiver, where the inputs and outputs of a vertex describe objects appearing in a tensor-product decomposition of the domain and codomain of a morphism; each edge is connected to only one vertex as input and one vertex as output because of how morphisms in a category are composed. A hypergraph category allows edges to connect to many vertices as input and many vertices as output, which categorically means that we can compose many morphisms containing an object in their codomain with many morphisms containing that object in their domain.

Hypergraph categories have been reinvented many times and given many different names, such as “well-supported compact closed categories” (Carboni and RSW), “dgs-monoidal categories” (GH), and “spidered/dungeon categories” (Morton). The name “hypergraph category” is more recent (Kissinger and Fong).


A hypergraph category is:

  • a symmetric monoidal category in which
  • each object is equipped with the structure of a special commutative Frobenius algebra, such that
  • the Frobenius algebra structure of any tensor product XYX\otimes Y is induced in the canonical way from those of XX and YY.

Note in particular that we do not require the morphisms of the category to be Frobenius algebra morphisms.


  • The reason for the definition is that if XX is a special commutative Frobenius algebra, then there is a unique morphism X mX nX^{\otimes m}\to X^{\otimes n} induced by the Frobenius algebra structure. It can of course be defined as the mm-ary multiplication followed by the nn-ary comultiplication; the real point is that the special commutative Frobenius axioms ensure that any composite of two such morphisms is again another such morphism. This is what enables the hypergraph string diagrams described informally above.

  • The free hypergraph category on one object is the category of finite sets and isomorphism classes of cospans. This is a decategorification of the fact that the free monoidal category containing a (non-special) commutative Frobenius algebra is the category of 1-dimensional manifolds and isomorphism classes of 2-dimensional cobordisms. More general free hypergraph categories can be constructed using labeled cospans.

  • Note that the special commutative Frobenius algebras are not required to be “extra-special”, meaning that the morphism I=X 0X 0=II = X^{\otimes 0} \to X^{\otimes 0} = I need not be the identity. Thus, the relevant sort of “hypergraphs” can contain “edges not incident to any vertices”. If we add the extra-special condition, the cospans are replaced by “co-relations”, i.e. jointly surjective cospans.


  • Aleks Kissinger, Finite matrices are complete for (dagger-)hypergraph categories, arxiv
  • Brendan Fong, Decorated Cospans, Theory and Applications of Categories, Vol. 30, 2015, No. 33, pp 1096-1120, arxiv
  • Brendan Fong, The Algebra of Open and Interconnected Systems, Ph.D. Thesis, arxiv
  • A. Carboni. Matrices, relations and group representations. J. Algebra, 138(2):497–529, 1991
  • R. Rosebrugh, N. Sabadini, and R. F. C. Walters. Generic commutative separable algebras and cospans of graphs. Th. App. Cat. 15(6):164–177, 2005. online.
  • F. Gadducci, R. Heckel. An inductive view of graph transformation. In “Recent Trends in Algebraic Development Techniques”, Lecture Notes in Computer Science 1376:223–237. Springer–Verlag, Berlin Heidelberg, 1998.
  • J. Morton. Belief propagation in monoidal categories. In B. Coecke, I. Hasuo, P. Panangaden, editors, Quantum Physics and Logic 2014 (QPL 2014), EPTCS 172:262–269.

Created on August 1, 2017 at 03:22:09. See the history of this page for a list of all contributions to it.