# The category of hypergraphs as a topos

It seems known that the category of hypergraphs is a topos. I am looking for any reference here, or just a statement of this in the literature, but can't find anything. There is one paper

A category-theoretical approach to hypergraphs, W. Dörfler and D. A. Waller, ARCHIV DER MATHEMATIK, Volume 34, Number 1, 185-192, DOI: 10.1007/BF01224952, 1980

which might contain information about that, but I don't have access to this paper (and it might take some time to get a copy, likely a paper-copy).

With a hypergraph I mean here a triple $(V,E,h)$, where $V$, $E$ are arbitrary sets, while $h$ is a map from $E$ to the set of finite subsets of $V$ (so $V$ is the set of vertices, $E$ the set of hyperedge-labels, and $h$ yields the hyperedge of a hyperedge-label). Morphisms are pairs $a: V \rightarrow V'$, $b: E \rightarrow E'$, which fulfil the usual commutativity condition.

-
What is the terminal object of the category of hypergraphs? I thought at first it should have V = E = 1. But then you need a map from E to the finite powerset of V, that is, you need to choose one of the two subsets of 1. Neither does the job, if I'm understanding correctly. – Tom Leinster Mar 11 '12 at 22:53
The terminal object T is the (labelled) hypergraph with one vertex and two hyperedge labels 0, 1, which are mapped to the two possible subsets of the same size. For every hypergraph G, the vertices must map to the single vertex, while a hyperedge label must map to 0 iff the corresponding hyperedge is empty. So there is exactly one morphism from G to T. – Oliver Kullmann Mar 11 '12 at 23:02
A student showed (with my help) in his PhD thesis that the category of hypergraphs is a topos. I felt that people working with homomorphisms of graphs would know about this. Now I started thinking about publishing the more general results. The category of hypergraphs can also be obtained by Artin glueing of the finite (forward!) powerset endo-functor of SET. Now this functor does not preserve binary products, contradicting Corollary 4.4 in the paper you cited (if F is an endofunctor of a topos, then its Artin glueing is a topos iff F preserves pullbacks). So it seems that Corollary is false. – Oliver Kullmann Mar 11 '12 at 23:25
I have access to the paper, but it does not talk about the fact that this category is a topos, they only construct products and pullbacks and various other things related to graphs and $r$-uniform hypergraphs. And also, they do not have the same definition of hypergraph, their $h$ is a map from $E$ to the set of non empty subsets of $V$ (instead of finite subsets of $V$). – Guillaume Brunerie Mar 11 '12 at 23:29
@Oliver: interesting. The fact that the finite powerset functor fails to preserve binary products doesn't imply that it fails to preserve pullbacks. Nevertheless, I agree that it fails to preserve pullbacks. So something's wrong somewhere. It would be interesting to go through the proof of Cor 4.4 in the case at hand; this should show whether it's Cor 4.4 or the result that hypergraphs form a topos (or both!) that's wrong. – Tom Leinster Mar 12 '12 at 0:09

One can reinterpret a hypergraph as a span-shaped diagram of sets where the left leg of the span is a finite map (meaning, all preimages are finite). Indeed, given a hypergraph, consider the span $$V\leftarrow\lbrace(v,e)\in V\times E\mid v\in h(e)\rbrace\rightarrow E;$$ it is clear that this gives a correspondence.