Todd Trimble
category of simple graphs

Contents

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

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?, and SimpGph opSimpGph^{op} is also regular. It is also \infty-extensive?.

Proof

(See also Adamek and Herrlich.) Let CC be the category of sets (or cardinality) 11 and 22 and functions between them. A presheaf on CC is a directed reflexive (multi)graph equipped with a direction-reversing involution on the set of edges. For this presheaf topos, there is just one nontrivial ¬¬\neg\neg-dense sieve, namely the inclusion

(s,t):hom(,1)+hom(,1)hom(,2)(s, t): \hom(-, 1) + \hom(-, 1) \to \hom(-, 2)

and so the category of ¬¬\neg\neg-separated presheaves? is equivalent to the category of presheaves XX such that the induced map

X(2)Set C op(hom(,2),X)(s,t) *Set C op(hom(,1)+hom(,1),X)X(1)×X(1),X(2) \cong Set^{C^{op}}(\hom(-, 2), X) \stackrel{(s, t)^\ast}{\to} Set^{C^{op}}(\hom(-, 1) + \hom(-, 1), X) \cong X(1) \times X(1),

which is the source-target pairing X(2)X(1)×X(1)X(2) \to X(1) \times X(1), is monic. Such a structure is tantamount to a set V=X(1)V = X(1) equipped with a reflexive symmetric binary relation. On the other hand, a Grothendieck quasitopos is, essentially by definition, the category of separated presheaves for a topology on a presheaf topos, in this case the ¬¬\neg\neg-topology.

Being a quasitopos with small coproducts, it is \infty-extensive provided that coproducts are disjoint. However, this is trivial to check (it even suffices to check, according to Elephant? 2.6.5, that 010 \to 1 is a regular monomorphism?, or that 1+11 + 1 is a disjoint coproduct, which it obviously is).

It is easy to describe monos? and epis? in SimpGphSimpGph. For, let Γ=hom(1,):SimpGphSet\Gamma = \hom(1, -): SimpGph \to Set be the underlying vertex-set forgetful functor?.

Proposition

The forgetful functor Γ=hom(1,):SimpGphSet\Gamma = \hom(1, -): SimpGph \to Set is faithful, in fact exhibits SimpGphSimpGph as a topological concrete category?.

We omit the easy proof. Next we have two easy results:

Proposition

Γ\Gamma reflects? monos and epis (because Γ\Gamma is faithful).

Proposition

Γ\Gamma preserves? limits? and colimits? (because it has a left adjoint? Δ\Delta and a right adjoint? \nabla).

It follows that Γ:SimpGphSet\Gamma: 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 Γ\Gamma preserves both pushouts and monos, and since the pushout of a mono in SetSet is a mono, we have that Γ(k)\Gamma(k) is monic in SetSet. Since Γ\Gamma reflects monos, this means kk is monic in SimpGphSimpGph.

As already observed, there is a chain of adjoint functors ΔΓ:SetSimpGph\Delta \dashv \Gamma \dashv \nabla: Set \to SimpGph. But in fact there is a fourth functor in the chain: Δ\Delta has a left adjoint Π:SimpGphSet\Pi: SimpGph \to Set, the connected components? functor. If EE is the simple graph consisting of two vertices a,ba, b with an edge between them, then there is a reflexive fork

a,b:1E!1a, b: 1 \rightrightarrows E \stackrel{!}{\to} 1

and Π\Pi is formed as a reflexive coequalizer? of the induced diagram:

hom(1,)hom(E,)hom(1,)Π\hom(1, -) \to hom(E, -) \rightrightarrows hom(1, -) \to \Pi
Proposition

ΠΔ\Pi \dashv \Delta, and Π\Pi preserves products.

Proof

Π\Pi preserves products because being a reflexive coequalizer, it is a sifted colimit? of product-preserving functors. For graphs GG, there is a natural map uG:GΔΠGu G: G \to \Delta \Pi G which at the underlying vertex-set level sends a vertex to its connected component; if SS is any set, then a graph map f:GΔSf: G \to \Delta S must send any two vertices with an edge between them to the same point, and so ff factors as GuGΔΠGΔgΔSG \stackrel{u G}{\to} \Delta \Pi G \stackrel{\Delta g}{\to} \Delta S for a unique map g:ΠGSg: \Pi G \to S, and this establishes the adjunction ΠΔ\Pi \dashv \Delta.

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

Γ(i)=Eq(Γ(f),Γ(g))\Gamma(i) = Eq(\Gamma(f), \Gamma(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 Γ(i)\Gamma(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

Γ(q)=Coeq(Γ(f),Γ(g))\Gamma(q) = Coeq(\Gamma(f), \Gamma(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

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

References

category: category
Created on June 13, 2017 at 07:04:24 by Todd Trimble