(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)$\Rightarrow$(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)$\Rightarrow$(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.
]]>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 $\neg\neg$-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 $\mathsf{Dgr}$ 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. :-)
]]>Try this.
]]>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).
]]>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.
]]>Re #36: IMO you shouldn’t worry much about things like that. I can change to $\mathbb{Z}/n$ (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 $Quiv$ 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 $\mathsf{Dgr}$.)
]]>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 $\mathsf{Dgr}$” 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 $\mathsf{Dgr}$ 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 $\alpha$ are called “$\alpha$-vertex paths” by people like B-J-G, but I think I generally prefer to avoid that term altogether by writing locutions like “paths $\alpha \to D$”. (To me, “$\alpha$-path” as consonant with $\alpha$-walk makes sense and is a little less ungainly, but I don’t have to use that either.) An explanation of where “$\alpha$-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 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.
]]>@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.
]]>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 $U$ 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).
Todd,
two small things, to get them into a citable numbered comment:
Small things:
the notation $\mathbb{Z}/(n)$ 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 $\mathbb{Z}/n$. 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 $\mathbb{Z}/n$ (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 $U(f)$ is monic.” wherein the map is just an injective set-map. Of course, monic$=$injective in $Set$, but to me it always sounds like a text is trying to emphasize that there is more structure than in $Set$ in force when “monic” is used.
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,
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,
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 “$\alpha$-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,
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 $1$ is not a terminal object of $Dgr$, since $Dgr$ 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 $Dgr(1,-)$ the “1” does not denote the terminal object of $Dgr$, for the strong reason that $Dgr$ does not have any terminal object.
[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, 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:
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.
]]>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 $(u, v)$ is an arc whenever $u \neq v$, 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 $\mathsf{Dgr}$. A weak cycle in a digraph $D$ may (in notation recently introduced) be identified with a map $p: Symm(Z_n) \to Symm(D)$. Form the pullback (leaving aside for the moment the issue of existence of pullbacks in $\mathsf{Dgr}$)
$\array{ C & \to & D \\ \downarrow & & \downarrow \mathrlap{u_D} \\ Symm(Z_n) & \underset{p}{\to} & Symm(D) }$Then a witness $z(p)$ should indeed belong to the image of the function $U(p)$; that was the first condition. This condition means that $z(p): 1 \to D$ factors through the pullback, so we have an element again denoted $z(p): 1 \to C$ (mild abuse of language). The second condition can be stated as saying that $z(p)$ has two in-neighbors in $C$, 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.)
]]>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 “$\alpha$-vertex path” but agree what is really meant here is not (necessarily) a path but a “walk”?
]]>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.
]]>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 “$r$-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”.
]]>Quick question for Peter: in what is now definition 2.4 (copied over from what you had), there is the terminology “$\alpha$-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 “$\alpha$-vertex walk”. Correct? (I’d be tempted to just call it an “$\alpha$-walk”.)
]]>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.
]]>