Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Here is old discussion that used to be in the entry graph and which hereby I am moving to the relevant talk-page (i.e.: the Forum thread with the same title as the entry, namely this one).
[begin forwarded discussion]
Obsolete discussion may also be found in the History at Version 24.
Toby: OK, I've completely redone the page above; this is how it looked before. In particular, I am defining things case by case, rather than choice by choice ( cases, rather than choices with options each). Feedback please!
(One obvious possibility is that the best style of definition is a mixture of the two previous styles: doing undirected and directed graphs separately, but in each case listing the two choices —loops or no loops, multiple edges or no multiple edges— as I had done before.)
Eric: Ugh. I see that quite some discussion went on here and I’m late to the party. This page is not beautiful nor remotely -categorical in my opinion. We already had a page that I was very happy with on directed graphs.
Isn’t there some way to state very simply:
A graph is a functor…
Here is a humble attempt…
+– {: .un_defn}
An abstract graph is a category with
one object , called the object of vertices;
one object , called the object of edges;
one morphism , called the ???;
together with identity morphisms.
More generally, a graph in a category is a functor . =–
Toby: First, it depends on what kind of ’graph’ you mean.
Let's take a simple undirected graph. Then the answer is no, since the definition of a simple graph is not (despite the name) as simple as the definition of digraph (directed pseudograph). Whereas a digraph consists of just , , and , a simple graph consists of , , and an injection . The two problems here are: how do you say that is an injection? and how do you describe a function in terms of functions among and ? (A map can be done; that's the same as two maps .) You can describe these things more internally, of course (say by replacing ’injective function’ with ’monomorphism’), but there's no category such that a simple graph is precisely a functor from to .
In fact, the only kind of graph above that can be defined as a functor from to for some fixed ’abstract general’ category is directed pseudograph, the kind of graph discussed at digraph. Between that, and the fact that every strict category has an underlying digraph, it's no surprise that this is the sort of graph that category theorists like. But it's not the sort of graph that graph theorists like so much!
It would be worth discussing what sort of graphs can be internalised in what sort of categories. Those graphs that allow loops are easier; I think that I can do them! For the graphs without loops, I haven't even decided what's the best way to phrase the definition in constructive mathematics. (Luckily it doesn't matter for finite graphs.)
[forwarded discussion continued in next comment]
[forwarded discussion continued]
Roger Witte says
A looped directed graph is a set with a set with a binary relation. A looped graph is a set with symmetric binary relation. A directed graph is a set with an irreflexive binary relation. A graph is a set with a symmetric irreflexive binary relation.
In each case this yields the correct definition of morphism and isomorphism
Toby: But what is the definition of morphism for a set equipped with an irreflexive relation? In many more structured examples (such as linear orders and apartness relations), at least, it is a function that reflects the relation instead of one that preserves the relation.
Long time lurker, first time writer: I don’t think of a graph as a set with binary relation so much as I think of it as a “set with an adjacency structure.” If one views graphs as adjacency lists, as a computer scientist would say, then the correct definition of morphism becomes obvious. (That said, I don’t know how well this generalizes to multigraphs – I tend to do actual graph theory and therefore work with simple graphs 99.9% of the time.)
All this makes me wonder if an approach along the following lines is possible: Define directed graphs in the broadest sense, as functors from the two-object, two-nontrivial-morphism category to the category of sets. As combinatorial objects, the obvious functor from the category of digraphs to the category of graphs is in fact a functor. Is there some analogous operation on the functor category of digraphs? (Apologies if some of the above doesn’t make much sense, I’m writing this on way too little sleep.)
Toby: I don't know the difference between ’a set with a (certain kind of) binary relation’ and ’a set with an adjacency structure’, at least not if an adjacency structure is a certain kind of binary relation. (Although it might be a good idea to say something like that in the Idea section.) Which defintion of morphism is obviously correct to you?
Long time lurker: I’m talking about the definition of graph homomorphism that graph theorists use, which I think agrees with the one given here at least for simple undirected graphs. And as for “binary relation” vs. “adjacency structure,” I don’t think there’s any real mathematical difference, but it can pay off to think of a (directed loop) graph as a function rather than a subset of .
Obviously there are some issues with this; for one thing, I don’t see an obvious way to abstract this in a category that doesn’t have a subobject classifier. But philosophically, I’d like to propose that the key property of graphs is that their edges don’t carry any information except for incidence – so, e.g., when we take a category and forget about how arrows compose, we get a digraph. And this suggests that we should have some way of defining a graph without any reference to edges.
[end forwarded discussion]
Added a brief “orienting” paragraph on subgraphs from the nPOV to graph. This article did not mention “subgraph” even once. (Incidentally, how to make a link to a page in the nlab work in a section-heading?)
This article did not mention “subgraph” even once.
From About:
If you find yourself annoyed by the state any given entry is in, for whatever reason, please feel encouraged to edit it in order to improve the situation.
Notice: an entry being in a pitiful state is usually more a sign of nobody having spared the time and energy to work on it, than of our joint incompetence to write a decent entry if we were being paid for doing it. So if you find your eyebrows raised by some entry, don’t turn away to be the next one not to work on it. Instead, improve it. We all do this voluntarily. We all have other duties to look after. So don’t be annoyed with “us”, help us.
I wouldn’t even say the “preferred” synonym in the nLab. I’m going to change it to “one synonym in the nLab”.
Edit: I made some other amendments as well. What had been there is what one would expect if the category of graphs is “any good”, but since there are all kinds of crazy ways to construct categories, I reworded it a bit. It would be good to introduce the standard definitions of (types of) subgraph beforehand, before embarking on alternative nPOV descriptions.
Thanks. Added a brief passage in response to
(Insert A standard usual graph-theoretic definition definitions of types of subgraph here.)
(reconsidered)
I’ve started reading Algebraic Graph Theory by Godsil and Royle, and it has some nice discussions that are clearly category-theory-inspired, so I inserted it into the bibliography at graph. (Some of this discussion reminded me of Tom Leinster’s post a few years back on Graph Colouring and Cartesian Closed Categories, and indeed he references this book.) But in doing so, I noticed that the bibliography also includes Lambek and Scott, Introduction to Higher Order Categorical Logic…which seems a bit odd. Apparently this goes back to the original revision, though. Was it intentional, or just a copy/paste error?
Good to know!
I went ahead and wiped the Lambek and Scott reference (surely it must have been a copy/paste bug!), and made a few other minor changes, mostly adding subsections to the Definition section, and a short mention of orientations of undirected graphs.
Re # 10.
and a short mention of orientations of undirected graphs.
Just to suggest a direction, seeing that since July 17, 2017 18:10:13 graph has arrived at orientations and invariants constructed thereof, it seems à propos to suggest: it may be of interested to some people round here to also treat the
“flow lattice”
of a finite undirected graph.
Remarks.
Yes, (flow lattice of )(cycle group with integer coefficients of when conceived of as a simplicial complex), and yes, the clash with the order-theoretic sense of “lattice” is very unfortunate (no clash in German btw, having “Gitter” and “Verband”), and yes, I have encountered accusations of this being an “inflated terminology”, but personally I think this a good terminology, and others appear to think so, too, calling it “lattice”, the clash notwithstanding , like Dancso, and also J. E. Greene herein and also D. Wagner herein, and O. Amini herein. This is related to the the-choice-of-a-synomy-is-the-statement-of-an-intent-issue, or, metaphorically, the-choice-of-a-synomym-is-the-choice-of-a-tagent-vector, giving the direction of generalization. Using “lattice” one signals that one intends to explore the linear-algebraic/module-theoretic/lattice-points-in-polytopes-direction, not a traditionally group-theoretic one. (Those lattices are rather dull, qua groups.) Saying lattice emphasizes their being-embedded-into-a-space.
There are still (as far as I know) open questions about the flow-lattice, in particular to find an appreciable characterization of when a generating set of the flow lattice contains a basis (in the sense of the theory of abelian groups). I am working on this on and off.
There is—and this is the main reason why I bring this up here—there were announcements of a categorification the flow lattice.
The flow-lattice is an finitely-generated-abelian-group-valued isomorphism-invariant of finite graphs.
I once briefly communicatet with the author of the above-cited talk-announcement about when a paper on the “categorification” would be out (it was also announced on a webpage, which I did not find in the time I allowed myself to search for it), and seem to recall that the answer was that this is not sure, and I surprisingly did not find out, searching for this, whether this has changed. But there is something to be done here.
EDIT: added one more reference to an article which both (0) uses the “lattice” terminology, and (1) has sort-of-an-nLab-relevant point of view (in that it is concerned with algebraic topology. Greene’s article is also a reasonably self-contained introduction to the cycle group of a graph from the lattice-perspective, in particular, from the flow-lattice-cut-lattice-duality-perspective.
The terminology “flow lattice” doesn’t sound bad to me. The topic seems reminiscent of Kirchhoff’s circuit laws, which have also been treated cohomologically, as discussed here.
Thanks for the references, Peter! I hadn’t heard of the “lattice” terminology, but I’ve actually been very interested in flows recently, so I’m happy to hear you studied them in your thesis. My interests are a bit further afield, coming from an analogy between flows on graphs and typings of lambda terms (discussed a bit at the end of these slides, and elaborated a bit in this abstract), but I’m trying to get a better handle on the background theory, and I’d definitely be interested in any categorical accounts.
Noam, [Typographical notes, concerning the slides mentioned in comment #13, just for the unlikely possibility that, due to your familiarity with them, you do not notice this, and intend to used the slides somewhere:
typo “underyling” on p. 24
from page 22 onwards, some of the slides to me seem slightly “cropped” at their right-hand sides, affecting some of the words; zooming did not help; understandability is not impaired by this
]
Noam, technical note: in the slides there are opacity-artifacts [couldn’t think of a better word], which, if you did do this with TikZ (like it seems you did), can be avoided by using
\begin{scope}[transparency group,opacity=0.5] \end{scope}
and the like. Easy to find, given an internet connection, that is.
thanks for spotting the typo. The slides were actually generated using the jessyink package for inkscape, which is great except that there is currently no good way to export pdfs as far as I know. (There is a way that goes via firefox, but unfortunately that’s where the cropping/artifacts you noticed seem to come up. The svg renders better in safari and chrome…at least on my computer!)
Linked to category of simple graphs.
moving the following old query box discussion out of the entry:
+–{: .query} Mike Shulman: Isn’t there something backwards about defining “isomorphic” and then “isomorphism” and then “morphism”? Doesn’t the logic generally flow in the other direction (especially around here)?
David Roberts: well at least there’s a historical precedent: this is how Bourbaki would have done it via structures :)
Toby: That, and it's simpler to state the definition of ’isomorphic’ than ’isomorphism’. Not to mention that graph theorists, in my experience, tend to care much more about the property of being isomorphic than the structure of having an isomorphism. As for ’morphism’, there's even disagreement about what that should be; I think that my definition is the obvious correct one, but it disagrees with the one at, for example, Wikipedia (although they had my definition in the past); both versions give the same notion of isomorphism, however.
Mike Shulman: Well, but we aren’t graph theorists here, are we? Isn’t it okay for us to rephrase their definitions in the more categorically sensible order?
Toby: I disagree that ’morphism’ before ’isomorphism’ is more categorially sensible. That's like defining before ; sometimes useful, sometimes not. Since I am getting ambiguity about morphisms in what I find online, I'd prefer to do isomorphisms first. With luck, I'll find some terminology to distinguish the two kinds of morphisms, or we can make up our own.
Mike Shulman: Okay, I’ll accept that sometimes it makes sense to have isomorphisms before morphisms. Certainly there are other situations in which the notion of isomorphism is more obvious, or less subject to debate, than the notion of morphism. But I am happy that now “isomorphism” comes before “isomorphic.”
RonnieBrown: I hope it is helpful to add the reference below, which also contains quite a few references to categorical treatments of graphs.
=–
I changed this:
Directed pseudographs are commonly used in category theory, where they are often called ’directed graphs’, ’digraphs’, or (less ambiguously) ’quivers’.
to this:
Directed pseudographs are commonly used in category theory, where they are often called ’directed graphs’, ’digraphs’, (less ambiguously) ’quivers’, or often in fact simply ’graphs’.
I think it’s important, especially for beginners reading this, to acknowledge that category theorists often use ’graph’ this way. Whether or not they should, they do.
(I have never heard a category theorist call them ’directed pseudographs’.)
1 to 21 of 21