Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

• Username
• Password
• Remember me

• Sign in using OpenID
• Remember me

• Forgot your password?
• Apply for membership

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nforum nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf sheaves simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

1. • CommentRowNumber1.
   • CommentAuthorNoam_Zeilberger
   • CommentTimeSep 25th 2015
   • PermaLink
   Author: Noam_Zeilberger
   Format: MarkdownItexI mentioned [here](http://nforum.ncatlab.org/discussion/6764/a-few-stubs-vertex-coloring-bipartite-graph-virtual-knot-theory/#Item_1) that I had made a stub for [[bipartite graph]], and alluded to the fact that there was a small mistake in the original definition which Thomas Holder corrected. For the record, the original definition I wrote was > A **bipartite graph** is a [[graph]] $G$ equipped with a [[vertex coloring|2-coloring]] of its vertices, i.e., equipped with a graph homomorphism $f : G \to K_2$. and then we had this discussion on the page: > Thomas: This is really what you want ? Normally, being bipartite is property of a graph not a structure. As you define it it amounts to being an object in $Grph/K_2$. This might be an ([[étendue]]) topos, presumably equivalent to the slice over $K_2$ of the topos of involutory directed graphs, cf. a related construction in Lawvere 1986 . > Noam: That's a good point. I am changing "equipped with a 2-coloring" to "can be 2-colored", which suggests the property reading (but presumably doesn't entirely rule out the possibility of a structure reading). Thanks for the reference to Lawvere! I recently found a question on mathoverflow about ["the category of hypergraphs as a topos"](http://mathoverflow.net/questions/90940/the-category-of-hypergraphs-as-a-topos), and got to thinking about whether the original definition that I had sloppily suggested for bipartite graphs actually is a good way of defining _hypergraphs_. Specifically, as explained at [[hypergraph]] (and on [Wikipedia](https://en.wikipedia.org/wiki/Hypergraph#Bipartite_graph_model)), any hypergraph can be canonically transformed into a 2-colored graph and vice versa (so long as we admit hypergraphs with empty hyperedges, or alternatively we assume that graphs have no isolated white vertices). But that suggests defining the category of hypergraphs precisely as the slice category $Grph/K_2$ that Thomas mentions above. I believe this is equivalent to the category of hypergraphs Oliver Kullman sketches in that mathoverflow question: a morphism between 2-colored graphs sends black vertices (= hypervertices) to black vertices and white vertices (= hyperedges) to white vertices, while preserving the incidence relation between them. Do people agree?

   I mentioned here that I had made a stub for bipartite graph, and alluded to the fact that there was a small mistake in the original definition which Thomas Holder corrected. For the record, the original definition I wrote was

   A bipartite graph is a graph $G$ equipped with a 2-coloring of its vertices, i.e., equipped with a graph homomorphism $f : G \to K_2$.

   and then we had this discussion on the page:

   Thomas: This is really what you want ? Normally, being bipartite is property of a graph not a structure. As you define it it amounts to being an object in $Grph/K_2$. This might be an (étendue) topos, presumably equivalent to the slice over $K_2$ of the topos of involutory directed graphs, cf. a related construction in Lawvere 1986 .

   Noam: That’s a good point. I am changing “equipped with a 2-coloring” to “can be 2-colored”, which suggests the property reading (but presumably doesn’t entirely rule out the possibility of a structure reading). Thanks for the reference to Lawvere!

   I recently found a question on mathoverflow about “the category of hypergraphs as a topos”, and got to thinking about whether the original definition that I had sloppily suggested for bipartite graphs actually is a good way of defining hypergraphs. Specifically, as explained at hypergraph (and on Wikipedia), any hypergraph can be canonically transformed into a 2-colored graph and vice versa (so long as we admit hypergraphs with empty hyperedges, or alternatively we assume that graphs have no isolated white vertices). But that suggests defining the category of hypergraphs precisely as the slice category $Grph/K_2$ that Thomas mentions above. I believe this is equivalent to the category of hypergraphs Oliver Kullman sketches in that mathoverflow question: a morphism between 2-colored graphs sends black vertices (= hypervertices) to black vertices and white vertices (= hyperedges) to white vertices, while preserving the incidence relation between them.

   Do people agree?

2. • CommentRowNumber2.
   • CommentAuthorNoam_Zeilberger
   • CommentTimeSep 25th 2015
   • PermaLink
   Author: Noam_Zeilberger
   Format: MarkdownItex...but the terminal object in this slice category is just a 2-colored $K_2$, i.e., the hypergraph consisting of one hyperedge incident to one hypervertex, which is different from what Kullmann suggested in the comments. I'm not exactly sure what he meant by "the usual commutativity condition". If $(V,E,h : E \to P(V))$ and $(V',E',h' : E' \to P(V'))$ are hypergraphs in that formulation, then I think the right notion of homomorphism is a pair $(a : V \to V', b : E \to E')$ together with a _2-cell_ $P(a) \circ h \Rightarrow h' \circ b$ rather than an equation. That translates the condition that $f : H \to H'$ is a hypergraph homomorphism if $v \in e$ implies $f(v) \in f(e)$ for all $v,e \in H$.

   …but the terminal object in this slice category is just a 2-colored $K_2$, i.e., the hypergraph consisting of one hyperedge incident to one hypervertex, which is different from what Kullmann suggested in the comments. I’m not exactly sure what he meant by “the usual commutativity condition”. If $(V,E,h : E \to P(V))$ and $(V',E',h' : E' \to P(V'))$ are hypergraphs in that formulation, then I think the right notion of homomorphism is a pair $(a : V \to V', b : E \to E')$ together with a 2-cell $P(a) \circ h \Rightarrow h' \circ b$ rather than an equation. That translates the condition that $f : H \to H'$ is a hypergraph homomorphism if $v \in e$ implies $f(v) \in f(e)$ for all $v,e \in H$.

3. • CommentRowNumber3.
   • CommentAuthorThomas Holder
   • CommentTimeSep 26th 2015
   • (edited Sep 26th 2015)
   • PermaLink
   Author: Thomas Holder
   Format: MarkdownItexIf you take as vertice set of the terminal object $V=\{\ast\}$ and as hyper edge label set $E=\{\empty,\{\ast\}\}$ then Kullmann's assigment function is $h=id_{2^\ast}$ i.e. $id_{K_2}$ = the terminal object of $Grph/K_2$, no !? Concerning the MO discussion, I have a hunch that the category Kullmann had in mind isn't really a topos. At some point the question comes up whether a corollary in what I think must be the Carboni-Johnstone paper on Artin glueing is erroneous. Now in that paper some of the claims were indeed wrong but I don't think the characterization in that corollary was among those because the elephant still believes in that result. Thus your remark on the morphisms is probably on the right track. To elaborate on the last part. The relevant category seems to be the [[Artin gluing]] of $F:Set\to Set$ with $F$ the finite power set functor i.e the suggested hypergraph category is $Set\downarrow F$. The proposed terminal object is $( 1_\mathcal{A},F(1_\mathcal{A}),id:F(1_\mathcal{A})\to{F(1_\mathcal{A})})$ with $\mathcal{A}=Set$ hence $(\{\ast\},\{\empty,\{\ast\}\},id_{\{\empty,\{\ast\}\}})$. This gives a topos iff $F$ preserves pullbacks (elephant I, pp.82,177).

   If you take as vertice set of the terminal object $V=\{\ast\}$ and as hyper edge label set $E=\{\empty,\{\ast\}\}$ then Kullmann’s assigment function is $h=id_{2^\ast}$ i.e. $id_{K_2}$ = the terminal object of $Grph/K_2$, no !?

   Concerning the MO discussion, I have a hunch that the category Kullmann had in mind isn’t really a topos. At some point the question comes up whether a corollary in what I think must be the Carboni-Johnstone paper on Artin glueing is erroneous. Now in that paper some of the claims were indeed wrong but I don’t think the characterization in that corollary was among those because the elephant still believes in that result. Thus your remark on the morphisms is probably on the right track.

   To elaborate on the last part. The relevant category seems to be the Artin gluing of $F:Set\to Set$ with $F$ the finite power set functor i.e the suggested hypergraph category is $Set\downarrow F$. The proposed terminal object is $( 1_\mathcal{A},F(1_\mathcal{A}),id:F(1_\mathcal{A})\to{F(1_\mathcal{A})})$ with $\mathcal{A}=Set$ hence $(\{\ast\},\{\empty,\{\ast\}\},id_{\{\empty,\{\ast\}\}})$. This gives a topos iff $F$ preserves pullbacks (elephant I, pp.82,177).

4. • CommentRowNumber4.
   • CommentAuthorNoam_Zeilberger
   • CommentTimeSep 26th 2015
   • (edited Sep 26th 2015)
   • PermaLink
   Author: Noam_Zeilberger
   Format: MarkdownItexSeen as a 2-colored graph, the terminal object $id_{K_2}$ of $Grph/K_2$ is just the $K_2$ graph with one vertex colored black and one colored white. So viewing it as a hypergraph, it has only one hyperedge, rather than two. As a 2-colored graph, the hypergraph that Kullmann describes is the union of this one together with an isolated white vertex. Just to clarify what I wrote above, by asking for a 2-cell $P(a)\circ h \Rightarrow h'\circ b$ I meant that for every hyperedge $e \in E$, there is an inclusion $P(a)(h(e)) \subseteq h'(b(e))$ (i.e., for all $e \in E$ and $v \in h(e)$, we have $a(v) \in h'(b(e))$). I believe with that definition the category is equivalent to $Grph/K_2$, but I have to check that. Asking for an equality and in particular for the reverse inclusion $P(a)\circ h \supseteq h'\circ b$ would demand that for every hyperedge $e' = b(e)$ which is in the image of the homomorphism, all of the hypervertices $v'$ which are incident to $e'$ are also in the image of the homomorphism $\exists v.v' = a(v)$. That condition doesn't make sense to me as part of the definition of a hypergraph homomorphism, but I will try to find an actual definition somewhere in the literature.

   Seen as a 2-colored graph, the terminal object $id_{K_2}$ of $Grph/K_2$ is just the $K_2$ graph with one vertex colored black and one colored white. So viewing it as a hypergraph, it has only one hyperedge, rather than two. As a 2-colored graph, the hypergraph that Kullmann describes is the union of this one together with an isolated white vertex.

   Just to clarify what I wrote above, by asking for a 2-cell $P(a)\circ h \Rightarrow h'\circ b$ I meant that for every hyperedge $e \in E$, there is an inclusion $P(a)(h(e)) \subseteq h'(b(e))$ (i.e., for all $e \in E$ and $v \in h(e)$, we have $a(v) \in h'(b(e))$). I believe with that definition the category is equivalent to $Grph/K_2$, but I have to check that.

   Asking for an equality and in particular for the reverse inclusion $P(a)\circ h \supseteq h'\circ b$ would demand that for every hyperedge $e' = b(e)$ which is in the image of the homomorphism, all of the hypervertices $v'$ which are incident to $e'$ are also in the image of the homomorphism $\exists v.v' = a(v)$. That condition doesn’t make sense to me as part of the definition of a hypergraph homomorphism, but I will try to find an actual definition somewhere in the literature.

5. • CommentRowNumber5.
   • CommentAuthorThomas Holder
   • CommentTimeSep 26th 2015
   • (edited Sep 27th 2015)
   • PermaLink
   Author: Thomas Holder
   Format: MarkdownItexApparently, I was seduced by the superficial ressemblance between the respective objects. I have no good intuition concerning the hyper-edges or the coloring. But would you agree with the rest, namely that $F$ is the right functor but the resulting category $Set\downarrow F$ is only a quasi-topos, in any case not a topos !? That seems to me the conclusion of the variuos comments on MO. I think that the morphisms in $Set\downarrow F$ are nevertheless bound to yield some reasonable notion of map. [add-corr.: as Todd points out below (#7) there is a result in Johnstone-Lack-Sobocinski that says that $\mathcal{B}\downarrow F$ is a quasitopos for $F:\mathcal{A}\to\mathcal{B}$ between two quasitoposes iff $F$ preserves pullbacks. Hence $Set\downarrow F$ is not even a quasitopos (cf. #6).]

   Apparently, I was seduced by the superficial ressemblance between the respective objects. I have no good intuition concerning the hyper-edges or the coloring. But would you agree with the rest, namely that $F$ is the right functor but the resulting category $Set\downarrow F$ is only a quasi-topos, in any case not a topos !? That seems to me the conclusion of the variuos comments on MO.

   I think that the morphisms in $Set\downarrow F$ are nevertheless bound to yield some reasonable notion of map.

   [add-corr.: as Todd points out below (#7) there is a result in Johnstone-Lack-Sobocinski that says that $\mathcal{B}\downarrow F$ is a quasitopos for $F:\mathcal{A}\to\mathcal{B}$ between two quasitoposes iff $F$ preserves pullbacks. Hence $Set\downarrow F$ is not even a quasitopos (cf. #6).]

6. • CommentRowNumber6.
   • CommentAuthorTodd_Trimble
   • CommentTimeSep 26th 2015
   • (edited Sep 26th 2015)
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexI wish I were following this discussion better, because it sounds interesting. But regarding some points: in the alleged Artin-gluing construction, I am strongly doubtful that the finite-power-set functor preserves pullbacks. A short back-of-envelope calculation indicates that the fiber product of the map $\exists !: P_{fin}(X) \to P_{fin} 1$ with itself (where $!: X \to 1$ is the unique map, and the covariant finite power set functor $P_{fin}$ on morphisms $f: A \to B$ is defined by direct image $P_{fin}(f) = \exists f$) is of size $(2^n - 1)^2 + 1$ if $X$ is of finite size $n$. Which is a far cry from the size of $P_{fin}(X^2)$, which is $2^{n^2}$. I believe what is true though is that $P_{fin}$ is a [[taut functor]]: preserves inverse images of subobjects. The fact that the full power set functor is taut plays an important role in Paul Taylor's theory of recursion and well-foundedness. Furthermore, consonant with what Mike said in that MO discussion, my instinct is that the category of hypergraphs (as defined in that discussion) is more likely to be a quasitopos. Most categories of graphs that I am familiar with, e.g., sets equipped with a symmetric relation, are in fact quasitoposes. (A somewhat idle musing here is that Artin gluing along a taut functor between toposes is a quasitopos: perhaps that is already known? That would be neat.) The last comment by Noam puts me in mind of the distinction between morphisms of $P_{fin}$-coalgebras (which are like simulations) and merely colax morphisms which merely preserve the relation $\prec$ defined by a coalgebra structure, as briefly discussed [here](http://ncatlab.org/nlab/show/well-founded+relation#simulations). But I should check up on that -- just throwing it out there for now. Edited: Sorry, Thomas; I hadn't noticed that you had meanwhile commented. I was in the middle of chauffering my daughter to her dance classes.

   I wish I were following this discussion better, because it sounds interesting. But regarding some points: in the alleged Artin-gluing construction, I am strongly doubtful that the finite-power-set functor preserves pullbacks. A short back-of-envelope calculation indicates that the fiber product of the map $\exists !: P_{fin}(X) \to P_{fin} 1$ with itself (where $!: X \to 1$ is the unique map, and the covariant finite power set functor $P_{fin}$ on morphisms $f: A \to B$ is defined by direct image $P_{fin}(f) = \exists f$) is of size $(2^n - 1)^2 + 1$ if $X$ is of finite size $n$. Which is a far cry from the size of $P_{fin}(X^2)$, which is $2^{n^2}$.

   I believe what is true though is that $P_{fin}$ is a taut functor: preserves inverse images of subobjects. The fact that the full power set functor is taut plays an important role in Paul Taylor’s theory of recursion and well-foundedness.

   Furthermore, consonant with what Mike said in that MO discussion, my instinct is that the category of hypergraphs (as defined in that discussion) is more likely to be a quasitopos. Most categories of graphs that I am familiar with, e.g., sets equipped with a symmetric relation, are in fact quasitoposes. (A somewhat idle musing here is that Artin gluing along a taut functor between toposes is a quasitopos: perhaps that is already known? That would be neat.)

   The last comment by Noam puts me in mind of the distinction between morphisms of $P_{fin}$-coalgebras (which are like simulations) and merely colax morphisms which merely preserve the relation $\prec$ defined by a coalgebra structure, as briefly discussed here. But I should check up on that – just throwing it out there for now.

   Edited: Sorry, Thomas; I hadn’t noticed that you had meanwhile commented. I was in the middle of chauffering my daughter to her dance classes.

7. • CommentRowNumber7.
   • CommentAuthorTodd_Trimble
   • CommentTimeSep 26th 2015
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexIt seems my idle musing was quite wrong, as shown by theorem 13 [here](http://users.ecs.soton.ac.uk/ps/papers/calco07.pdf).

   It seems my idle musing was quite wrong, as shown by theorem 13 here.

8. • CommentRowNumber8.
   • CommentAuthorThomas Holder
   • CommentTimeSep 26th 2015
   • PermaLink
   Author: Thomas Holder
   Format: MarkdownItexad #6: you probably haven't missed much and still answered most of my questions anyway. Why so shy with your back-of-the-envelope-calculation ? Doesn't the same example work for full $P$ as well? I have added the Johnstone-Lack-Sobocinski paper at [[Artin gluing]].

   ad #6: you probably haven’t missed much and still answered most of my questions anyway. Why so shy with your back-of-the-envelope-calculation ? Doesn’t the same example work for full $P$ as well?

   I have added the Johnstone-Lack-Sobocinski paper at Artin gluing.

9. • CommentRowNumber9.
   • CommentAuthorNoam_Zeilberger
   • CommentTimeSep 27th 2015
   • (edited Sep 27th 2015)
   • PermaLink
   Author: Noam_Zeilberger
   Format: MarkdownItexThere's a definition of hypergraph homomorphism in _Relations and Graphs_ by Schmidt & Ströhlein, and it's essentially the one I had in mind. They define a hypergraph as a heterogenous relation $H \subseteq E \times V$ (describing "incidence" between hyperedges and hypervertices), and a homomorphism $(H \subseteq E\times V) \to (H' \subseteq E'\times V')$ as a pair of functions $f_e : E \to E'$, $f_v : V \to V'$ which preserve the incidence relation, i.e., $e\,H\,v$ implies $f_e(e)\,H'\,f_v(v)$. They define this as a generalization of the case of homogenous relations, which they call "1-graphs" and I believe correspond to "directed loop graphs" in the terminology of {[[graph]]} (no multiple edges, but loops are okay). Re: Thomas #5 and Todd #6, the homogenous case would indeed correspond to a colax morphism of coalgebras for the powerset monad. How would you translate that to the heterogenous case? I think one way to describe it is as the category of elements of the functor $(\times^\op ; P) : Set^{op} \times Set^{op} \to Cat$, where $P : Set^{op} \to Cat$ sends a set to its partial order of subsets. (By the way, I don't see a good motivation for restricting hyperedges to be incident to a finite number of hypervertices, as suggested in the mathoverflow question; if you do that then you should also restrict hypervertices to be incident to a finite number of hyperedges, to preserve the perfect edge/vertex duality of hypergraphs.) Getting back to my claim that this category (call it $\mathcal{H}$) is equivalent to $Grph/K_2$, I see one issue is what exactly we mean by "$Grph$". I was thinking of it as the category of "pseudographs" in the sense of {[[graph]]}, but now I realize that for hypergraphs in $\mathcal{H}$, the corresponding 2-colored graphs are all _simple_ graphs, i.e., any pair of a white vertex and a black vertex can be incident at most once. (Note that 2-coloring a pseudograph forces it to be loop-free, but it could still contain multiple edges.) So, now I'll claim that $\mathcal{H} \equiv SimpGrph/K_2$, but I'm also interested in how to generalize this to the case of 2-colored pseudographs. I guess we should replace relations by spans?

   There’s a definition of hypergraph homomorphism in Relations and Graphs by Schmidt & Ströhlein, and it’s essentially the one I had in mind. They define a hypergraph as a heterogenous relation $H \subseteq E \times V$ (describing “incidence” between hyperedges and hypervertices), and a homomorphism $(H \subseteq E\times V) \to (H' \subseteq E'\times V')$ as a pair of functions $f_e : E \to E'$, $f_v : V \to V'$ which preserve the incidence relation, i.e., $e\,H\,v$ implies $f_e(e)\,H'\,f_v(v)$. They define this as a generalization of the case of homogenous relations, which they call “1-graphs” and I believe correspond to “directed loop graphs” in the terminology of {graph} (no multiple edges, but loops are okay). Re: Thomas #5 and Todd #6, the homogenous case would indeed correspond to a colax morphism of coalgebras for the powerset monad. How would you translate that to the heterogenous case? I think one way to describe it is as the category of elements of the functor $(\times^\op ; P) : Set^{op} \times Set^{op} \to Cat$, where $P : Set^{op} \to Cat$ sends a set to its partial order of subsets. (By the way, I don’t see a good motivation for restricting hyperedges to be incident to a finite number of hypervertices, as suggested in the mathoverflow question; if you do that then you should also restrict hypervertices to be incident to a finite number of hyperedges, to preserve the perfect edge/vertex duality of hypergraphs.)

   Getting back to my claim that this category (call it $\mathcal{H}$) is equivalent to $Grph/K_2$, I see one issue is what exactly we mean by “$Grph$”. I was thinking of it as the category of “pseudographs” in the sense of {graph}, but now I realize that for hypergraphs in $\mathcal{H}$, the corresponding 2-colored graphs are all simple graphs, i.e., any pair of a white vertex and a black vertex can be incident at most once. (Note that 2-coloring a pseudograph forces it to be loop-free, but it could still contain multiple edges.) So, now I’ll claim that $\mathcal{H} \equiv SimpGrph/K_2$, but I’m also interested in how to generalize this to the case of 2-colored pseudographs. I guess we should replace relations by spans?

10. • CommentRowNumber10.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeSep 27th 2015
    • (edited Sep 27th 2015)
    • PermaLink
    Author: Noam_Zeilberger
    Format: MarkdownItexSo to flesh that out, hypergraphs allowing "multiple incidences" could be modelled by the functor category $Set^{\mathcal{B}}$, where $\mathcal{B} = X \leftarrow R \rightarrow Y$ is the walking span. Likewise, pseudographs can be modelled by the functor category $Set^{\mathcal{P}}$, where $\mathcal{P}$ is the walking "quiver equipped with an involution exchanging source and target", i.e., $\mathcal{P}$ has two objects $X_1,X_0$ and two parallel arrows $s,t : X_1 \to X_0$, together with an arrow $i : X_1 \to X_1$ such that $i^2 = id$ and $s\circ i = t$. The $K_2$ graph lives in $Set^{\mathcal{P}}$, and can be defined by $$X_1 = X_0 = 2, \quad s = id, t = \neg, i = \neg$$ Then my conjecture is that $Set^{\mathcal{B}}$ is equivalent to the slice category $Set^{\mathcal{P}}/K_2$.

    So to flesh that out, hypergraphs allowing “multiple incidences” could be modelled by the functor category $Set^{\mathcal{B}}$, where $\mathcal{B} = X \leftarrow R \rightarrow Y$ is the walking span. Likewise, pseudographs can be modelled by the functor category $Set^{\mathcal{P}}$, where $\mathcal{P}$ is the walking “quiver equipped with an involution exchanging source and target”, i.e., $\mathcal{P}$ has two objects $X_1,X_0$ and two parallel arrows $s,t : X_1 \to X_0$, together with an arrow $i : X_1 \to X_1$ such that $i^2 = id$ and $s\circ i = t$. The $K_2$ graph lives in $Set^{\mathcal{P}}$, and can be defined by

    $$X_1 = X_0 = 2, \quad s = id, t = \neg, i = \neg$$

    Then my conjecture is that $Set^{\mathcal{B}}$ is equivalent to the slice category $Set^{\mathcal{P}}/K_2$.

11. • CommentRowNumber11.
    • CommentAuthorThomas Holder
    • CommentTimeSep 28th 2015
    • PermaLink
    Author: Thomas Holder
    Format: MarkdownItexRegarding $Set^\mathcal{P}/K_2$: that is the category I had in mind in the passage that you quote in (#1). I imagine that $SimpGrph$ is rather badly behaved as category e.g. it seems to lack a terminal object !? So slicing is already an improvement - on the other hand it seems to me that you have to deduce all categorical properties of $SimpGrph/K_2$ by foot now. So isn't this just a high brow way to restate the fact that 2-colored graphs correspond to hypergraphs !? My point in (#5) was that $Set\downarrow F$ should be canonically related to $Grph/K_2$ assuming this to be $HypGrph$, not that it was $HypGrph$. A point that I still consider worth thinking about if one takes $F$ the full covariant powerset functor provided you like the _objects_ in $Set\downarrow F$ as _hypergraphs_. By the way, I think that 'directed loop graphs' are just the $\neg\neg$-separated quivers described [here](http://arxiv.org/abs/math/0306394). A last suggestion, it might be well worthwhile looking if there already exists in the literature a _species_ of hypergraphs.

    Regarding $Set^\mathcal{P}/K_2$: that is the category I had in mind in the passage that you quote in (#1).

    I imagine that $SimpGrph$ is rather badly behaved as category e.g. it seems to lack a terminal object !? So slicing is already an improvement - on the other hand it seems to me that you have to deduce all categorical properties of $SimpGrph/K_2$ by foot now. So isn’t this just a high brow way to restate the fact that 2-colored graphs correspond to hypergraphs !?

    My point in (#5) was that $Set\downarrow F$ should be canonically related to $Grph/K_2$ assuming this to be $HypGrph$, not that it was $HypGrph$. A point that I still consider worth thinking about if one takes $F$ the full covariant powerset functor provided you like the objects in $Set\downarrow F$ as hypergraphs.

    By the way, I think that ’directed loop graphs’ are just the $\neg\neg$-separated quivers described here.

    A last suggestion, it might be well worthwhile looking if there already exists in the literature a species of hypergraphs.

12. • CommentRowNumber12.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeSep 28th 2015
    • PermaLink
    Author: Noam_Zeilberger
    Format: MarkdownItex> I imagine that $SimpGrph$ is rather badly behaved as category e.g. it seems to lack a terminal object That's right -- luckily, it looks like we can actually get by with the larger category of "loop graphs", i.e., symmetric relations, which I believe is cartesian closed. The terminal object in $LoopGrph$ is the equality relation on 1, corresponding to the one vertex loop. Moreover, $K_2$ lives inside (as the disequality relation on 2), and taking the slice $LoopGrph/K_2$ still recovers the category of "simple hypergraphs" = heterogenous relations, owing to the fact that 2-coloring a graph rules out the possibility of loops. > So isn’t this just a high brow way to restate the fact that 2-colored graphs correspond to hypergraphs !? With this starting point I think that the equivalence has more punch: slicing into disequality takes you from symmetric relations to heterogenous relations.

    I imagine that $SimpGrph$ is rather badly behaved as category e.g. it seems to lack a terminal object

    That’s right – luckily, it looks like we can actually get by with the larger category of “loop graphs”, i.e., symmetric relations, which I believe is cartesian closed. The terminal object in $LoopGrph$ is the equality relation on 1, corresponding to the one vertex loop. Moreover, $K_2$ lives inside (as the disequality relation on 2), and taking the slice $LoopGrph/K_2$ still recovers the category of “simple hypergraphs” = heterogenous relations, owing to the fact that 2-coloring a graph rules out the possibility of loops.

    So isn’t this just a high brow way to restate the fact that 2-colored graphs correspond to hypergraphs !?

    With this starting point I think that the equivalence has more punch: slicing into disequality takes you from symmetric relations to heterogenous relations.

13. • CommentRowNumber13.
    • CommentAuthorThomas Holder
    • CommentTimeOct 1st 2015
    • (edited Oct 1st 2015)
    • PermaLink
    Author: Thomas Holder
    Format: MarkdownItexYour remark on slicing into inequality gives an interesting point of view! I see at [[category of simple graphs]] that $Loopgrph$ happens to be a quasitopos (cf. Todd in #6) and hence so is $Loopgrph/K_2$. This suggests that it corresponds to $Sep_{\neg\neg}(Set^\mathcal{P}/K_2)$ assuming this to be a way to 'separate' graphs. It would be now interesting to see how Lawvere's construction fits in. He takes as "B-partite graphs" those $E\to B$ in $Set^{\Delta_1^{op}}/B$ such the pullback (in $Set^{\Delta_1^{op}}$) along $\flat E\to B$ yields $\flat(E\to B)$. He claims that this yields the quivers as petit topos from the slice over the loop. But to what would his topos of $K_2$-partite graphs correspond to ? $Set^\mathcal{P}/K_2$ as well !? It is kind of interesting to see how natural concepts of graphs are apparently related to his petit-gros story!

    Your remark on slicing into inequality gives an interesting point of view!

    I see at category of simple graphs that $Loopgrph$ happens to be a quasitopos (cf. Todd in #6) and hence so is $Loopgrph/K_2$. This suggests that it corresponds to $Sep_{\neg\neg}(Set^\mathcal{P}/K_2)$ assuming this to be a way to ’separate’ graphs.

    It would be now interesting to see how Lawvere’s construction fits in. He takes as “B-partite graphs” those $E\to B$ in $Set^{\Delta_1^{op}}/B$ such the pullback (in $Set^{\Delta_1^{op}}$) along $\flat E\to B$ yields $\flat(E\to B)$. He claims that this yields the quivers as petit topos from the slice over the loop. But to what would his topos of $K_2$-partite graphs correspond to ? $Set^\mathcal{P}/K_2$ as well !? It is kind of interesting to see how natural concepts of graphs are apparently related to his petit-gros story!

14. • CommentRowNumber14.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeOct 1st 2015
    • PermaLink
    Author: Noam_Zeilberger
    Format: MarkdownItexSo before I saw your comments I went ahead and filled out the article some more. Coming back to #1, I believe the conclusion of this discussion is that hypergraphs should not be _defined_ as 2-colored graphs, but rather that the classical equivalence can be expressed as an equivalence of categories. A very natural way of defining a hypergraph is simply as a span, and then hypergraphs can be organized as a presheaf category $Set^{\bullet\leftarrow * \rightarrow \circ}$. I see that this is exactly what James Cranch suggested in an answer to the original MO question, but then got tripped up by the finiteness condition. As I said earlier, I don't understand the motivation for this condition, and in some situations I am interested in it is false. I don't know if anyone has worked out some hypergraph theory using spans, but I think it could be interesting. As I mentioned, the book by Schmidt & Ströhlein takes a relational approach. > I see at [[category of simple graphs]] that $Loopgrph$ happens to be a quasitopos (cf. Todd in #6) and hence so is $Loopgrph/K_2$. This suggests that it corresponds to $Sep_{\neg\neg}(Set^\mathcal{P}/K_2)$ assuming this to be a way to 'separate' graphs. I believe that's right, and that the equivalent category $SimpHGrp$ corresponds to $Sep_{\neg\neg}(Set^{\bullet\leftarrow * \rightarrow \circ})$. I will have to look back to the article by Lawvere to understand your second comment.

    So before I saw your comments I went ahead and filled out the article some more. Coming back to #1, I believe the conclusion of this discussion is that hypergraphs should not be defined as 2-colored graphs, but rather that the classical equivalence can be expressed as an equivalence of categories. A very natural way of defining a hypergraph is simply as a span, and then hypergraphs can be organized as a presheaf category $Set^{\bullet\leftarrow * \rightarrow \circ}$. I see that this is exactly what James Cranch suggested in an answer to the original MO question, but then got tripped up by the finiteness condition. As I said earlier, I don’t understand the motivation for this condition, and in some situations I am interested in it is false.

    I don’t know if anyone has worked out some hypergraph theory using spans, but I think it could be interesting. As I mentioned, the book by Schmidt & Ströhlein takes a relational approach.

    I see at category of simple graphs that $Loopgrph$ happens to be a quasitopos (cf. Todd in #6) and hence so is $Loopgrph/K_2$. This suggests that it corresponds to $Sep_{\neg\neg}(Set^\mathcal{P}/K_2)$ assuming this to be a way to ’separate’ graphs.

    I believe that’s right, and that the equivalent category $SimpHGrp$ corresponds to $Sep_{\neg\neg}(Set^{\bullet\leftarrow * \rightarrow \circ})$.

    I will have to look back to the article by Lawvere to understand your second comment.

15. • CommentRowNumber15.
    • CommentAuthorThomas Holder
    • CommentTimeOct 1st 2015
    • PermaLink
    Author: Thomas Holder
    Format: MarkdownItexSorry, that the last part sounded so cryptic, unfortunately the passage in the Lawvere paper will be very dense, too. As you were using more exotic type of graphs, it occurred to me that after all it might be possible to squeeze hypergraphs out of reflexive graphs as well. Such a result would be primarily interesting for Lawvere's enterprise - and the resulting construction presumably much more involved than your construction. Concerning the finiteness condition: it seems to be rather common in combinatorics that people demand uniform (finite) cardinalities of the hyper-edge sets e.g. Bollobás in his combinatorics book defines only r-uniform hypergraphs. So this particular form might be caused by some intended application.

    Sorry, that the last part sounded so cryptic, unfortunately the passage in the Lawvere paper will be very dense, too. As you were using more exotic type of graphs, it occurred to me that after all it might be possible to squeeze hypergraphs out of reflexive graphs as well. Such a result would be primarily interesting for Lawvere’s enterprise - and the resulting construction presumably much more involved than your construction.

    Concerning the finiteness condition: it seems to be rather common in combinatorics that people demand uniform (finite) cardinalities of the hyper-edge sets e.g. Bollobás in his combinatorics book defines only r-uniform hypergraphs. So this particular form might be caused by some intended application.

16. • CommentRowNumber16.
    • CommentAuthorThomas Holder
    • CommentTimeOct 6th 2015
    • (edited Oct 8th 2015)
    • PermaLink
    Author: Thomas Holder
    Format: MarkdownItexFor finger practice, I have computed $Set^{\mathcal{C}^{op}}/K_2$ via the formula $Set^{\mathcal{C}^{op}}/K_2\cong Set^{(\int_\mathcal{C}K_2)^{op}}$. Here $\int_\mathcal{C}K_2$ is the category of elements and I use as blueprint for quivers with an involution the category $\mathcal{C}$ with underlying diagram $[0]\rightrightarrows [1]\circlearrowleft$ . For $\int_\mathcal{C}K_2$ , this yields the following underlying diagram with the obvious compositions $\ast\substack{\nearrow\\ \searrow}\substack{\ast \\ \downarrow\uparrow \\ \ast}\substack{\nwarrow\\ \swarrow}\ast$ . This is equivalent to the walking cospan $\ast\rightarrow\ast\leftarrow\ast$. Hence $ Set^{\mathcal{C}^{op}}/K_2\cong Set^{(\ast\rightarrow\ast\leftarrow\ast)^{op}}\cong Set^{\ast\leftarrow\ast\rightarrow\ast}$ as you said. [addendum: incidentally, the argument works for the generic arc $K:=Hom_\mathcal{D}(-,[1])$ in $\mathcal{D}$ , the diagram category $[0]\rightrightarrows [1]$ underlying quivers, as well with the same result: $\int_\mathcal{D}K =\ast\rightarrow\ast\leftarrow\ast$ hence $Set^{\mathcal{D}^{op}}/K\cong Set^{\ast\leftarrow\ast\rightarrow\ast}$ . ]

    For finger practice, I have computed $Set^{\mathcal{C}^{op}}/K_2$ via the formula $Set^{\mathcal{C}^{op}}/K_2\cong Set^{(\int_\mathcal{C}K_2)^{op}}$. Here $\int_\mathcal{C}K_2$ is the category of elements and I use as blueprint for quivers with an involution the category $\mathcal{C}$ with underlying diagram $[0]\rightrightarrows [1]\circlearrowleft$ . For $\int_\mathcal{C}K_2$ , this yields the following underlying diagram with the obvious compositions $\ast\substack{\nearrow\\ \searrow}\substack{\ast \\ \downarrow\uparrow \\ \ast}\substack{\nwarrow\\ \swarrow}\ast$ . This is equivalent to the walking cospan $\ast\rightarrow\ast\leftarrow\ast$. Hence $Set^{\mathcal{C}^{op}}/K_2\cong Set^{(\ast\rightarrow\ast\leftarrow\ast)^{op}}\cong Set^{\ast\leftarrow\ast\rightarrow\ast}$ as you said.

    [addendum: incidentally, the argument works for the generic arc $K:=Hom_\mathcal{D}(-,[1])$ in $\mathcal{D}$ , the diagram category $[0]\rightrightarrows [1]$ underlying quivers, as well with the same result: $\int_\mathcal{D}K =\ast\rightarrow\ast\leftarrow\ast$ hence $Set^{\mathcal{D}^{op}}/K\cong Set^{\ast\leftarrow\ast\rightarrow\ast}$ . ]

17. • CommentRowNumber17.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeOct 7th 2015
    • PermaLink
    Author: Noam_Zeilberger
    Format: MarkdownItexNice proof!

    Nice proof!

18. • CommentRowNumber18.
    • CommentAuthorThomas Holder
    • CommentTimeMay 17th 2016
    • PermaLink
    Author: Thomas Holder
    Format: MarkdownItexI've added a remark to [[hypergraph]] that $ Set^{\bullet\leftarrow\bullet\rightarrow\bullet} $ is spatial and [[scattered topos|scattered]]. I hope I got the subtoposes right though!

    I’ve added a remark to hypergraph that $Set^{\bullet\leftarrow\bullet\rightarrow\bullet}$ is spatial and scattered. I hope I got the subtoposes right though!

19. • CommentRowNumber19.
    • CommentAuthorThomas Holder
    • CommentTimeAug 10th 2016
    • (edited Aug 10th 2016)
    • PermaLink
    Author: Thomas Holder
    Format: MarkdownItexI've added an [[Artin gluing]] analysis of $ Set^{\bullet\leftarrow\bullet\rightarrow\bullet} $ with fringe functor $\sqcap\colon Set\times Set\to Set$ and $(X,Y)\mapsto X\times Y$ at [[hypergraph]] yielding an adjoint string: $j^\circ\dashv j_!\dashv j^\ast \dashv j_\ast \colon Set\to \mathbb{Gl}(\sqcap)$. It would be nice if somebody could take a look at the last adjunction $j^\circ\dashv j_!$ since it is done mostly by hand without checking all the details.

    I’ve added an Artin gluing analysis of $Set^{\bullet\leftarrow\bullet\rightarrow\bullet}$ with fringe functor $\sqcap\colon Set\times Set\to Set$ and $(X,Y)\mapsto X\times Y$ at hypergraph yielding an adjoint string: $j^\circ\dashv j_!\dashv j^\ast \dashv j_\ast \colon Set\to \mathbb{Gl}(\sqcap)$. It would be nice if somebody could take a look at the last adjunction $j^\circ\dashv j_!$ since it is done mostly by hand without checking all the details.

20. • CommentRowNumber20.
    • CommentAuthorMike Shulman
    • CommentTimeAug 10th 2016
    • PermaLink
    Author: Mike Shulman
    Format: MarkdownItexLooks reasonable to me.

    Looks reasonable to me.

21. • CommentRowNumber21.
    • CommentAuthorThomas Holder
    • CommentTimeAug 10th 2016
    • PermaLink
    Author: Thomas Holder
    Format: MarkdownItexThanks ! I probably got a bit mystified by the Artin gluing. If one thinks of the hypergraphs simply as a presheaf topos this is a rather straightforward $\Pi\dashv\Delta\dashv\Gamma\dashv B$ string.

    Thanks ! I probably got a bit mystified by the Artin gluing. If one thinks of the hypergraphs simply as a presheaf topos this is a rather straightforward $\Pi\dashv\Delta\dashv\Gamma\dashv B$ string.