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 whose elements are called vertices, together with a collection of 2-element subsets {x,y}\{x, y\} of VV; these are called edges of the graph.

There are various ways of forming a category of simple graphs. Perhaps the most straightforward is to define a morphism of graphs GHG \to H to be a function f:VWf: V \to W between the vertex sets to be a graph morphism if {f(x),f(y)}\{f(x), f(y)\} is an edge of HH whenever {x,y}\{x, y\} is an edge of GG.

Another option – and this is the one chosen for this article – starts by regarding a simple graph as carrying the same information as a set VV equipped with a symmetric reflexive relation EE. Indeed, such a relation determines (and is uniquely determined by) a simple graph GG where for given vertices x,yVx, y \in V, there is an edge {x,y}\{x, y\} between xx and yy in GG iff both (x,y)E(x, y) \in E and xyx \neq y. We will write E(x,y)E(x, y) to mean (x,y)E(x, y) \in E.

Then, under the relational formulation, we define a morphism (V,E)(W,F)(V, E) \to (W, F) between simple graphs straightforwardly1 as a function f:VWf: V \to W that preserves the relevant structure, i.e., that E(x,y)E(x, y) implies F(f(x),f(y))F(f(x), f(y)). One reason for preferring this notion of morphism is that it allows, for example, consideration of arbitrary edge contractions of a simple graph as quotients in the category (cf. graph minor), something that is not possible under the prior notion of morphism.

Thus we will adopt the latter notion of morphism which takes reflexive symmetric relations EE as primary. The resulting category of simple graphs is denoted by SimpGphSimpGph.

Note that graphs and their morphisms can also be understood in functorial language, by regarding simple graphs as special types of presheaves, as follows. Let CC be the category of sets 1{*}1 \coloneqq \{\ast\} and 2{s,t}2 \coloneqq \{s, t\} and functions between them. Then a presheaf X:C opSetX: C^{op} \to Set is given by sets V=X(1)V = X(1) and E=X(2)E = X(2) and maps

  • d 0:X(2)X(*s)X(1)d_0: X(2) \stackrel{X(\ast \mapsto s)}{\to} X(1) (source map),

  • d 1:X(2)X(*t)X(1)d_1: X(2) \stackrel{X(\ast \mapsto t)}{\to} X(1) (target map),

  • i:X(1)X(s,t*)X(2)i: X(1) \stackrel{X(s, t \mapsto \ast)}{\to} X(2) (reflexive map),

  • σ:X(2)X(st,ts)X(2)\sigma: X(2) \stackrel{X(s \mapsto t, t \mapsto s)}{\to} X(2) (symmetry map).

satisfying appropriate identities imposed by equations in CC. Simple graphs can then be regarded equivalently as such presheaves where the map

d 0,d 1:X(2)X(1)×X(1)\langle d_0, d_1 \rangle: X(2) \to X(1) \times X(1)

is a monomorphism. In that case, a morphism of simple graphs amounts to a natural transformation between such presheaves.

An aside on other notions of graph

“Simple graph” as defined in the nLab (see graph) means that edges are 2-element subsets of VV, but of course that doesn’t preclude consideration of other types of graph. One option is to consider sets VV equipped with a collection of subsets of VV of cardinality either 1 or 2, i.e., allowing some but not necessarily all loops as edges. We don’t call those “simple graphs” (at graph they are called “loop graphs”), but nevertheless they form a respectable category under the straightforward notion of morphism ff (if {x,y}\{x, y\} is an edge of the domain, possibly with x=yx = y, then {f(x),f(y)}\{f(x), f(y)\} is an edge of the codomain).

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.) As above, let CC be the category of sets 11 and 22 and functions between them, and regard the category of simple graphs as a full subcategory of the presheaf topos Set C opSet^{C^{op}}. For this presheaf topos, there is just one nontrivial ¬¬\neg\neg-dense sieve, namely the inclusion

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

