Not signed in (Sign In)

Not signed in

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

  • Sign in using OpenID

Site Tag Cloud

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 comma 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 finite 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 k-theory lie-theory limits linear linear-algebra locale localization logic mathematics 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

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

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • 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 nnForum 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 (88 cases, rather than 33 choices with 22 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 nn-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 XX is a category with

    • one object X 0X_0, called the object of vertices;

    • one object X 1X_1, called the object of edges;

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

    • together with identity morphisms.

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

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

    In fact, the only kind of graph above that can be defined as a functor from XX to SetSet for some fixed ’abstract general’ category XX 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 V2 VV \rightarrow 2^V rather than a subset of V×VV \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

    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.

    • 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 GG)==(cycle group with integer coefficients of GG 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!)

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

    diff, v93, current

    • CommentRowNumber19.
    • CommentAuthorUrs
    • CommentTimeAug 7th 2022

    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