# Start a new discussion

## Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

## Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorUrs
• CommentTimeApr 4th 2012
• (edited Apr 4th 2012)

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 $n$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 ($8$ cases, rather than $3$ choices with $2$ 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 $n$-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}

###### Definition

An abstract graph $X$ is a category with

• one object $X_0$, called the object of vertices;

• one object $X_1$, called the object of edges;

• one morphism $e : X_1 \to ???$, called the ???;

• together with identity morphisms.

A graph is a functor $G: X\to$ Set.

More generally, a graph in a category $C$ is a functor $G : X \to C$. =–

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 $V$, $E$, and $d: E \to V^2$, a simple graph consists of $V$, $E$, and an injection $d: E \to \left({V \atop 2}\right)$. The two problems here are: how do you say that $d$ is an injection? and how do you describe a function $E \to \left({V \atop 2}\right)$ in terms of functions among $V$ and $E$? (A map $E \to V^2$ can be done; that's the same as two maps $E \to V$.) You can describe these things more internally, of course (say by replacing ’injective function’ with ’monomorphism’), but there's no category $X$ such that a simple graph is precisely a functor from $X$ to $Set$.

In fact, the only kind of graph above that can be defined as a functor from $X$ to $Set$ for some fixed ’abstract general’ category $X$ 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]

• CommentRowNumber2.
• CommentAuthorUrs
• CommentTimeApr 4th 2012

[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 $V \rightarrow 2^V$ rather than a subset of $V \times V$.

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]

• CommentRowNumber3.
• CommentAuthorPeter Heinig
• CommentTimeJun 14th 2017
• (edited Jun 14th 2017)

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

• CommentRowNumber4.
• CommentAuthorTodd_Trimble
• CommentTimeJun 14th 2017

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.

• CommentRowNumber5.
• CommentAuthorTodd_Trimble
• CommentTimeJun 14th 2017
• (edited Jun 14th 2017)

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.

• CommentRowNumber6.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017

Thanks. Added a brief passage in response to

(Insert A standard usual graph-theoretic definition definitions of types of subgraph here.)

• CommentRowNumber7.
• CommentAuthorPeter Heinig
• CommentTimeJun 16th 2017
• (edited Jun 16th 2017)

(reconsidered)

1. 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?

• CommentRowNumber9.
• CommentAuthorTodd_Trimble
• CommentTimeJul 2nd 2017

Good to know!

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

• CommentRowNumber11.
• CommentAuthorPeter Heinig
• CommentTimeJul 21st 2017
• (edited Jul 22nd 2017)

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.

• This is a topic close to my heart since I proved a theorem about bases of the flow lattice in my thesis.
• Yes, (flow lattice of $G$)$=$(cycle group with integer coefficients of $G$ 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.

• CommentRowNumber12.
• CommentAuthorTodd_Trimble
• CommentTimeJul 21st 2017

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.

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

• CommentRowNumber14.
• CommentAuthorPeter Heinig
• CommentTimeJul 22nd 2017
• (edited Jul 22nd 2017)

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

]

• CommentRowNumber15.
• CommentAuthorPeter Heinig
• CommentTimeJul 22nd 2017

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.

4. 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!)