(where ss is shorthand for C(,*s)C(-, \ast \mapsto s) and similarly for tt) 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(C(,2),X)(s,t) *Set C op(C(,1)+C(,1),X)X(1)×X(1),X(2) \cong Set^{C^{op}}(C(-, 2), X) \stackrel{(s, t)^\ast}{\to} Set^{C^{op}}(C(-, 1) + C(-, 1), X) \cong X(1) \times X(1),

which is the source-target pairing d 0,d 1:X(2)X(1)×X(1)\langle d_0, d_1 \rangle: X(2) \to X(1) \times X(1), is monic. In other words, a simple graph in this language is exactly a separated presheaf. 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).

Remark

Implicit in this proof is the way in which (for example) limits of simple graphs are calculated. Since SimpGphSimpGph is realized as a category of separated presheaves which is a reflective subcategory of all presheaves, limits in SimpGphSimpGph are calculated just as they are in the presheaf category Set C opSet^{C^{op}}, which is to say: they are computed objectwise, at the objects 1,21, 2 of CC.

For example, consider how to construct the equalizer of a pair of graph maps f,g:GHf, g: G \rightrightarrows H. For the vertex set of the equalizer (computing the equalizer at the object 11 of CC), one just takes the equalizer of the functions between the vertex sets of GG and HH. At the edge set level where we have maps E=G(2)F=H(2)E = G(2) \rightrightarrows F = H(2): since there is at most one edge between two vertices, the maps f(2),g(2)f(2), g(2) must agree on eEe \in E provided f(d 0e)=g(d 0e)f(d_0 e) = g(d_0 e) and f(d 1e)=g(d 1e)f(d_1 e) = g(d_1 e), so the equalizer graph is just the full or induced subgraph of GG given by the equalizer vertex set.

Moreover, every induced subgraph HGH \hookrightarrow G arises as an equalizer (consider the equalizer of the two embeddings of GG into the amalgamation G+ HGG +_H G, which at the vertex level agrees with HGH \hookrightarrow G).

Of course this is elementary, but we get much more more: the quasitopos SimpGphSimpGph is also a locally cartesian closed category, and dependent products can also be read off directly from how they work for presheaves.

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:

SimpGph(1,)SimpGph(E,)SimpGph(1,)ΠSimpGph(1, -) \to SimpGph(E, -) \rightrightarrows SimpGph(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 (see Remark 1).

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

  • 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. (The fact that regular monos are stable under pushout, used to ensure that the epi-(regular mono) factorization is an orthogonal factorization system, is true because SimpGphSimpGph, being a quasitopos, is a coregular category, meaning SimpGph opSimpGph^{op} is regular.) Both factorizations coincide at the level of underlying functions between vertex sets, both being the usual epi-mono factorization.

In particular, we have the easy facts that

  • ff is a mono iff qq is a graph isomorphism: monos in SimpGphSimpGph are simple graph maps that are injective on vertices and edges,

  • ff is an epi iff ii is a graph isomorphism: epis in SimpGphSimpGph are simple graph maps that are surjective on vertices.

Subcategories

Graph theory suggests both full and wide subcategories of SimpGphSimpGph. See the category of simple graphs from a graph-theoretic perspective for more details.

Natural numbers object

The category SimpGphSimpGph has a natural numbers object; on abstract grounds this is formed by applying the reflection functor

L:Set C opSimpGphL: Set^{C^{op}} \to SimpGph

to the natural numbers object in Set C opSet^{C^{op}}.

References

  • Jiří Adámek and Horst Herrlich, Cartesian closed categories, quasitopoi, and topological universes. Comm. Math. Univ. Carol., Vol. 27, No. 2 (1986), 235-257. (web)
  • Reinhard Diestel, Graph Theory (Second Edition), Graduate Texts in Mathematics 173, Springer (2000).

category: category


  1. In other words, the usual notion of morphism between structures or models as in model theory.

Revised on June 18, 2017 00:39:12 by Todd Trimble (24.146.226.222)