Quiv (Rev #11) in nLab

Contents

Idea

QuivQuiv or DiGraphDiGraph is the category of quivers or (as category theorists often call them) directed graphs. It can be viewed as the default categorical model for the concept of a category of graphs.

Definition

We can define a quiver to be a functor G:X op→SetG\colon X^{op} \to Set, where X opX^{op} is the category with an object 00, an object 11 and two morphisms s,t:1→0s, t\colon 1 \to 0, along with identity morphisms. This lets us efficiently define QuivQuiv as the category of presheaves on XX, where:

• objects are functors G:X op→SetG\colon X^{op} \to Set,
• morphisms are natural transformations between such functors.

In other words, QuivQuiv is the functor category from this X opX^{op} to Set.

As a topos

The category Quiv=Set X opQuiv = Set^{X^{op}}, being a category of presheaves, is a topos. The representable functors X(−,0),X(−,1)X(-, 0), X(-, 1) may be pictured as the “generic figures” (generic vertex, generic edge) that occur in directed graphs:

X(−,0)=•,X(−,1)=(x→ey)X(-, 0) = \bullet, \qquad X(-, 1) = (x \stackrel{e}{\to} y)

and from this picture we easily see that X(−,0)X(-, 0) has two subobjects ∅,•\emptyset, \bullet whereas X(−,1)X(-, 1) has five: empty,x,y,(x,y),(x→ey)empty, x, y, (x, y), (x \stackrel{e}{\to} y).

Being a presheaf topos has a lot of nice consequences and instantly yields answer to questions like whether finite limits of directed graphs exist or how to construct the exponential quiver Y XY^X of all homomorphisms X→YX\to Y between two quivers X,YX,Y in QuivQuiv since the answers are provided by topos theory.

In the following subsections some of the topos structure in QuivQuiv is worked out explicitly.

The subobject classifier

Knowing the subobjects of the representable functors in turn allows us to calculate the structure of the subobject classifier Ω\Omega since they correspond to the elements of the value of Ω\Omega at the corresponding objects of X opX^{op} i.e. the set of vertices of Ω\Omega is Ω(0)={∅,•}\Omega(0)=\{\emptyset,\bullet\} and the set of edges is Ω(1)={empty,x,y,(x,y),(x→ey)}\Omega(1)=\{empty, x, y, (x, y), (x \stackrel{e}{\to} y)\}.

Whence pictured Ω\Omega is the quiver with two vertices and five edges that looks roughly like

∅ ⇄xy • empty↺ ↺↺x→ey (x,y)\array{ \emptyset & \underoverset{x}{y}{\rightleftarrows} & \bullet \\ \mathllap{empty} \circlearrowleft & & \circlearrowleft \circlearrowleft \mathrlap{x \stackrel{e}{\to} y} \\ & & \mathllap{(x, y)} }

(so there is one loop labeled “empty” at the vertex ∅\emptyset, and two loops at the vertex •\bullet, one labeled (x,y)(x, y) and the other x→eyx \stackrel{e}{\to} y).

How does Ω\Omega work? Suppose that X⊆YX\subseteq Y is a subgraph and χ X:Y→Ω\chi_X:Y\to\Omega its characteristic map, then χ X\chi_X maps vertices of YY not in XX to ∅\emptyset and vertices in XX to •\bullet (a vertex is either contained in a subgraph or not - the choice is binary and, accordingly, Ω\Omega needs two vertices to represent this). For edges the situation is more complicated since there are five ways (and, accordingly five edges in Ω\Omega to represent this) for an edge zz of YY to be related to the subgraph XX: the most straightforward is when zz has neither source nor target in XX, such zz are definitely not in XX and are represented in Ω\Omega by the loop at ∅\emptyset. Now suppose that zz has either source or target vertex in XX but not both: χ X\chi_X maps these to the maps x,yx,y between ∅⇄•\emptyset\rightleftarrows\bullet, respectively. When zz has both source and target in XX, the edge itself might or might not be in XX, and the corresponding two cases are represented by the two loops at •\bullet , respectively, with ee representing the edges that are contained XX.

(Double) negation

The negation ¬:Ω→Ω\neg:\Omega\to \Omega is defined as the characteristic map of ⊥:1→Ω\bot:1\to\Omega. It specifies how

im(⊥)=↺empty∅im(\bot)= \underoverset{{empty}}{\empty}{\circlearrowleft}

sits as a subgraph in Ω\Omega:

since •\bullet is not im(⊥)im(\bot) whereas ∅\empty is, ¬\neg interchanges the two vertices and, accordingly, all loops at •\bullet must go empty{empty} . Conversely, emptyempty goes to ee (since it is fully contained in im(⊥)im(\bot)). Now xx has its target but not its source in im(⊥)im(\bot) hence it goes to yy whereas yy has its source but not its target in im(⊥)im(\bot) and therefor goes to xx.

Complementing a subobject X⊆YX\subseteq Y i.e. taking the subobject ¬X\neg X of YY that is classified by ¬∘χ X\neg\circ\chi_X amounts to taking all vertices of YY not in XX and all the edges in YY between them.

Whence the result ¬¬X\neg\neg X of applying ¬\neg twice to X⊆YX\subseteq Y amounts to adding to XX all the edges of YY that have source and target in XX. This implies in turn that a subgraph X⊆YX\subseteq Y is dense for the double negation topology ¬∘¬:Ω→Ω\neg\circ\neg:\Omega\to\Omega , precisely when it contains all vertices of YY since complementing twice will throw into ¬¬X\neg\neg X all the edges in YY between all the vertices in XX.

By definition, a quiver XX is separated for ¬¬\neg\neg when for every other quiver YY and dense subobject i:S↪Yi:S\hookrightarrow Y and any map f:S→Xf:S\to X there is at most one g:Y→Xg:Y\to X such that the following diagram commutes:

S i↓ ↘ f Y →g X \array{ S & & \\ i\downarrow &\searrow &f \\ Y &\underset{g}{\to} & X }

A separated quiver XX is a ¬¬\neg\neg-sheaf when such a unique gg always exists.

Suppose that a quiver XX has a pair of parallel edges w,zw,z. Then the subgraph i:S↪Xi:S\hookrightarrow X that is just like XX but has w,zw,z ommitted is dense in XX. Let τ zw:X→X\tau_{zw}:X\to X be the automorphism of XX that is just like the identity on XX but interchanges ww and zz. Then id X∘i=τ zw∘i=iid_X\circ i=\tau_{zw}\circ i=i and one sees that XX is not separated.

Conversely, let XX be a quiver with at most one edge x→yx\to y between any pair (x,y)(x,y) of vertices and f:S→Xf:S\to X be a map with i:S↪Yi:S\hookrightarrow Y is dense in YY. Since ii is a bijection on the vertex sets of SS and YY, if a factorization of ff through g:Y→Xg:Y\to X and ii exists the effect of gg on the vertices is uniquely determined by ff but since in XX there is at most one edge between any pair of vertices the image of any edge a→ba\to b in YY under gg is already fixed: it is the unique edge between g(a)g(a) and g(b)g(b). In particular, one sees that a separated object XX is a sheaf precisely when there exists exactly one edge between any pair of vertices since then abitrary edges in abitrary factors YY can be mapped to the appropriate edge in XX. To sum up:

The corresponding full subcategories are denoted by Sep ¬¬(Quiv)Sep_{\neg\neg}(Quiv) and Sh ¬¬(Quiv)Sh_{\neg\neg}(Quiv) , respectively. By generalities, it follows that Sep ¬¬(Quiv)Sep_{\neg\neg}(Quiv) is a quasitopos and Sh ¬¬(Quiv)Sh_{\neg\neg}(Quiv) is a Boolean topos.

Quivers that have at most one edge between any vertices can be called ‘simple’ with the caveat that contrary to (the usual concept of) a simple graph they are allowed to have loops.

Since the edges of ¬¬\neg\neg-separated quivers simply encode a binary endorelation on their vertex sets and being a morphism between ¬¬\neg\neg-separated quivers then amounts to preserve that relation one sees that Sep ¬¬(Quiv)Sep_{\neg\neg}(Quiv) and Sh ¬¬(Quiv)Sh_{\neg\neg}(Quiv) are equivalent to the categories EndoRelEndoRel with objects (X,ρ)(X,\rho) where XX is a set and ρ\rho a binary endorelation on XX, and, respectively, the category TotalRelTotalRel of sets equipped with the total relation. The latter can be identified with SetSet since morphisms between sets equipped with the total relation behave just like ordinary functions between sets.

• hypergraph

References

• R. T. Bumpy, D. M. Latch, Categorical Constructions in Graph Theory , Internat. J. Math. & Math. Sci. 9 no.1 (1986) pp.1-16.

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

• S. Vigna, A Guided Tour in the Topos of Graphs , arXiv.0306394 (2003). (abstract)