nLab
category of simple graphs

Contents

Introduction

Both category theory and graph theory study patterns based on diagrams consisting of nodes and edges. Despite this surface impression, there is in fact very little interaction between the scientific communities of category theorists and of graph theorists.

This article is a modest bridge, indicating that the category of graphs (in the usual graph-theorist’s sense – see for example Diestel) has some very nice properties.

Simple graphs as relations

By a simple graph, we mean a set VV equipped with a symmetric reflexive relation EE. Morphisms between simple graphs are functions which preserve the given relations. Elements of VV are called vertices. Write E(x,y)E(x, y) to say (x,y)E(x, y) \in E.

When drawing graphs, we put an edge between vertices xx, yy iff xyx \neq y and E(x,y)E(x, y). In particular, we will not bother drawing an edge between xx and itself; we can think of it as tacitly there if we like. Perhaps better yet, that tacit edge can be thought of as a path of length 00 from xx to itself (and who bothers drawing a path of length 00?). In any case, it is clear that there is a natural bijection between

  • simple graph structures on VV in the graph-theorist’s sense (i.e., graphs that are undirected, loop-free, and with at most one edge between two vertices), and

  • reflexive symmetric relations on VV;

thus we are within our rights to identify these two concepts.

This maneuver allows a simple definition of morphism as a function (between the sets of vertices) that preserves the edge relation:

(x,y)E G(f(x),f(y))E H. (x,y) \in E_G \;\Rightarrow\; (f(x),f(y)) \in E_H .

This then includes natural operations like edge contractions as quotients. Namely, if f:GHf \colon G \to H is a morphism as defined above, and if we have G(x,y)G(x, y) and f(x)=f(y)=vf(x) = f(y) = v, we still have H(f(x),f(y))H(f(x), f(y)) by default, so we can think of ff as contracting the edge between xx and yy in GG down to an edge of length 00 between vv and itself in HH.

The category of simple graphs is denoted by SimpGphSimpGph.

Properties of SimpGphSimpGph

The category SimpGphSimpGph has very good properties. For example,

Theorem

SimpGphSimpGph is a Grothendieck quasitopos. In particular, it is a regular category and even a logos. It is also \infty-extensive.

See for example Adamek and Herrlich.

It is easy to describe monos and epis in SimpGphSimpGph. For, let Vert:SimpGphSetVert \colon SimpGph \to Set be the underlying vertex-set forgetful functor. We have two easy results:

Proposition

VertVert reflects monos and epis (because VertVert is faithful).

Proposition

VertVert preserves limits and colimits (because it has a left adjoint DiscDisc and a right adjoint CodiscCodisc).

It follows that Vert:SimpGphSetVert \colon SimpGph \to Set both preserves and reflects monos and epis. As a result, we can prove various simple exactness results in SimpGphSimpGph. For instance:

Lemma

In SimpGphSimpGph, the pushout of any mono is a mono.

Proof

Suppose we have a pushout diagram in SimpGphSimpGph:

G H mono k G H\array{ G & \to & H \\ ^\mathllap{mono} \downarrow & & \downarrow^\mathrlap{k} \\ G' & \to & H' }

Since VertVert preserves both pushouts and monos, and since the pushout of a mono in SetSet is a mono, we have that Vert(k)Vert(k) is monic in SetSet. Since VertVert reflects monos, this means kk is monic in SimpGphSimpGph.

Equalizers and coequalizers

If f,g:GHf, g \colon G \stackrel{\to}{\to} H are maps in SimpGphSimpGph, then their equalizer Eq(f,g)=i:KGEq(f, g) = i \colon K \to G is given at the vertex level by

Vert(i)=Eq(Vert(f),Vert(g))Vert(i) = Eq(Vert(f), Vert(g))

and at the edge level by K(x,y)G(i(x),i(y))K(x, y) \Leftrightarrow G(i(x), i(y)); in other words, if x,yx, y belong to KK and there is an edge between them in GG, then that edge lies in KK. To express this last condition, we say the subgraph ii is full (at the edge level).

Thus, ii is a regular mono in SimpGphSimpGph iff both Vert(i)Vert(i) is monic in SetSet and ii is full at the edge level.

The coequalizer of ff and gg, say Coeq(f,g)=q:HQCoeq(f, g) = q \colon H \to Q, is given at the vertex level by

Vert(q)=Coeq(Vert(f),Vert(g))Vert(q) = Coeq(Vert(f), Vert(g))

