relations on graphs
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
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.
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.
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
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... 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.
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
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
participants (6)
-
Jamie Vicary -
John Stell -
Richard Garner -
Ronnie Brown -
Thomas Streicher -
Vaughan Pratt