Not signed in

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

• Username
• Password
• Remember me

• Sign in using OpenID
• Remember me

• Forgot your password?
• Apply for membership

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory internal-categories k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

1. • CommentRowNumber1.
   • CommentAuthorUrs
   • CommentTimeApr 4th 2012
   • (edited Apr 4th 2012)
   • PermaLink
   Author: Urs
   Format: MarkdownItexHere 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](http://ncatlab.org/nlab/revision/graph/24). _Toby_: OK, I\'ve completely redone the page above; [this](http://ncatlab.org/nlab/revision/graph/24) 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 [[internalization|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]

   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]

2. • CommentRowNumber2.
   • CommentAuthorUrs
   • CommentTimeApr 4th 2012
   • PermaLink
   Author: Urs
   Format: MarkdownItex[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]

   [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]

3. • CommentRowNumber3.
   • CommentAuthorPeter Heinig
   • CommentTimeJun 14th 2017
   • (edited Jun 14th 2017)
   • PermaLink
   Author: Peter Heinig
   Format: MarkdownItexAdded 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?)

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

4. • CommentRowNumber4.
   • CommentAuthorTodd_Trimble
   • CommentTimeJun 14th 2017
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItex> 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.

   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.

5. • CommentRowNumber5.
   • CommentAuthorTodd_Trimble
   • CommentTimeJun 14th 2017
   • (edited Jun 14th 2017)
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexI 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.

   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.

6. • CommentRowNumber6.
   • CommentAuthorPeter Heinig
   • CommentTimeJun 15th 2017
   • PermaLink
   Author: Peter Heinig
   Format: MarkdownItexThanks. Added a brief passage in response to > (Insert A standard usual graph-theoretic definition definitions of types of subgraph here.)

   Thanks. Added a brief passage in response to

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

7. • CommentRowNumber7.
   • CommentAuthorPeter Heinig
   • CommentTimeJun 16th 2017
   • (edited Jun 16th 2017)
   • PermaLink
   Author: Peter Heinig
   Format: MarkdownItex(reconsidered)

   (reconsidered)

8. • CommentRowNumber8.
   • CommentAuthorNoam_Zeilberger
   • CommentTimeJul 2nd 2017
   • PermaLink
   Author: Noam_Zeilberger
   Format: MarkdownItexI'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](https://golem.ph.utexas.edu/category/2014/12/graph_colouring_and_cartesian.html), 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](https://ncatlab.org/nlab/revision/graph/1), though. Was it intentional, or just a copy/paste error?

   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?

9. • CommentRowNumber9.
   • CommentAuthorTodd_Trimble
   • CommentTimeJul 2nd 2017
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexGood to know!

   Good to know!

10. • CommentRowNumber10.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeJul 17th 2017
    • PermaLink
    Author: Noam_Zeilberger
    Format: MarkdownItexI 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.

    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.

11. • CommentRowNumber11.
    • CommentAuthorPeter Heinig
    • CommentTimeJul 21st 2017
    • (edited Jul 22nd 2017)
    • PermaLink
    Author: Peter Heinig
    Format: MarkdownItexRe # 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](https://link.springer.com/article/10.1007/s00222-012-0421-4) and also D. Wagner [herein](http://www.sciencedirect.com/science/article/pii/S0095895610000742), and O. Amini [herein](https://arxiv.org/abs/1007.2456). 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](http://www.ams.org/amsmtgs/2199_abstracts/1095-18-228.pdf) 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.

    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.