and at the edge level by taking the image of the composite E HVert(H) 2q 2Vert(Q) 2E_H \hookrightarrow Vert(H)^2 \stackrel{q^2}{\to} Vert(Q)^2, so that

Q(x,y) u,vH(u,v)q(u)=xq(v)=y.Q(x, y) \Leftrightarrow \exists_{u, v} H(u, v) \wedge q(u) = x \wedge q(v) = y.

Thus, qq is a regular epimorphism if it is surjective at both the vertex and edge levels.

Ternary factorization

The category of simple graphs has a ternary factorization system as follows: each morphism f:GHf \colon G \to H factors as

GqGaHiHG \stackrel{q}{\to} G' \stackrel{a}{\to} H' \stackrel{i}{\to} H

where

  • qq is a surjection between vertex-sets and at the edge level, i.e., is a regular epi;

  • aa induces an identity between vertex-sets (hence is jointly monic and epic), but without necessarily being full at the edge level;

  • ii is given by an injection between vertex-sets and is full at the edge level, and (thus) is a regular mono.

The factorization of ff into qq followed by iai \circ a is the (regular epi)-mono factorization, while the factorization of ff into aqa \circ q followed by ii is the epi-(regular mono) factorization. To round out the discussion, we prove that regular monos are stable under pushout (which ensures that the epi-(regular mono) factorization is an orthogonal factorization system).

Lemma

In SimpGphSimpGph, the pushout of any regular monomorphism along any map is a regular mono.

Proof

Let j:GHj \colon G \to H be a regular mono in SimpGphSimpGph, and let f:GGf \colon G \to G' be any map. Form the pushout of the pair (j,f)(j, f) as a coequalizer diagram

Gi 2fi 1jHGqHG \stackrel{\overset{i_1 \circ j}{\to}}{\underset{i_2 \circ f}{\to}} H \sqcup G' \stackrel{q}{\to} H'

where i 1:HHGi_1 \colon H \to H \sqcup G', i 2:GHGi_2 \colon G' \to H\sqcup G' are the coproduct inclusions. We are trying to show that qi 2q \circ i_2 is a regular mono. Certainly Vert(qi 2)Vert(q i_2) is monic in SetSet (again since VertVert preserves monos and pushouts), so we just have to check that qi 2q i_2 is full at the edge level. So, suppose H(qi 2(x),qi 2(y))H'(q i_2(x), q i_2 (y)); we must show G(x,y)G'(x, y). According to how we form coequalizers qq, there exist u,vHGu, v \in H \sqcup G' such that q(u)=qi 2(x)q(u) = q i_2(x), q(v)=qi 2(y)q(v) = q i_2(y), and (HG)(u,v)(H \sqcup G')(u, v). Since HH and GG' are embedded disjointly in their coproduct, we have that

  • either both uu and vv belong to the GG'-component, in which case u=i 2(x)u = i_2(x) and v=i 2(y)v = i_2(y) (but in that case we’re done because G(x,y)G'(x, y) follows from (HG)(i 2x,i 2y)(H \sqcup G')(i_2 x, i_2 y), according to how the coproduct HGH \sqcup G' is constructed);

  • or both uu and vv belong to the HH-component. But according to how pushouts are constructed at the vertex level, this means there exist g 1,g 2Gg_1, g_2 \in G such that f(g 1)=xf(g_1) = x, j(g 1)=uj(g_1) = u and f(g 2)=yf(g_2) = y, j(g 2)=vj(g_2) = v. Since H(u,v)H(u, v), or H(j(g 1),j(g 2))H(j(g_1), j(g_2)), and jj is full at the edge level (because it is a regular mono), we have G(g 1,g 2)G(g_1, g_2), and therefore G(f(g 1),f(g 2))G'(f(g_1), f(g_2)) or G(x,y)G'(x, y), as desired.

Theorem

SimpGphSimpGph is co-regular, i.e., SimpGph opSimpGph^{op} is regular.

Proof

This is obvious from the first definition of “regular” given here.

References

  • Reinhard Diestel, Graph Theory (Second Edition), Graduate Texts in Mathematics 173, Springer (2000).
  • Jiri Adamek and H. Herrlich, Cartesian closed categories, quasitopoi, and topological universes. Comm. Math. Univ. Carol., Vol. 27, No. 2 (1986), 235-257. (web)

category: category

Revised on August 24, 2012 20:25:04 by Urs Schreiber (89.204.138.87)