Re: Undirected graphs

[Marco Grandis <grandis@dima.unige.it>]

Dear Bob,

Involutive graphs are what you are saying, of course. If I had to
choose, I would take this as my favoured notion of "undirected
graph", because it is a presheaf topos on a very simple site.

A graph theorist would probably say that an "undirected graph" is
what you are hinting at, which amounts to taking the involutive
graphs where all loops are fixed by the involution (or the ones where
no loop is fixed, except the trivial ones?). Then, he might want to
forget about trivial loops, and allow vertices with no loops.

Being in a category list, another reason of "preferring" the first
notion might be:

- a category has an underlying graph,
- an involutive category has an underlying involutive graph,
- involutive categories where all endomorphisms are fixed by the
involution are rather unnatural; not to mention the ones where no
endomorphism is fixed except the identities.

Of course, there might be reasons in favour of the other choices, or
of considering different choices at a time. Life is complicated and
mathematics too. Even working in category theory, I think we should
avoid being too "categorical"...

Best regards

Marco

On 8 Mar 2006, at 16:07, cat-dist@mta.ca wrote:

> I've been following the recent posts on undirected graphs
> with interest. But I have a question. I think it's being said
> that undirected graphs are the same as directed graphs with
> involution. (Presheaves on the full subcategory of SET determined
> by 1 and 2, or just 2.) Which is nice but what about loops?
> The involution might fix a loop or not. So wouldn't we be
> getting undirected graphs with two kinds of loops, whole loops
> and semiloops? What am I missing?
>
> Bob
>
>
>