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.
Created digraph. Some background: this discussion. Created with permission, in the sense of
If you really want to split off material that is pertinent to digraphs in the graph-theorist’s sense, then I myself would have no objection to a new article “digraph”.
I think the disambiguation at the top is far too wordy and has too much inappropriately placed information. I would cut it down to “This article is about digraphs in the sense of ___ [keep it short!]. For directed graphs in the sense of ___, see ___.” Something as short as you can make it, and in just one (italic) font.
All those terms in boldface can go under a Definitions section. It is becoming traditional at the nLab to start with a brief Idea or Introduction section, maybe just a paragraph or two long in this case, in plain words and eschewing (for the most part) symbolism.
Peter, I second that comment by Todd. Your edits tend to exhibit a large ratio of minute miscellania over mathematical content. My suggestion is: First try to stick to the matter-of-fact style of math textbooks proceeding by numbered definitions/proposition/proof to get the content in place. When that core content is done, then there may be room for decoration left.
An elementary concept such as “digraph” should lend itself to exercising this. If you announce an entry on “digraph”, try to make it your ambition that it does contain the definition, and one or two basic properties, in established semi-formal math style. Then a paragraph in “Idea” at the top to orient the reader.
Agreed with #2 and #3. The comments about terminology should probably be in a separate section, after the definition.
Thanks for the comments. The state digraph is in was due to its being newly created, and a chunk of directed graph moved over to it wholecloth, to get things under way, and then having had to break off. Will improve soon.
Re #3
(EDIT: removed non-mathematical comments here.)
We have one example of such a thing already (documenting Power’s pasting schemes more-or-less-verbatim, independently of what I will make of them). Here I do not count digraph as a separate exercise; I am seeing that entry (currently) more or less as necessary for documenting pasting schemes.
One suggestion could be to resume the discussion on improving the nLab-coverage of the cartesian closed structure on presheaf categories over small categories which we had elsewhere, finding “the” correct treatment of the “funny” contender to the “correct” definition, doing it better than most texts, and making Todd’s relevant exposition elsewhere more available to readers.
Peter, you know what a standard math textbook looks like. If you are editing here, to first approximation your task is to produce material that looks roughly like that!
I suggest: Drop everything else you are doing, halt all the lengthy discussion on the nForum here (which will also give us time to catch up, we happen to have other duties, too) and bring digraph into a form that people could print it out and would have an article on digraphs as good as any chapter they might find in the textbooks.
A few first points, referring to the present state of the entry (which hopefully does not remain the present state for long):
The definition gets a numbered environment.
A numbered remark is added below that, relating the definition to those of just “graph” and other variants.
Citations are not of the form “Cf. e. g. p. 2”. I hope you see why that is weird. You have seen how we cite around here (or in any maths textbook), adopt that practice.
As you must have noticed by now, our sections “Related concepts” are a pure link-list to entries that the reader might also be interested in. You may remember this practice from printed encyclopedias back in the days. Conversely, anything that goes with actual text is not to be found under “Related entries” but under “Properties”, where you are asked to try to stick to standard semi-formal math mode.
It seems whimsical to have a list of terminology convention that makes up 90 per cent of the whole entry, whithout then being used. Once you do have a sizable amount of mathematics content in place in this entry, which does use this termimnology, then it may be time to add such a list.
As a rule of thumb: if discussion of terminology makes up more than five percent of the content of a maths page, then it is out of place.
I hope you take these comments in good spirit. But I’ll re-iterate the suggestion that for the time being you halt all other activity, and focus on just this entry digraph. It is your area of expertise (I suppose) it is elementary, it is fundamental, hence it is an ideal entry for you to get a feeling for what an Lab edit is meant to achieve.
The other regulars here show remarkable energy in following along your edits, so I am sure you will get much feedback and guidance as you work on digraph now. Once this is in acceptable shape, then (and only then), I suggest, you move on to editing the next entry. The experience there will then be much smoother for you and for us.
Re #7:
Urs, many thanks for the suggestions.
focus on just this entry digraph.
I’ll gladly do so, probably keeping it short though.
I am not primarily interested in writing a long entry on digraphs for their own sake on the nLab. I find the aspect of what is appropriate for the nLab very interesting and important, and currently the only “architectual” justification for treating it to me appear the pasting schemes. In particular since there already are quivers to cater to probably all other uses.
So again, digraph will be cleaned up soon.
For some of the small issues we are having, there are good mathematical reasons. For example, my hesitation to formally define “trail” is my respect for stylistic issues and the question how to fittingly present such a “negative” condition.
And “trail” is not mentioned for trails’ sake, but because Power in his proof of a pasting theorem makes crucial use of what I would call a “weakly connected trail”.
Thanks, Peter.
Right, the entry does not have to be long at all, and it should not be much work to bring it into decent shape. You now the topic, you don’t need to look up references, I suppose, so it should take about 20 minutes to produce a decent minimum entry.
Urs, thanks again. Brief notification:
state of the entry (which hopefully does not remain the present state for long)
digraph has now been put in something of a placeholder-state, for a reason, and will soon be finished. Not today though, but soon.
Added, complying with Urs’s suggestions, to digraph the sort-of-bare-minimum of what is necessary for a rigorous treatment of A. J. Power’s 1990 theorem on pasting schemes.
In particular, a rigorous treatment of plane digraphs is crucial for this.
The best treatment of plane undirected graphs I know of is in the fourth edition of R. Diestel’s textbook “Graph Theory”. I therefore made the design decision to adapt, with some significant changes, Diestel’s treatment to digraphs.
The list of axioms is the one I am currently working with in my private writings. My main iinterest (currently) is not digraph, but pasting scheme.
Have to interrupt for today. Intend to return to both pasting scheme and digraph soon.
There are several things to discuss, but presently I do not have time to spell them out. Only one small thing now: today I spent (perhaps too much) time, as an exercise, to try to find out whether in ZFC there is a short proof of the following, which would be relevant to digraph:
(d) if is a set and is a subset of , then .
This should be a proof of a few lines, or a reference to a good reference, but today I did not find one, in the time I allowed myself for it. Does someone know a proof/reference of (d)?
Maybe I’m misunderstanding, but that seems false. For example and is a counterexample (not even depending on a particular definition of ordered pairs).
Your statement (d) is a curio of material set theory, and in structural set theory it isn’t even a well-formed sentence (you can’t take the intersection of two arbitrary sets). Since the nLab default is the n-POV such things may distract from the actual mathematical content of graph theory.
Note also that if you report on every vague thought or personal question that arises to you while writing this page, then it will a) take up your time in writing it up here and b) take up the time of people who might wish to see a contentful summary of what changes you’ve made to digraph but have to wade through said written up personal questions.
I trimmed down the disambiguation at the top of the page, and made the Idea section less vague and more concrete. (There is too much repetition between nLab pages of the difference between digraphs and quivers, which is a simple enough distinction. This can be relegated to directed graph.)
Peter, there’s something odd-looking about your definition of walk. You write where is some ordinal. And yet you refer to where ranges over all of . So this means the actual domain of is , not .
There should be a definition of a map of digraphs (which, barring terminological subtlety, which is not worth discussing, can be mathematically unambiguous). Then adjectives as needed. A walk can then be a digraph map , where we take the digraph using the underlying non-reflexive relation on the ordinal. We can define a digraph map to be injective on vertices, and (completely) injective to be the obvious things, and thus get the definitions following that of walk in a model-independent way.
This way, the definitions are amenable to category-theoretic analysis, rather than foundational quibbles, like worrying whether .
I just added this example (of ordinal), but David’s right: from the nPOV, it’s always worth asking “what are the morphisms?” Then phrase fundamental notions in terms of morphisms.
I’m not very enthused about defining the length of a walk to be the cardinality of the underlying ordinal of a walk, since a walk is clearly longer than a walk (presuming both of those exist). This may be standard practice, but it’s losing information.
Continued with the more expository parts of digraph. Intend to return to this soon.
(Many thanks for the comments. Will not have time to discuss them now, but soon. Only so much now: David’s comment in 20 made me question just mimicking B-J–G’s definition of “walk”, and I changed my mind (and notes); it seems much better now, and the definition of “walk” now makes full use of digraphs not having parallel arcs: a consequence of this is that *walks are determined by a vertex-sequence alone”, which would not be true for quivers in general. Again, will return to this soon, in particular to pasting scheme. Have to double-check something first. Both digraph and pasting scheme seem to be in acceptable form to lie dormant for a short while.)
I’ve done a little rearranging for the sake of thematic flow. I’ll probably have a few questions later.
I’ve taken the liberty of adding more material to impart a categorical flavor to the subject. There is still a ways to go here, but a lot of notions that Peter had introduced are now finding their places in categorical niches.
For now the section “Miscellaneous notions” is merely a placeholder while things are being sorted out. Some of those will probably find a natural place in the categorical development, but I’m taking a break for the moment.
Quick question for Peter: in what is now definition 2.4 (copied over from what you had), there is the terminology “-vertex path”. Is that what it’s called in the literature? The problem is that “paths” in the sense to come later hadn’t been introduced, and so I guess what is really meant here is an “-vertex walk”. Correct? (I’d be tempted to just call it an “-walk”.)
Re 24
α\alpha-vertex path”. Is that what it’s called in the literature?
Yes, in a reasonably tolerant sense of “what it’s called in the literature”, yes.
I am personally strongly partial to always using this “-vertex path” (or walk, for that matter) terminology, which is not longer than the many usages using “length”, yet does away with the ambiguities besetting “length”.
Re 24 again
I guess what is really meant here is an “α\alpha-vertex walk”. Correct?
Yes, thanks for pointing out.
To remind all of us of this, the main justification for this terminology is that it makes full use of digraphs just being irreflexive relations, a consequence of which is that the vertex-sequence of a path-itself-construed-as-a-digraph already determines said path, hence paths in digraphs should be vertex-sequences from the out-set. Then, a “path”, strictly speaking, is not a digraph, but this definition is overall clearer and cleaner.
I didn’t really understand what you’re driving at in the second paragraph of #26, on several levels, but mainly this: how is this supposed to justify calling a walk a path? The terminology is very confusing.
Is “walk” itself standard terminology? Do other people say “-vertex path” but agree what is really meant here is not (necessarily) a path but a “walk”?
There seems to be a mistake in the formulation of “constructive acyclic directed graph”, in the condition
This can’t be right because the condition is trivially satisfied by the complete digraph, where is an arc whenever , and the complete digraph is as far away from being acyclic as you can get.
Now I think I know what was really intended here, but it seems to be most cleanly stated in terms of pullbacks in . A weak cycle in a digraph may (in notation recently introduced) be identified with a map . Form the pullback (leaving aside for the moment the issue of existence of pullbacks in )
Then a witness should indeed belong to the image of the function ; that was the first condition. This condition means that factors through the pullback, so we have an element again denoted (mild abuse of language). The second condition can be stated as saying that has two in-neighbors in , and no out-neighbors.
(There’s an unstated lemma in all this. One part of the lemma is the observation that weak 2-cycles in a digraph are automatically cycles. Another is that obstructions to directedness of weak cycles can be indeed reduced to this neighbor condition. I have no doubt this is an utterly standard lemma in graph theory.)
Todd, re 28, yes there was an oversight during too much “live” editing. Still, taking this so-to-speak-constructive reformulations seriously seems important, since Power uses more-or-less this “instantiation” of the concept of “acyclic”, namely:
I recognize that your last question gets to more essential things, and I will respond to this soon, yet to proceed methodically, and to make them easier to reference for you, I will first make some comments and ask some question, each time thinking it objectively justified to do so, more or less in separate comment.
EDIT: what I am getting at here is that currently I adopt a sort-of-chronological method of ordering the comments, going along the article in the direction it is currently displayed, rather than in a the-perceived-to-be-most-essential-thing-first-order; fo,r otherwise it seems to me the structure of the article could decrease rather than increase.
Please note that this to me seems an efficient method to collaborate on this article, to edit the small things out of the way first, and the intent is to further this project, which has considerable substance, some minor oversights notwithstanding.
In particular, Power’s proof seems correct, seems (after several email exchanges with people working decidedly in digraph theory) to use an interesting, correct and at the time of publication, new, lemma which does not seem to have found its way into the digraph theoretic literature, and builds a nice bridge between digraph theory and category theory.
If you disagree, and prefer a first-things-first-approach over the first-digest-the-recent-edits-thoroughly-approach, please let me know, and I’ll try to adapt to that.
Todd, small, more-or-less “type-theoretic” comment on the sentence
It is straightforward that Dgr is a full subcategory of the category of quivers Quiv.
Shouldn’t one be more careful and say that it is equivalent to one? The precise issue is an instance of intensional-vs-extensional: intensionally, Dgr is different from any subcategory of Quiv, since Quiv is not defined via relations, at least not set-theoretically-defined relations. Extensionally, Dgr is equivalent to a subcategory of Quiv. And then of course there is the issue that using the “s” and “t” functions that have recently been introduced, Dgr even intensionally at least looks the same as the nuts-and-bolts definition of Quiv. Maybe one could sum this up by:
[Technical note: I try to use “Todd,” at the start of the comments, to sort-of-address the comments primarily to more-or-less the person apparently interested in the article. This is neither to exclude others, nor to direct the comments too much on Todd, rather for readability/nuance/weighing/skippability of the comments.]
Todd,
Small things:
there is a left-out “the” in “implies that underlying set functor”
Do you agree that one should replace “We call this an ordinal digraph.” with “We call this an ordinal digraph and denote it by the respective ordinal itself. Note that is not a terminal object of , since does not have any terminal objects”. (Possibly over-expclicit, but the main reason I am bringing this up are the two facts that
in category-theory, more often than not,
in the hom-set expressions of the from the “1” does not denote the terminal object of , for the strong reason that does not have any terminal object.
Todd,
mainly this: how is this supposed to justify calling a walk a path? The terminology is very confusing. Is “walk” itself standard terminology? Do other people say “-vertex path” but agree what is really meant here is not (necessarily) a path but a “walk”?
We may be partly talking past each other. I try to answer as precisely as possible:
My answer in 26 is meant to explain the switch from “path-in-digraph-is-alternating-vertex-arc-sequence”, like in e.g. the monograph of B-J–G, to “path-in-digraph” is vertex-sequence, subject to an axiom which makes it more-or-less like the usual notion of path in topology, namely parametrized sequence of points, subject to constraints coming from the topology of the target space.
“path” in def. 2.4. should simply become “walk” , and, more precisely,
Yes, “walk”, by itself, for the rather weak notion of
is very common, and consistent with usages in graph theory, more or less since its inception.
Todd,
Do other people say “α\alpha-vertex path” but agree what is really meant here is not (necessarily) a path but a “walk”?
No, definitely not, this was an artifact of having accidentally left in the word “path” during reorganizing.
Todd,
your having introduced cyclic order into the article is wonderfully apposite, to the point that in the graph-theoretic literature, ternary relations are being used when doing formal proofs with embedded graphs: part of the reasons for the (probably still a little longer lasting) delay of a treatment of Power’s proof is my trying to eliminate irrelevancies, like the use of topological embeddings, and a central part in this is that
it seems to me that one should, at least in the non-historical, generalizing part of the nLab article,
and, when formally working with rotation systems,
so it is good to have them introduced in digraph.
It might be good to treat both the topological embeddins and the “combinatorial embeddings” (this is a rather usual technical term about which you can easily find more) in the article though, this is not meant to say one should eliminate the “plane digraph” definition altogether: it is more intuitive, and can be integrated with the newly-increased level of treatment of point-set-topology on the nLab, and these plane digraphs pose some interesting practical mathematics questions, regarding translation of classical definitions into constructive ones.
Todd,
two small things, to get them into a citable numbered comment:
Small things:
the notation chosen for the cyclic group with n elements is currently not consistent with (any of the variants visible on) the page cyclic group. I would recommend . When this issue comes up, I always remember a comment by G. Kuperberg somewhere online (I did not try to find it now), wherein he recommends this notation (I seem to recall that he even gives reasons, but I may misremember this).
on the point of using “monic” for injective functions: it seems likely that this is the preferred convention in the nLab (is it?); just in case it is not: currently, injective set-maps are called ’monic’ in the article, e.g. in “For suppose is monic.” wherein the map is just an injective set-map. Of course, monicinjective in , but to me it always sounds like a text is trying to emphasize that there is more structure than in in force when “monic” is used.
Todd,
Re the proof of Prop. 3.1., small thing, separately in a citable comment: it seems that one should
with (in particular with an internal nLab link)
“Since the hom-functor preserves limits preserves all limits, hence in particular preserves monos, so if …
since the current formulation can lead inexperience readers to believe that there is a reason specific to monos at play here, while the statement is true for much more general reasons (preservation of all limits).
@Peter
Shouldn’t one be more careful and say that it is equivalent to one?
By the principle of equivalence saying it is a subcategory is perfectly fine.
Re my comment in 37 (this is an example that having separately referencable comments is useful): thinking about it again, there is an issue with existence of pullbacks.
In a category which has all pullbacks,
preserving each pullback
implies
preserving monos.
How things are in Dgr I will have to think through.
Okay, thanks for these responses/suggestions.
Re “full subcategory”: I’m happy to insert the words “equivalent to”. I was going for the equivalence-invariant notion of full subcategory which is called “1-subobject” in subcategory. To what degree this relaxed practice has become standard, I don’t know, but you’re probably right that better safe than sorry.
Re #32, I’m happy to incorporate your suggestions there as well. I was thinking about a section “Categorical properties of ” where existence or non-existence of certain limits, colimits, etc. is discussed, including non-existence of a terminal object. Some of the content of “remarks on the definitions” you have could be worked into that discussion. The bad properties of result from the irreflexivity in combination with the definition of morphism; with just a slight modification of either and you get certain quasitoposes which are a very nice environment to be in. (Elsewhere you quoted Lawvere’s exasperated remarks on graph theorists and how they seem never to define precisely what category they’re working in, but it wouldn’t surprise me if some of them do think about such issues.)
We could remark in the section on paths, trails, cycles (which have in common the fact that they are all monic morphisms) that paths with domain are called “-vertex paths” by people like B-J-G, but I think I generally prefer to avoid that term altogether by writing locutions like “paths ”. (To me, “-path” as consonant with -walk makes sense and is a little less ungainly, but I don’t have to use that either.) An explanation of where “-vertex path” comes from might be an unnecessary side distraction, but let me mull it over. I’d want to keep any such explanation very brief.
Moving to global issues: I am a little concerned about this article becoming imbalanced by having such a focus on concepts used in Power’s article, but for now we can work with what we have and continue “labbifying” it (i.e., placing the concepts introduced into categorical narratives). As long as the article is well-structured, it probably wouldn’t be too painful to split it up later if need be.
I think it would also help me if I could get my hands on Power’s article. Would it be possible to send me a copy over email? If you’re not comfortable doing that, let me know, but my address is gmail dot com preceded by topological dot musings.
Re #36: IMO you shouldn’t worry much about things like that. I can change to (as I often use that notation myself anyway), but this is an extremely minor detail, and no one could misunderstand what was meant there even if it isn’t documented on the nLab.
Same with in #30. People can surely figure out such simple things for themselves.
Re #39: representables preserve monos even in the absence of pullbacks; this is immediately checkable even by inexperienced readers. I don’t think we need to go the route of reducing monos to pullbacks and then citing a result on the nLab that representables preserve limits and hence pullbacks; IMO that’s a bit overkill. (Although I do want to discuss pullbacks in .)
Todd, thanks for the answers.
but it wouldn’t surprise me if some of them do think about such issues.
I recognize this was not a question, and I think we should, and for an extended time, focus on the matters at hand, instead of getting into this larger question. Therefore, only briefly, summarizingly:
yes, many have and many do, especially the graph theory in and around the Charles University Prague; yet, if you want one, rather discursive (and rather old) article to start reading more on this, my suggestion would be the one of Bumby and Latch cited in directed graph
it will probably not surprise you that most of them time, in the graph-theoretical literature, homomorphisms are defined, but what the definition implies for the category in question is mostly ignored, the respective mathematician not having learned what category theory cares about; this is a cultural difference; mostly, the morphisms defined are immediately made a thing-to-be-studied combinatorially for its own sake (counting the number of homomorphsims , for example, or proving the existence of at least one (this may seem bizarre from a category-theoretic perspective) morphism between two given graphs with given properties combinatorially-given properties.
Again, such more-or-less-sociological matters can lead one astray; I try to keep to the mathematics of pasting schemes, by and large, at the moment. There is substance there.
The Bumby-Latch doesn’t point to anywhere at the moment, but I’m intrigued since this is probably Richard Bumby at Rutgers where I did my PhD. As you undoubtedly know, there is plenty of representation of graph theory at Rutgers and at DIMACS, but I had only brief discussions with people there about interactions between graph theory and category theory (I only recall talking about this with Michael Saks and Jeff Kahn, and as I say they were brief – I know rather more now than I did then).
Try this.
Ah, thanks Tim. I’ll add that in soon unless someone beats me to it.
The point of view there is indeed congenial to category theorists, but they tend to focus more on directed graphs and reflexive directed graphs as category theorists use those terms (multiple parallel edges as in quivers), which form presheaf toposes, whereas in articles such as category of simple graphs, there is an effort to look at the corresponding quasitoposes of -separated presheaves, which comes a bit closer to the traditional graphs of graph theory where there are at most single edges between vertices.
The article digraph is about the most straighforward definition of a category of graphs that graph theorists seem to implicitly consider, although that category is not especially nice. Still, one can do some things in it and it may be an interesting exercise to see how far one can take it, before making up one’s mind that it’s a lousy category after all and one would be better off shifting attention to something nicer. :-)
(Todd, just a small thing Re a half-question asked in #28:
Another is that obstructions to directedness of weak cycles can be indeed reduced to this neighbor condition. I have no doubt this is an utterly standard lemma in graph theory.
This is not a standard lemma, simply because graph theory is not sufficiently formalized for there to be any agreement how to prove this, or even whether one should write a proof of this. In graph theory, this, if addressed at all, would be dealt with in meta-language by saying “Take your non-cycle weak cycle, start (at any vertex) running around it; if you made it round the cycle without encountering an outdegree-two-on-the-cycle-vertex, you would have traced out a cycle, contradicting the hypothesis; hence there is a vertex satisfying the vertex condition.” In short, this is definitely not a standard lemma in graph theory, with citable standard references, or a name to it.
EDIT: sort-of-a-bridge from the question about how to characterize non-cycle weak cycles to the following passage about a standard lemma about finite acyclic graphs is: for cycles, it’s an “if and only if”, for general digraphs, of course only the implication (acyclic)(neighbor condition) holds, and one has to insert a hypothesis of finiteness.
Note: in the above, I took your question extremely literally, construing it to only ask for “weak cycle not-a-cycle if and only if there is out-degree-two-vertex”; if you are asking for whether there are quotable references of (a proof in usual logic of) the more general statement “Finite digraph acyclic only if there is at least one vertex with out-degree zero and at least one with in-degree zero.” then, yes, this is an utterly standard lemma in digraph theory, already appearing in Harary1969, Theorem 16.2, and also in B-J–G, 2nd, Prop. 2.1.1; note that “finite”, unlike for your question about “cycle”, which entails “finite”, is evidently a necessary condition: consider the countably infinite double-ray to get a counterexample if it is left out. Incidentally, note also tha the formulation of B-J–G, Prop 2.1.1 is one of the several reasons why I introduced, after discussions with people working in digraph theory, the terms “king” and “coking” instead of Power’s global “source” and “sink”: the modern standard meaning of “source” resp. “sink” is just this local “vertex with in-degree resp. out-degree zero” meaning, as e.g. used in Prop 2.1.1:
To sum up, what is an utterly standard lemma is “(finite acyclic)(there is a source and a sink)”, which “source” and “sink” in the standard modern sense, not in the BondyMurty-sense, yet this is only tangentially relevant to the current project to formally treat cycles and weak cycles on the nLab.
1 to 46 of 46