12. • CommentRowNumber12.
    • CommentAuthorTodd_Trimble
    • CommentTimeJul 21st 2017
    • PermaLink
    Author: Todd_Trimble
    Format: MarkdownItexThe 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](https://ncatlab.org/johnbaez/show/Circuit+theory).

    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.

13. • CommentRowNumber13.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeJul 21st 2017
    • PermaLink
    Author: Noam_Zeilberger
    Format: MarkdownItexThanks 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](http://noamz.org/talks/bridges.svg), and elaborated a bit in [this abstract](http://noamz.org/talks/strimploids.pdf)), but I'm trying to get a better handle on the background theory, and I'd definitely be interested in any categorical accounts.

    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.

14. • CommentRowNumber14.
    • CommentAuthorPeter Heinig
    • CommentTimeJul 22nd 2017
    • (edited Jul 22nd 2017)
    • PermaLink
    Author: Peter Heinig
    Format: MarkdownItexNoam, [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, [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

    ]

15. • CommentRowNumber15.
    • CommentAuthorPeter Heinig
    • CommentTimeJul 22nd 2017
    • PermaLink
    Author: Peter Heinig
    Format: MarkdownItexNoam, 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.

    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.

16. • CommentRowNumber16.
    • CommentAuthorNoam_Zeilberger
    • CommentTimeJul 22nd 2017
    • PermaLink
    Author: Noam_Zeilberger
    Format: MarkdownItexthanks 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!)

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

17. • CommentRowNumber17.
    • CommentAuthorRichard Williamson
    • CommentTimeApr 16th 2020
    • PermaLink
    Author: Richard Williamson
    Format: MarkdownItexAdding 'semi-graph' as a related concept (page will be created shortly). <a href="https://ncatlab.org/nlab/revision/diff/graph/93">diff</a>, <a href="https://ncatlab.org/nlab/revision/graph/93">v93</a>, <a href="https://ncatlab.org/nlab/show/graph">current</a>

    Adding ’semi-graph’ as a related concept (page will be created shortly).

    diff, v93, current

18. • CommentRowNumber18.
    • CommentAuthorOscar_Cunningham
    • CommentTimeJun 4th 2020
    • PermaLink
    Author: Oscar_Cunningham
    Format: MarkdownItexLinked to [[category of simple graphs]]. <a href="https://ncatlab.org/nlab/revision/diff/graph/94">diff</a>, <a href="https://ncatlab.org/nlab/revision/graph/94">v94</a>, <a href="https://ncatlab.org/nlab/show/graph">current</a>

    Linked to category of simple graphs.

    diff, v94, current

19. • CommentRowNumber19.
    • CommentAuthorUrs
    • CommentTimeAug 7th 2022
    • PermaLink
    Author: Urs
    Format: MarkdownItexmoving 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](http://en.wikipedia.org/wiki/graph) (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 $\leq$ 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. =-- *** <a href="https://ncatlab.org/nlab/revision/diff/graph/99">diff</a>, <a href="https://ncatlab.org/nlab/revision/graph/99">v99</a>, <a href="https://ncatlab.org/nlab/show/graph">current</a>

    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 $\leq$ 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.

    =–

    ---

    diff, v99, current

20. • CommentRowNumber20.
    • CommentAuthorperezl.alonso
    • CommentTimeJun 7th 2024
    • PermaLink
    Author: perezl.alonso
    Format: MarkdownItexpointer * Teo Banica. *Graphs and their symmetries* (2024). ([arXiv:2406.03664](https://arxiv.org/abs/2406.03664)). <a href="https://ncatlab.org/nlab/revision/diff/graph/104">diff</a>, <a href="https://ncatlab.org/nlab/revision/graph/104">v104</a>, <a href="https://ncatlab.org/nlab/show/graph">current</a>

    pointer

    • Teo Banica. Graphs and their symmetries (2024). (arXiv:2406.03664).

    diff, v104, current

21. • CommentRowNumber21.
    • CommentAuthorJohn Baez
    • CommentTimeNov 13th 2024
    • (edited Nov 13th 2024)
    • PermaLink
    Author: John Baez
    Format: MarkdownItexI 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'.) <a href="https://ncatlab.org/nlab/revision/diff/graph/105">diff</a>, <a href="https://ncatlab.org/nlab/revision/graph/105">v105</a>, <a href="https://ncatlab.org/nlab/show/graph">current</a>

    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’.)

    diff, v105, current

22. • CommentRowNumber22.
    • CommentAuthorThomas Holder
    • CommentTime6 days ago
    • PermaLink
    Author: Thomas Holder
    Format: MarkdownItexAdded a section on labelled graphs. <a href="https://ncatlab.org/nlab/revision/diff/graph/106">diff</a>, <a href="https://ncatlab.org/nlab/revision/graph/106">v106</a>, <a href="https://ncatlab.org/nlab/show/graph">current</a>

    Added a section on labelled graphs.

    diff, v106, current

23. • CommentRowNumber23.
    • CommentAuthorRodMcGuire
    • CommentTime6 days ago
    • PermaLink
    Author: RodMcGuire
    Format: MarkdownItexterminology quibble > The commutative diagrams one sees in texts on category theory or on the nLab are often examples of labelled graphs i.e. basically quivers with names attached to their directed edges. A "name" on a node or edge is unique and used for external reference. Labels can be used many times.

    terminology quibble

    The commutative diagrams one sees in texts on category theory or on the nLab are often examples of labelled graphs i.e. basically quivers with names attached to their directed edges.

    A “name” on a node or edge is unique and used for external reference. Labels can be used many times.

24. • CommentRowNumber24.
    • CommentAuthorThomas Holder
    • CommentTime6 days ago
    • PermaLink
    Author: Thomas Holder
    Format: MarkdownItexIf you want to change or even delete that introductory passage, just go ahead! A more realistic example might provide a better motivation for the concept anyway.

    If you want to change or even delete that introductory passage, just go ahead! A more realistic example might provide a better motivation for the concept anyway.