Re: relations on graphs

[Richard Garner <rhgg2@hermes.cam.ac.uk>]

While we're on the topic of directed graphs, can
anyone provide a satisfactory conceptual
explanation for the following curiosity?

Let Ar(Set) be the arrow category of Set, and let
DGph be directed multigraphs, i.e., presheaves over
the parallel pair category as per Thomas' message.

Prop: DGph is comonadic over Ar(Set)

Proof: We have an adjunction U -| C as follows.

U: DGph -> Ar(Set) sends a directed graph
s, t : A -> V to the coproduct injection V -> V + A.

C: Ar(Set) -> DGph sends an arrow f : X -> Y to the
directed graph \pi_1, \pi_2 : X*X*Y -> X.

It's easy to check that this is an adjunction, and
so we induce a comonad T = UC on Ar(Set), the
functor part of which sends f: X --> Y to the
coproduct injection X --> X + X*X*Y. Thus a
coalgebra structure f --> Tf consists of specifying
a map p: Y --> X + X*X*Y satisfying three axioms.

These axioms force f: X --> Y to be an injection,
and the map p to be defined by cases: those y in Y
which lie in the image of f are sent to f^-1(y) in
the left-hand copy of X, whilst those y in Y that
are not in X are sent to some element (s(y), t(y),
y) of X*X*Y. Thus giving a T-coalgebra structure on
f:X --> Y is equivalent to giving a directed graph
structure s, t : Y \setminus f(X) --> X: and this
assignation extends to a functor T-Coalg --> DGph
which together with the canonical comparison
functor DGph --> T-Coalg gives us an equivalence of
categories, Q.E.D.

--

Richard Garner

--On 09 March 2007 20:10 Thomas Streicher wrote:

> If one allows multiple edges with the same source and target then
> they certainly form a topos, namely that of presheaves over the
> category with 2 objects and 2 parallel nontrivial arrows.
> The \neg\neg-separated objects in this topos are precisely those
> graphs where there is at most one edge from one node to another one.
> The latter category is not a topos but a quasitopos.
> The non-full monos in this category are typical examples of
> epic monos which are not isos.
>
> All this can be found in Lawvere's "Qualitative distinctions between
> toposes of graphs".
>
> Thomas Streicher
>
>
>