Definition of Category of Hypergraphs

418 Views Asked by At

I have a question concerning the definition of Hypergraphs in category theory, which I adopted from "A category-theoretical approach to hypergraphs" by W.Dörfler and D.A.Waller: http://rd.springer.com/article/10.1007%2FBF01224952#page-1

So the definition is as follows:

A hypergraph consists of a triple $X=(V,E,f)$, where $V$ is a vertex-set, $E$ (disjoint from $V$) is the edge set, and $f:E\rightarrow PV-\{\emptyset\}$ is the function which assigns to each edge its (non-empty) set of vertices.

How would this arbitrary hypergraph be represented according to this definition? (please, see the link. cannot include the image due to lack of "reputation")

https://www.dropbox.com/s/98jp9aqakwd2sq1/HG1-eps-converted-to.pdf?dl=0

Also, is there any particular reason for which in category theory hypergraphs are not defined in the following manner: $H=(V,E)$, where $V$ is just enumeration of vertices and $E$ is the set of hyper edges with any cardinality?

For example, the hypergraph I proposed above would be: $V=\{1,2,3,4,5,6,7\}$ and$E=\{\{7\},\{1,2\},\{3,4\},\{3,6\},\{5,6\},\{4,6,7\},\{1,2,3,4\},\}$,

1

There are 1 best solutions below

4
On BEST ANSWER

The difference between the definitions is explained in the first paragraph of section 2: their definition, unlike yours, allows for multiple edges with the same vertex set. So, for a silly example, if $X$ is a set, $x∈X$, and $G_i$ are a bunch of groups acting on $X$, then we could view each group $G_i$ as an edge whose vertex set is the $G_i$-orbit of $x$. Different groups would represent different edges, even if they behaved identically.

Now, when you ask "How would this hypergraph be represented?", in the case of the example you build the answer is boring: since the example you use has at most one edge per set of vertices, we might as well represent an edge by its set of vertices, so we get a silly-looking description: basically the one you give in your final paragraph, together with $f$ being the identity function (since an edge is already a set of vertices).

However, imagine a hypergraph with one point, $x$, and three edges each with one vertex ($x$) each. Then we need to give the different edges separate names, to tell them apart; one possible description of this hypergraph is $$V=\{x\},\quad E=\{A, B, C\},\quad f=\{(A, \{x\}), (B, \{x\}), (C, \{x\})\}.$$ The only vertex is $x$, there are three edges, and each edge has the same underlying set of vertices: $\{x\}$.