10
$\begingroup$

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).

By 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 fulfill the usual commutativity condition.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ 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. $\endgroup$
    – Oliver Kullmann
    Commented Mar 11, 2012 at 23:02
  • 2
    $\begingroup$ 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. $\endgroup$
    – Oliver Kullmann
    Commented Mar 11, 2012 at 23:25
  • 3
    $\begingroup$ 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$). $\endgroup$
    – Guillaume Brunerie
    Commented Mar 11, 2012 at 23:29
  • 2
    $\begingroup$ @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. $\endgroup$
    – Tom Leinster
    Commented Mar 12, 2012 at 0:09
  • 2
    $\begingroup$ @OliverKullmann, can you resolve the question? Is the category of hypergraphs a topos? $\endgroup$
    – Tom LaGatta
    Commented Dec 18, 2013 at 15:59

2 Answers 2

Reset to default
5
$\begingroup$

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.

This seems more natural to work with.

The category of sets is a topos. The category of diagrams of some given shape in a topos is itself a topos, so the category of span-shaped diagrams of this sort is again a topos. Imposing finiteness conditions tends not to destroy the property of being a topos, and one can rapidly check that philosophy in this case.

Improve this answer
$\endgroup$
2
  • 8
    $\begingroup$ It seems to me that your spans must also be required to be jointly monic (in addition to the left leg being finite-to-one). That looks like the sort of property that usually takes you from a topos into a quasitopos. $\endgroup$
    – Mike Shulman
    Commented Apr 4, 2012 at 17:36
  • $\begingroup$ +1, for being correct. $\endgroup$
    – James Cranch
    Commented Apr 4, 2012 at 18:23
1
$\begingroup$

According to this presentation:

Will Grilliette and Lucas Rusnak, Natural Generalizations of Graphs Part II: Commas, Topoi, & Homomorphisms, Discrete Mathematics Seminar, Texas State University (2017) DOI:10.13140/RG.2.2.13627.92961

Quote:

The classical categories H of hypergraphs and M of (undirected) multigraphs arise naturally as a comma category using the power-set functor P. However, P is well-known not to preserve limit processes, and both H and M fail to be Cartesian closed as a result, among other issues. On the other hand, the category Q of quivers arises equivalently as both a comma category and a functor category. Consequently, Q can be represented as a topos of presheaves, inheriting a significant amount of structure immediately.

note: quiver = directed multigraph.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .