nLab hypergraph

Redirected from "hypergraphs".
Contents

Contents

Idea

In an ordinary undirected graph, each edge ee links an unordered pair of vertices xx and yy (perhaps allowing for the possibility that x=yx = y, as in the case of a loop). Hypergraphs generalize this, allowing a “hyperedge” to link any set of “hypervertices”. Abstracting everything away but the incidence relation between hypervertices and hyperedges, a hypergraph can be modelled as an arbitrary heterogenous relation, or more generally as a span.

Categories of hypergraphs: Definition

As with “graph”, the word “hypergraph” does not have an entirely standardized meaning. We take as our starting point (Schmidt & Ströhlein), who define hypergraphs as heterogenous relations (usually presented as boolean-valued matrices) and give an appropriate notion of morphism. We call these “simple” hypergraphs, since they are a special case of a more general definition given below.

Definition

The category of simple hypergraphs SimpHGrphSimpHGrph has objects consisting of a pair of sets (V,E)(V,E) equipped with a relation RV×ER \subseteq V \times E, and morphisms (RV×E)(RV×E)(R \subseteq V \times E) \to (R' \subseteq V' \times E') consisting of pairs of functions (f:VV,g:EE)(f : V \to V', g : E \to E') which preserve the relation, i.e., such that for all vV,eEv\in V, e \in E, if (v,e)R(v,e) \in R then (fv,ge)R(f v,g e) \in R'.

The category of simple hypergraphs could also be referred to more dryly as “the category of binary relations”, although this has potential for confusion with Rel (whose morphisms are binary relations).

In a simple hypergraph, a hypervertex can be incident to a hyperedge at most once, but in some situations one wants to allow a hypervertex to be incident to a hyperedge multiple times. To define hypergraphs in this more general sense, we keep the intuition of hypergraphs-as-heterogenous-relations, but generalize relations to spans.

Definition

The category of hypergraphs HGrphHGrph has objects consisting of a pair of sets (V,E)(V,E) equipped with a span VvReEV \overset{v}\leftarrow R \overset{e}\rightarrow E, and morphisms (VvReE)(VvReE)(V \overset{v}\leftarrow R \overset{e}\rightarrow E) \to (V' \overset{v'}\leftarrow R' \overset{e'}\rightarrow E') consisting of triples of functions (f:VV,g:EE,h:RR)(f : V \to V', g : E \to E', h:R \to R') such that vh=fvv'\circ h = f\circ v and eh=gee'\circ h = g\circ e.

Note that HGrphHGrph is just the category of presheaves over the “walking cospan” \bullet \rightarrow \bullet \leftarrow \bullet, and that SimpHGrphSimpHGrph is a full subcategory of HGrphHGrph.

Hypergraphs from a topos-theoretic perspective

In Lawvere (1986 p.6, 1989 pp.283-4) it is pointed out that Set Set^{\bullet\leftarrow\bullet\rightarrow\bullet} is a spatial topos since it is equivalent to the topos of sheaves on the space X={a,b,c}X=\{a,b,c\} with topology τ={,{a},{b},{a,b},{a,b,c}}\tau=\{\emptyset,\{a\},\{b\},\{a,b\},\{a,b,c\}\} i.e. XX has two isolated points a,ba,b and a focal one cc whose only neighborhood is the whole space.

The lattice of subtoposes of Set Set^{\bullet\leftarrow\bullet\rightarrow\bullet} consists (besides the two obvious subtoposes) of one closed and two open copies of SetSet, two closed copies of the Sierpinski topos complementing the open copies of SetSet respectively and an open Set×Set=Sh({a,b})=Sh ¬¬(Set )Set\times Set=Sh(\{a,b\})=Sh_{\neg\neg}(Set^{\bullet\leftarrow\bullet\rightarrow\bullet}) complementing the closed copy of SetSet. In particular, Set Set^{\bullet\leftarrow\bullet\rightarrow\bullet} is a scattered topos.

The complementary open-closed pairs of the subtopos lattice correspond precisely to analyses of Set Set^{\bullet\leftarrow\bullet\rightarrow\bullet} by Artin gluing.

For instance, take the product functor :Set×SetSet\sqcap\colon Set\times Set\to Set with (X,Y)X×Y(X,Y)\mapsto X\times Y. \sqcap is left exact since it forms an adjoint string with the diagonal functor and the coproduct functor: \sqcup\dashv \triangle\dashv\sqcap .

Then Gl()\mathbf{Gl}(\sqcap) has objects ((X,Y),Z,u:ZX×Y)((X,Y),Z, u\colon Z\to X\times Y) where (X,Y)Set×Set(X,Y)\in Set\times Set and ZSetZ\in Set and uu is a morphism in SetSet. Since by the universal property of products u:Zu 0,u 1X×Yu\colon Z\overset{\langle u_0, u_1\rangle}{\rightarrow} X\times Y corresponds to a pair of maps u 0u_0, u 1u_1, one sees that the objects in Gl()\mathbf{Gl}(\sqcap) really correspond to spans in SetSet.

The open inclusion of Set×SetSet\times Set into Gl()\mathbf{Gl}(\sqcap) is given by the geometric morphism

i *:Set×SetGl()(X,Y)((X,Y),X×Y,id X×Y) i_\ast \colon Set\times Set\to \mathbf{Gl}(\sqcap) \qquad (X,Y)\mapsto ((X,Y),X\times Y,id_{X\times Y})
i *:Gl()Set×Set((X,Y),Z,u)(X,Y) i^\ast\colon \mathbf{Gl}(\sqcap)\to Set\times Set \qquad ((X,Y),Z,u)\mapsto (X,Y)
i !:Set×SetGl()(X,Y)((X,Y),0,0X×Y), i_{!} \colon Set\times Set\to \mathbf{Gl}(\sqcap) \qquad (X,Y)\mapsto ((X,Y),0,0\to X\times Y) \quad ,

and the closed inclusion of SetSet by

j *:SetGl()X((1,1),X,X1×1) j_\ast \colon Set\to \mathbf{Gl}(\sqcap) \qquad X\mapsto ((1,1),X,X\to 1\times 1)
j *:Gl()Set((X,Y),Z,u)Z. j^\ast\colon\mathbf{Gl}(\sqcap)\to Set \qquad ((X,Y),Z,u)\mapsto Z\quad .

Since \triangle\dashv\sqcap the closed inclusion is essential:

j !:SetGl()X((X,X),X,Xid X,id XX×X). j_!\colon Set \to \mathbf{Gl}(\sqcap)\qquad X\mapsto ((X,X), X, X\overset{\langle id_X,id_X\rangle}{\to} X\times X)\quad .

Since \sqcup\dashv \triangle there is a somewhat surprising further left adjoint:

j :Gl()Set((X,Y),Z,u)X uY. j^\circ\colon\mathbf{Gl}(\sqcap)\to Set \qquad ((X,Y),Z,u)\mapsto X\sqcup_u Y\quad .

Here X uY X\sqcup_u Y denotes the pushout of Xu 0Zu 1YX\overset{u_0}{\leftarrow} Z\overset{u_1}{\rightarrow} Y where u 0u_0, u 1u_1 are the pair of maps provided by u:Zu 0,u 1X×Yu\colon Z\overset{\langle u_0, u_1\rangle}{\rightarrow} X\times Y . Since a map from ((X,Y),Z,u)((X,Y),Z,u) to j !(W)j_!(W) is a triple (f 0,f 1,f 2)(f_0,f_1,f_2) such that the following diagram commutes:

Z u 0,u 1 X×Y f 2 f 0f 1 W id W,id W W×W \array{ Z & \overset{\langle u_0, u_1\rangle}{\rightarrow} & X\times Y \\ f_2\downarrow & &f_0\downarrow \downarrow f_1 \\ W & \overset{\langle id_W, id_W\rangle}{\rightarrow} & W\times W }

(f 0,f 1,f 2)(f_0,f_1,f_2) has to satisfy the two conditions f 0u 0=f 2f_0 u_0= f_2 and f 1u 1=f 2f_1 u_1=f_2, or equivalently, f 0u 0=f 1u 1f_0 u_0=f_1 u_1 . But this is the same as giving a map from j ((X,Y),Z,u)=X uYj^\circ ((X,Y),Z,u)= X\sqcup_u Y to WW by the universal property of the pushout.

Whence we get an adjoint string:

j j !j *j *:Set𝔾𝕝()j^\circ\dashv j_!\dashv j^\ast \dashv j_\ast \colon Set\to \mathbb{Gl}(\sqcap)

with j !j_!, j *j_\ast fully faithful, exhibiting Gl()\mathbf{Gl}(\sqcap) almost as a cohesive topos over SetSet. Of course, since Set Set^{\bullet\leftarrow\bullet\rightarrow\bullet} is spatial it is not expected to satisfy all of Lawvere’s axioms. In particular, the Nullstellensatz is violated since none of the copies of SetSet is dense in Set Set^{\bullet\leftarrow\bullet\rightarrow\bullet}.

Let QQ be the diagram category NtsAN\overset{s}{\underset{t}{\rightrightarrows}} A underlying the topos Set Q opSet^{Q^{op}} of directed graphs or quivers. Consider the Yoneda embedding of the object AA into the presheaves: Y(A)=Hom Q(,A)Y(A)=Hom_Q(-,A). Viewed as a graph this gives the basic figure type of an arrow K 2=K_2=\bullet\to\bullet , the other basic figure being the node \bullet given by Y(N)Y(N) .

The category of elements QY(A)\int_Q Y(A) is just the category \bullet\rightarrow \bullet\leftarrow\bullet underlying the hypergraphs. Since Y(A)Y(A) is the representable presheaf corresponding to AA this is equivalent to the slice category Q/AQ/A. Then the following equivalence exhibits Set Q opSet^{Q^{op}} as an étendue topos using a general formula for slices of presheaf toposes and suggesting to view a quiver as a ‘foliated’ hypergraph:

Set Q op/Y(A)Set (Q/A) opSet ( QY(A)) opSet .Set^{Q^{op}}/Y(A)\simeq Set^{(Q/A)^{op}}\simeq Set^{(\int_Q Y(A))^{op}}\simeq Set^{\bullet\leftarrow\bullet\rightarrow\bullet}\quad .

This equivalence will be further explained in terms of graph colorings in the next section.

Hypergraphs as 2-colored graphs

There is a classical equivalence between hypergraphs and 2-colored (hence bipartite) graphs. Given a hypergraph HH, define a graph G(H)G(H) whose vertex set is the disjoint union of the hypervertices and the hyperedges of HH, and with an edge x vx ex_v \sim x_e in G(H)G(H) whenever the corresponding pair (v,e)(v,e) are incident in HH (creating multiple edges in the case of multiple incidence). By coloring vertices corresponding to hypervertices in black and vertices corresponding to hyperedges in white, we satisfy the requirement that no pair of vertices sharing an edge have the same color. Conversely, this construction is clearly reversible: any 2-colored graph GG determines a hypergraph H(G)H(G) by interpreting black vertices as hypervertices and white vertices as hyperedges that connect all of their (black vertex) neighbors.

Giving a vertex coloring of a graph GG with nn colors is equivalent to building a graph homomorphism GK nG \to K_n into the complete graph on nn vertices, and so graphs equipped with a 22-coloring are naturally organized as a slice category over K 2K_2. The classical equivalence between hypergraphs and 2-colored graphs can then be expressed formally as an equivalence of categories

HGrphGrph/K 2 HGrph \cong Grph/K_2

between the category of hypergraphs and the slice over K 2K_2 of the category of graphs, where by the latter we mean “pseudographs” in the greatest level of generality, allowing for loops, multiple edges between vertices, and dangling half-edges (as described in this definition). Moreover, this equivalence restricts to an equivalence

SimpHGrphLoopGrph/K 2 SimpHGrph \cong LoopGrph/K_2

where LoopGraphLoopGraph is the category of “loop graphs”, i.e., the full subcategory of GrphGrph whose objects are symmetric relations.

References

  • W. Dörfler and D. A. Waller, A category-theoretical approach to hypergraphs, Archiv der Mathematik 34 no.1 (1980) pp.185-192. DOI: 10.1007/BF01224952

  • W. Grilliette, A Functorial Link between Hypergraphs and Quivers , Electronic J. of Combinatorics 22 (2015). (arXiv:1608:00058)

  • F. William Lawvere, Categories of Spaces may not be Generalized Spaces as Exemplified by Directed Graphs, Revista Colombiana de Matemáticas XX (1986) pp.179-186. Reprinted with commentary in TAC 9 (2005) pp.1-7. (pdf)

  • F. William Lawvere, Qualitative Distinctions between some Toposes of Generalized Graphs , Cont. Math. 92 (1989) pp.261-299.

  • T. R. S. Walsh, Hypermaps Versus Bipartite Maps, Journal of Combinatorial Theory (B) 18 (1975) pp.155-163.

  • Martin Schmidt, Functorial Approach to Graph and Hypergraph Theory, (arXiv:1907.02574)

Last revised on July 8, 2019 at 12:14:07. See the history of this page for a list of all contributions to it.