Categories with hyperedges?

Categories with hyperedges?

[Uwe Egbert Wolter]

Dear all,

Categories can be defined by extending directed multi graphs with
identities and composition.  The underlying directed multi graph of a
small category C is given by the sets C_Mor, C_Obj and the source and
target maps src^C,trg^C:C_Mor -> C_Obj.

Has it ever been investigated what structures arise when we try,
instead, to extend directed multi hypergraphs by identities and
composition? A "directed multi hypergraph" H is thereby given by a set
H_E of edges, a set H_V of vertices and two maps src^H,trg^H:H_E ->
Pow(H_V) from H_E into the power set Pow(H_V) of H_V.

I'm aware of monoidal categories and I would like to know if there is
something else around.

Any comment or reference is welcome

Uwe Wolter


[For admin and other information see: http://www.mta.ca/~cat-dist/ ]

Re: Categories with hyperedges?

[Joachim Kock]

Dear Uwe,

there are the notions of properad and prop.  They are successive
generalisations of operads: for operads the composable
configurations are rooted trees; for properads the composable
configurations are directed graphs required to be connected and
acyclic; for props, connectedness is given up.

Note that in all these cases, as well as in the string diagram
calculus for monoidal categories, the edges are the objects, and
the nodes are the operations.  The (1,1)-operations are just
arrows in the sense of categories.  This is in contrast with the
role graphs play as structures underlying categories.

Properads can be described as algebras for a monad on a category
of presheaves on elementary graphs.  Any (directed) hypergraph
defines a presheaf on elementary graphs, and the properad monad
actually restricts to this subcategory: there is a monad for
properads defined on the category of hypergraphs.

The category of directed graphs embeds in two ways into
hypergraphs: one sending edges to hyperedges, and another
sending edges to (1,1)-nodes (and nodes to hyperedges).  Under
this second embedding, the free-properad monad restricts to the
free-category monad!  In this way hypergraphs provide the
smallest setting in which to unify the dual roles played by
graphs (as contrasted above), and in this way I think one can
say that properads provide an answer to your question (unless
I misunderstand it).

All this is explained in my recent paper

    'Graphs, hypergraphs, and properads', arXiv:1407.3744.

Cheers,
Joachim.


On 25/6/15 14:34, Uwe Egbert Wolter wrote:
  > Dear all,
  >
  > Categories can be defined by extending directed multi graphs with
  > identities and composition.  The underlying directed multi graph of a
  > small category C is given by the sets C_Mor, C_Obj and the source and
  > target maps src^C,trg^C:C_Mor -> C_Obj.
  >
  > Has it ever been investigated what structures arise when we try,
  > instead, to extend directed multi hypergraphs by identities and
  > composition? A "directed multi hypergraph" H is thereby given by a set
  > H_E of edges, a set H_V of vertices and two maps src^H,trg^H:H_E ->
  > Pow(H_V) from H_E into the power set Pow(H_V) of H_V.
  >
  > I'm aware of monoidal categories and I would like to know if there is
  > something else around.
  >
  > Any comment or reference is welcome
  >
  > Uwe Wolter

[For admin and other information see: http://www.mta.ca/~cat-dist/ ]