Subject: categories: Undirected graphs citation

From: Vaughan Pratt <[email-masked]>
Date: Mon, 27 Feb 2006 09:23:50 -0800

What would be an early reference for the representation of undirected
graphs (of the set-enriched rather than {0,1}-enriched kind) as
presheaves on the full subcategory 1 and 2 of Set?

Vaughan Pratt

---

From: [email-masked]
Date: Tue, 28 Feb 2006 18:01:56 -0500

Bob Rosebrugh and I use that point of view explicitly in our book
Set for Mathematics, but it is also in my paper "Qualitative
distinctions..."graphs".  Many of the more precise papers on
combinatorics carefully describe each piece of the graph structure
without noting that  this amounts to a presentation of  the monoid
of endomaps of the 2 element set (which of course suffices).

A similar lacuna of explicitness occurs in many papers on Galois
theory where pregroupoids are an intermediate step ; the
description of  the pregroupoid concept is really just a presentation
of the monoid of endomaps of the 4-element set.  (A right action of
that monoid is a groupoid if it satisfies the evident  pullback
condition on the action of the idempotents, the associative law
being a case of the well-definedness of  higher composition.)