nLab Quiv

Redirected from "DiGraph".
Contents

Context

Category theory

Topos Theory

topos theory

Background

Toposes

Internal Logic

Topos morphisms

Extra stuff, structure, properties

Cohomology and homotopy

In higher category theory

Theorems

Contents

Idea

QuivQuiv or DiGraphDiGraph is the category of quivers or 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 opSetG\colon X^{op} \to Set, where X opX^{op} is the category with an object 00, an object 11 and two morphisms s,t:10s, t\colon 1 \to 0, along with identity morphisms. This lets us define QuivQuiv as the category of presheaves on XX, where:

In other words, QuivQuiv is the functor category from 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 thought of as the “generic figures” (generic vertex, generic edge) that occur in directed graphs:

X(,0)=,X(,1)=(xey)X(-, 0) = \bullet, \qquad X(-, 1) = (x \stackrel{e}{\to} y)

From this picture, we can see that:

  • X(,0)X(-, 0) has two subobjects: \emptyset and \bullet.
  • X(,1)X(-, 1) has five subobjects: empty,x,y,(x,y),(xey)empty, x, y, (x, y), (x \stackrel{e}{\to} y).

The fact that QuivQuiv is a presheaf topos allows us to use topos theory, which give answers to questions like whether finite limits of directed graphs exist, or how to construct the exponential quiver Y XY^X of all morphisms XYX\to Y between two quivers in QuivQuiv.

The initial object 00 in QuivQuiv is the graph without vertices and edges aka the empty graph. The terminal object is the graph 11 with one vertex and one edge. Points of an arbitrary graph YY i.e. maps 1Y1\to Y then correpond to loops in YY whence any loopfree graph with a vertex has no points but is not empty (0\neq 0).

In the following subsections, more of the structure of the topos QuivQuiv will be worked out explicitly.

The subobject classifier

Knowing the subobjects of the representable functors 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}:

  • The set of vertices of Ω\Omega is Ω(0)={,}\Omega(0)=\{\emptyset,\bullet\}.
  • The set of edges of Ω\Omega is Ω(1)={empty,x,y,(x,y),(xey)}\Omega(1)=\{empty, x, y, (x, y), (x \stackrel{e}{\to} y)\}.

We can visualize Ω\Omega as the following quiver with two vertices and five edges:

xy empty xey (x,y)\array{ \emptyset & \underoverset{x}{y}{\rightleftarrows} & \bullet \\ \mathllap{empty} \circlearrowleft & & \circlearrowleft \circlearrowleft \mathrlap{x \stackrel{e}{\to} y} \\ & & \mathllap{(x, y)} }

where the vertex \emptyset has one loop labeled “empty”, and the vertex \bullet has two loops with labels (x,y)(x, y) and (xeyx \stackrel{e}{\to} y).

Suppose now that XYX\subseteq Y is a subgraph and χ X:YΩ\chi_X \colon Y\to\Omega is its characteristic map. On vertices:

  • χ X\chi_X maps vertices of YY not in XX to \emptyset.
  • χ X\chi_X maps vertices in XX to \bullet.

Thus, a vertex is either contained in a subgraph or not. This is represented in Ω\Omega by two vertices.

For edges, the situation is more complicated since there are five cases, which are represented by five edges in Ω\Omega. On edges:

  • χ X\chi_X maps edges which have neither source nor target in XX to the loop at \emptyset.
  • χ X\chi_X maps edges with only the source vertex in XX to xx.
  • χ X\chi_X maps edges with only the target vertex in XX to yy.
  • χ X\chi_X maps edges with both source and target vertices in XX, but where the edges themselves are not in the subgraph XX, to (x,y)(x,y).
  • χ X\chi_X maps edges that are in the subgraph XX to (xeyx \stackrel{e}{\to} y).

(Double) negation

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

im()=emptyim(\bot)= \underoverset{{empty}}{\empty}{\circlearrowleft}

sits as a subgraph in Ω\Omega:

  • Since \bullet is not in im()im(\bot), but \empty is, ¬\neg interchanges the two vertices.
  • Thus, all loops at \bullet must go to the loop empty{empty}.
  • The edge emptyempty goes to (xeyx \stackrel{e}{\to} y), since it is fully contained in im()im(\bot).
  • Now xx has only its target vertex in im()im(\bot), hence it goes to the edge yy.
  • However, yy has only its source vertex in im()im(\bot), so it goes to the edge xx.

