Re: relations on graphs

Re: relations on graphs

[Jamie Vicary]

> Is there any literature which discusses different
> possible notions for relations on graphs?

In any regular category, and certainly any topos, there is a well
defined notion of relation, where a relation between two objects is a
subobject of their product. These admit a * operation and compose in a
well-behaved way; look towards the end of McLarty's category theory
textbook for info on this.

The category of directed graphs is certainly such a category, being
regular. The category of graphs is not a topos, I believe, but might
still be regular.

          Jamie Vicary.

Re: relations on graphs

[Richard Garner]

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

relations on graphs

[Thomas Streicher]

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

Re: relations on graphs

[Ronnie Brown]

Jamie Vicary states `the category of graphs is not a topos'. The situation
is not so simple, and is discussed for the combinatorially minded reader in
06.04 BROWN, R., MORRIS, I., SHRIMPTON, J. & WENSLEY, C.D.
Graphs of morphisms of graphs
http://www.informatics.bangor.ac.uk/public/mathematics/research/preprints/06/cathom06.html#06.04
There are categories of undirected graphs which are not toposes. But ...

Ronnie Brown

----- Original Message -----
From: "Jamie Vicary" <jamie.vicary@imperial.ac.uk>
To: <categories@mta.ca>
Sent: Friday, March 09, 2007 10:01 AM
Subject: categories: Re: relations on graphs


>> Is there any literature which discusses different
>> possible notions for relations on graphs?
>
> In any regular category, and certainly any topos, there is a well
> defined notion of relation, where a relation between two objects is a
> subobject of their product. These admit a * operation and compose in a
> well-behaved way; look towards the end of McLarty's category theory
> textbook for info on this.
>
> The category of directed graphs is certainly such a category, being
> regular. The category of graphs is not a topos, I believe, but might
> still be regular.
>
>          Jamie Vicary.
>

Re: relations on graphs

[Vaughan Pratt]

> The category of directed graphs is certainly such a category, being
> regular. The category of graphs is not a topos, I believe, but might
> still be regular.

Suitably defined the category of undirected graphs is indeed a topos.
As came up a year ago on this list (thread beginning with my 2/27/06
inquiry about the history of the presheaf category of undirected
graphs), undirected or symmetric graphs can be defined as M-sets for the
monoid M = Set(2,2), endomorphisms of the doubleton in Set, aka the four
unary Boolean operations.  Of the latter, x and not-x together denote
the two directions of edge x while 0(x) and 1(x) denote its two vertices
(as self-loops).

One might imagine some sort of asymmetry between x and not-x that makes
x the primary direction, but x and not-x always travel together as a
group (quite literally: S_2) under graph homomorphism and their
inseparability justifies the view of the two as forming a single
undirected edge having two directed names, x and not-x.

The singleton splits 0 and 1 to make those self-loops vertices in their
own right, so by Morita equivalence the full subcategory of Set with
objects the positive cardinals up to 2 canonically represents the same
presheaf category up to equivalence.

Dusko Pavlovic, "A categorical setting for the 4-color theorem," JPAA
102, 1, 75--88 (1995), organizes undirected graphs as the above topos.
Section 10.3 (pp. 176--180) of Lawvere and Rosebrugh, Sets for
Mathematics, CUP 2003, develops this topos in more detail, pointing out
the two distinguished loops, an idiosyncrasy of this representation of
undirected graphs.

All this lifts readily to the topos of higher dimensional graphs:
simplicial sets in the directed case, symmetric simplicial sets in the
undirected.  Marco Grandis, in Finite sets and symmetric simplicial
sets, Theory Appl. Categ. 8 (2001), No. 8, 244-252, identified the
presheaves on FinSet with the undirected or symmetric simplicial sets,
which as Clemens Berger pointed out had been encountered much earlier in
another guise by Daniel Kan (Amer. J. Math. 79 (1957) 449-476 as the
barycentric subdivision of a simplicial set.

Vaughan

Re: relations on graphs

[Jamie Vicary]

On 3/9/07, Jamie Vicary <jamie.vicary@imperial.ac.uk> wrote:
> > Is there any literature which discusses different
> > possible notions for relations on graphs?
>
> In any regular category, and certainly any topos, there is a well
> defined notion of relation, where a relation between two objects is a
> subobject of their product. These admit a * operation and compose in a
> well-behaved way; look towards the end of McLarty's category theory
> textbook for info on this.
>
> The category of directed graphs is certainly such a category, being
> regular. The category of graphs is not a topos, I believe, but might
> still be regular.

Dear all, before the flood of complaints begins: I should make it
clear that I am differentiating between the category of directed
graphs, which is certainly a topos, and the category of graphs (i.e.
edges have no orientation) which, as I have just managed to convince
myself, is certainly _not_ a topos.

The original poster was enquiring about the category of graphs, I
believe, rather than the category of directed graphs.

            JAmie.

relations on graphs

[John Stell]

For a set, X, relations on X are equivalent to
join-preserving functions on the powerset P(X).

If we replace X by a graph, the usual notion
of a relation on a graph is  a pair of relations
one on edges and one on nodes subject to an
obvious compatibility condition. However such
relations are not as general as the join-preserving
functions on the bi-Heyting algebra of subgraphs
(consider for example the one node, one edge graph).
If we mean relations in this more general sense
could there be a notion of converse? (anything
for which R** = R, and 1* = 1, and (RS)* = S*R*)

Is there any literature which discusses different
possible notions for relations on graphs?

John Stell