Taking the complement of a subobject XYX\subseteq Y, i.e. taking the subobject ¬X\neg X of YY that is classified by ¬χ X\neg\circ\chi_X, then amounts to taking all vertices of YY not in XX and all the edges in YY between them.

Hence, the result ¬¬X\neg\neg X of applying ¬\neg twice to XYX\subseteq Y amounts to adding to XX all the edges of YY that have source and target in XX. This implies that a subgraph XYX\subseteq Y is dense for the double negation topology given by ¬¬:ΩΩ\neg\circ\neg \colon\Omega\to\Omega precisely when it contains all vertices of YY, since taking the complement 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:SYi \colon S\hookrightarrow Y, and any map f:SXf \colon S\to X, there is at most one g:YXg \colon 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:SXi:S\hookrightarrow X that is just like XX but has w,zw,z omitted is dense in XX. Let τ zw:XX\tau_{zw}:X\to X be the automorphism of XX that is just like the identity on XX except that it interchanges ww and zz. Then id Xi=τ zwi=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 xyx\to y between any pair (x,y)(x,y) of vertices and f:SXf:S\to X be a map with i:SYi: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:YXg: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 aba\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 arbitrary edges in arbitrary factors YY can be mapped to the appropriate edge in XX. To sum up:

Proposition

A quiver XX is separated for the double negation topology ¬¬\neg\neg precisely if there exists at most an edge aba\to b between any pair (a,b)(a,b) of vertices. XX is a ¬¬\neg\neg-sheaf precisely if there exists a unique edge aba\to b between any pair (a,b)(a,b). \Box

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 pair of vertices can be called ‘simple’ with the caveat that contrary to (the usual concept of) a simple graph they are allowed to have loops. Similarly, ¬¬\neg\neg-sheaves can be called ‘complete’.

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 BinBin 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.

Some subcategories and adjunctions

The inclusion Sh ¬¬(Quiv)Sep ¬¬(Quiv)Sh_{\neg\neg}(Quiv)\hookrightarrow Sep_{\neg\neg}(Quiv) is actually an essential localization, since it corresponds (from the relational perspective) to the adjoint triple eut:SetBine\dashv u\dashv t:Set\hookrightarrow Bin where tt maps a set XX to (X,τ X)(X,\tau_X) with τ X\tau_X the total relation on XX, uu is the forgetful functor mapping (X,ρ)(X,\rho) to XX and, ee maps a set XX to (X,)(X,\empty).

Similarly, Sh ¬¬(Quiv)iQuivSh_{\neg\neg}(Quiv)\overset{i}{\hookrightarrow} Quiv is an essential subtopos: if we identify sheafification rr with the functor that maps a quiver to the quiver on the same vertex set with edge set the total relation on the vertex set, then lril\dashv r\dashv i where ll forgets the edges of a complete quiver.

In particular, it follows then from general properties of the double negation topology that Sh ¬¬(Quiv)Sh_{\neg\neg}(Quiv) is the Aufhebung of 010\dashv 1. Whence, there exists indeed a notion of ‘codiscreteness’ (= an Aufhebung of 010\dashv 1) for quivers, namely ‘completeness’, but it does not arise from a right adjoint to the section functor Γ:QuivSet\Gamma \colon Quiv\to Set that maps a quiver to its set of loops. Indeed, the adjoint string ΠΔΓ:QuivSet\Pi\dashv\Delta\dashv\Gamma \colon Quiv\to Set that comes with the ‘discrete’ inclusion Δ\Delta that maps a set to the quiver with vertex set XX and edge set precisely one loop for every vertex, is not a localisation since ΠΔ\Pi\dashv\Delta is not a geometric morphism because Π\Pi fails to preserve products.

Furthermore, since it is a general result for presheaf toposes (cf. La Palme Reyes et al. 2004, p.204) that Γ\Gamma has a right adjoint BB precisely if a generic figure has a point and in the case of Quiv neither the generic vertex nor the generic edge contains a loop, we see that the functor Γ:QuivSet\Gamma:Quiv\to Set has no right adjoint.

References

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

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

  • M. La Palme Reyes, G. E. Reyes, H. Zolfaghari, Generic Figures and their Glueings, Polimetrica Milano 2004. (pdf)

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

category: category

Last revised on August 31, 2022 at 01:19:23. See the history of this page for a list of all contributions to it.