(Context-adding comment re 70
Along the lines of #66, I’ve created signed graph.
just to add one piece of relevant context for future use in the newly created signed graph: there is some literature on homomorphisms between signed graphs, such as this by Éric Sopena et al.. Note that category theory is absent from that paper, barring one appearance in the bibliography. I do not mean to say that this should be the morphisms of the still-to-be-worked-out category $\mathsf{SignedGraphs}$. These morphisms should perhaps be suggested by category theoretical considerations, in particular, by what functors
$\mathsf{TetradirectedGraphs}$ $\rightarrow$ $\mathsf{BidirectedGraphs}$ $\rightarrow$ $\mathsf{SignedGraphs}$ $\rightarrow$ SimpGph
can be constructed with what definition of morphisms.)
]]>I may run out of steam responding to all this because I have other things to do, and your comments are numerous and long.
Actually, I do not even type-wise understand what you mean by
The most sensible approach along these lines would have to cut down on the size of $N$ so that its only elements are $+, -$, and some other element which I’ll call $0$.
Obviously I meant that axioms should be added so that in models, where sorts $V$ and $N$ are interpreted as sets, the set for $N$ is to have 3 elements. I think this is a very common type of notational overloading, where the same notation (here $N$) is used both as a formal symbol and for interpretations of that symbol. Usually the reader should figure out from context which is meant. I do this again below, so be forewarned.
Please note that in comment 86 I defined ’-’ and ’+’ to be names of elements of the set $\Sigma$-Fun, see
Yeah, I know. Specifically, they are constant (symbols) of type/sort $N$.
Do you have any particular “unintended consequences” in mind here?
Sure. The set $N$ becomes part of the data of what you intend to call a signed graph. Unless the axioms dictate otherwise, in a model, $N$ could be a set like $\{+, -, 0, 1, 2, \ldots\}$ where elements other than $+, -, 0$ are irrelevant dross or unintended stuff having nothing to do with the notion of signed graph. Thus you could have two models which look exactly alike as far as all the data that is relevant to signed graphs is concerned, but fail to be isomorphic because e.g. $N$ gets interpreted as an infinite set in one and a finite set in the other – differing cardinalities of dross. Thus signed graph isomorphism would not be reflected in model isomorphism.
Anyway, this business about constants $+, -$ seems reasonably cleared up now. It’s good you tell me of generalizations of signed graphs, with edge labelings in more general groups. That does help make this choice of signature seem more natural.
Personally, thinking about signatures helps me to orient myself in the literature.
This may be related to my point that choice of signature varies from author to author, so that that information would better fit the second table by author/reference work.
Do you think the author is consciously avoiding saying “relation” here?
Maybe, I don’t know. I was using the word “relation” informally, at a metalanguage level.
]]>Re #66 and #46, I’ve expanded oriented graph a bit to include also this more general sense of “oriented graph” (duplicating a bit of content that was already in graph).
]]>Todd, re 87
(If you don’t do this, then I think you’re going to have unintended consequences in your models.)
Do you have any particular “unintended consequences” in mind here? I do not see a reason why the additional axioms
…. axiom that says $\forall_{x: N} \; x = + \vee x = - \vee x = 0$, and also axioms $+ \neq 0, - \neq 0, + \neq -$. (If you don’t do this, then I think you’re going to have unintended consequences in your models.)
$\sigma(u, v) = 0$ if $u$–$v$ is false, as well as $\sigma(u, v) = + \vee \sigma(u, v) = -$ if $u$–$v$ is true.
that you give in 87 are necessary, though I have not yet thought about it yet.
Actually, I do not even type-wise understand what you mean by
The most sensible approach along these lines would have to cut down on the size of $N$ so that its only elements are $+, -$, and some other element which I’ll call $0$.
Please note that in comment 86 I defined ’-’ and ’+’ to be names of elements of the set $\Sigma$-Fun, see
$\Sigma$-Fun$:=$ $\{\sigma,-,+\}$, the anonymous type-assigning map stipulated by Johnstone being the map which
in 87.
More specificall,
… constants of the sort $number$ (I’ll call it $N$) […] cut down on the size of $N$ so that its only elements are $+, -$, and some other element which I’ll call $0$.
i.e., wrong to speak of a sort having elements. From what I learned,
and, as such, cannot have any elements, nor can you “cut down on [its] size.
Would you please clarify? What definition of “sort” were you using there?
]]>Todd, re 70
In fact, it’s obvious that signed graphs can be construed as a purely relational theory, by positing two relations $E_+$ and $E_-$ on $V$ satisfying suitable axioms.
First of all, you are right in the sense that this is often done, sort of, in parts of the literature. A textbook-example is Schrijver’s Trilogy, Volume C, Section 75.2. I say “sort of” because Schrijver’s signed graphs are specified triples $(V,E,\Sigma)$ with $\Sigma\subseteq E$, and with the element of $\Sigma$ being spoken of as “negative edges” and reasoned about in informal logic, first and foremost, counting the number of members of $\Sigma$ per cycle and calling those with an odd number of “negative edges” “odd cycles”.
Your definition is, moreover, exactly followed in what is arguably the first paper of signed graph theory, part of which is anticipated in Kőnig’s 1936 textbook.
However (and it seems that Zaslavsky agrees, when writing about Harary’s 1953 paper that “here is the first recognition of the crucial fact that labelling edges by elements of a group-specifically the sign group-can lead to a general theory” [my emphasis])
it seems to me that
Reasons:
to me it seems desirable to avoid using unnecessary words and predicates as much as reasonably possible, and instead strive for equational reasoning
if one defines derived notions like “odd cycle of a signed graph”, “balanced signed graph”, and, most importantly for the nLab,
it seems best to have a group structure on the set of signs, and to then multiply signs, and e.g.
This then is algebraic/equational reasoning. I am partly interested in doing formal proofs, and
if you use the relational approach, then you have to
Moreover, perhaps more importantly for the nLab, which one day should have a functor
which the combinatorial literature is still lacking,
it seems to me to be true that
the usual map $\mathrm{Ob}(\mathsf{BidirectedGraphs})\rightarrow\mathrm{Ob}(\mathsf{SignedGraphs})$ , which
cannot reasonably be defined if you do not have the signs present as part of the signature used (you cannot reasonably define a multiplication on your $E_-$), while if you have the $\sigma\colon edge\rightarrow number$ and a $\tau\colon vertex,\, edge \rightarrow number$ function symbols, you are free to have ’add-ons’ later.
]]>Todd,
Re 70
So “the signature” is not something determined by the category of structures and their homomorphisms, and one should pause to wonder if (or to what extent) signatures need to be set in stone.
Yes, certainly a signature is not a property of a category of structures (in any reasonable sense of “property” that I know of), regrettably perhaps. So, if done badly, listing a signature in a table, can be misleading. I was never meaning to suggest to readers something like “aha, the signature of digraphs is this”, or something like that. Whence the perhaps overly lengthy caveats in the table.
Yet to me it seems advisable to use signatures in directed graph, for pragmatic/systematizing/standardizing reasons. If one tells readers clearly and briefly that the choice of signature is a somewhat arbitray one, but does choose one for each of the variants of directed graphs, this seems, to me, to add structure.
Personally, thinking about signatures helps me to orient myself in the literature.
In my opinion one should simply use the usual conventions from categorical logic, for each of “digraph”, “quiver”, “bidirected graph”, “signed graph”, “Borisov-Manin directed graph”, making some reasonable arbitrary decisions for each, and listing them side by side in the table.
]]>Todd,
Re 82:
(2) The syntax of the definition of bidirected graph looks off. The turnstyle $\vdash$ is not a logical connective; it signifies an entailment relation between formulas, and the line * $\forall (v:V)$ $\forall (e:E)\qquad$ $v\in \bigcup d(e)$ $\qquad\vdash_{}\qquad$ $\neg(\tau(v,e)=0)\qquad\qquad$ doesn’t quite parse (the quantification doesn’t span across the entailment sign); it should be replaced with e.g. * $\forall (v:V)$ $\forall (e:E)\; v\in \bigcup d(e) \Rightarrow \neg(\tau(v,e)=0)$
Thanks for catching that. Yes, I simply abused $\vdash$, using it like $\Rightarrow$. Thanks for amplifying that. I will mark my old comment accordingly, to warn inexperienced readers, without hiding the error.
In #86 the sequent notation was correctly used, it seems to me.
Incidentally, you say “entailment relation”. Do you think there is a reason that Johnstone in Definition 1.1.5 of Volume 2 resorts to the circumlocution “[…] a sequent [is] a formal expression […]”, i.e. to the undefined “formal expression”?
Do you think the author is consciously avoiding saying “relation” here?
Probably this is a stylistic/expository decision, to avoid confusion, since he has recently defined “relation symbols” between sorts. It seems to me though, that using a sort called “formula” the author could make $\vdash_{\overline{x}}$ into a relation-symbol, literally.
]]>Todd,
Re 80
A page on an important subject like digraph theory deserves a larger point of view than to be a support-system or depository for another envisioned to-be-created specialized page. Thus, it might be wholly appropriate to include an important theorem like Robbins’ theorem on digraph. That’s the type of thing a reader might expect to see. Not a long list of definitions which is mainly for the purpose of a much more specialized theorem like Power’s theorem.
I certainly agree with this, yet I am surprised to see you see this this way. I take the principle of only adding things which make sense for category theory very seriously, at least as an intellectual exercise, and if I take this view, then I am led to not favoring writing an article on usual digraph theory, rather letting all material included be guided by category theoretical considerations.
However, if, like you at least seem to say, there is a wish around here to include some digraph-theory-style material, then I would be able and glad to do so. (Briefly, this would mean: the usual notions of connectedness, i.e. arc- versus vertex-connectedness, higher connectedness, Robbins’ theorem, the directed Menger theorem, flows). It seems wiser to first try to deliver something presentable on Power’s proof though, yet afterwards I could contribute some of the usual fare.
]]>Re 80,
Todd, many thanks for all the comments.
Listen, we’re still jiggering stuff around. It’s a lot of work trying to figure out how to reorganize the definitions sensibly and fit them into a coherent story.
I hear you. I agree.The most substantial issue in all of this seems, to me, that I do not deliver (an exposition of Power’s proof). There are reasons, yet it would be bad style to write about any. I am working to change this; it will take still a little while.
Re
Re #77: I propose creating Power’s pasting theorem for such a surgical purpose.
Re 80:
My own approach would be to write up Power’s theorem on its own page,
This seems to be a good approach.
]]>In general I agree with everything Todd is saying. In particular, digraph is not the place for any sort of discussion of Power’s work or of definitions that are specific to it. However, as a slight moderation to #80 I would say that I think it’s okay to create a page A mainly because one needs it to “support” another page B, even if the resulting content at A is somewhat lopsided and incomplete because of the original author’s limited interest in A as a means to B, as long as the content that is placed on the page A is about A in general (e.g. standard terminology and theorems about A, even if a somewhat idiosyncratic choice of such to include) rather than about the use of A in B.
]]>Well, now you’re at least trying to spell out the signature. Before it was really confusing what you had in mind, which is why I asked.
Please note that Johnstone allows multi-sorted signatures, whereas in many logic books they don’t even refer to the set of sorts of a signature; they just refer to function, relation, and constant (symbols). That traditional type of signature could be called “mono-sorted” by categorical logicians. The (Tarski-style) interpretation of the (usually unspoken-of) sort is just this set $\dom(A)$.
Anyway, let’s see. So you wish to interpret $+, -$ as constants of the sort $number$ (I’ll call it $N$)?
Ultimately I think such an approach is doable, but in order to really nail it down, you’re going to have to add more axioms, and the result is going to be cumbersome, and I think people would laugh at it.
The most sensible approach along these lines would have to cut down on the size of $N$ so that its only elements are $+, -$, and some other element which I’ll call $0$. So have exactly 3 constants of sort $N$, and then add an axiom that says $\forall_{x: N} \; x = + \vee x = - \vee x = 0$, and also axioms $+ \neq 0, - \neq 0, + \neq -$. (If you don’t do this, then I think you’re going to have unintended consequences in your models.)
Then have an axiom $\sigma(u, v) = 0$ if $u$–$v$ is false, as well as $\sigma(u, v) = + \vee \sigma(u, v) = -$ if $u$–$v$ is true.
Together with the rest of your axioms.
Personally I think it would be much simpler to go the two relations $E_+, E_-$ route, but in summary reply, yes you can define a theory of signed graphs according to your sketched suggestion, a multi-sorted theory which includes two or three constants for one of the sorts and no other elements, but it looks pretty silly to insist on this as being “the signature” for signed graphs.
do you agree that both Hoges and Johnstone give, in their various ways, some sort of licence to call - and + “constant symbols”?
Johnstone: yes, if done right. Hodges – I think I have a copy of his book somewhere, but the answer is again yes if he discusses multisorted signatures or structures; if not, then I don’t see that he’s given “license” in his book, although if he were pressed on the matter in person, I can imagine his giving an airy shrug of the shoulders.
]]>Terminological comment, background citations for further possible use in composing tables
Todd,
For the category-theoretic reference, consider P.T.Johnstone: Sketches of an Elephant, Volume 2:
Definition 1.1.1 A (first-order) signature $\Sigma$ consits of the following data.
(a) A set $\Sigma$-Sort of sorts.
(b) A set $\Sigma$-Fun of function symbols, together with a map assigning to each $f\in\Sigma$-Fun its type, which consists of a finite non-empty list of sorts (with the last sort in the list enjoying a distinguished status): we write $f\colon A_1\cdot\cdot\cdot A_n\rightarrow B$ to indicate that $f$ has type $A_1,\dotsc,A_n,B$. (The number $n$ is called the arity of $f$; in the case $n=0$, $f$ is more usually called a constant of sort $B$.)
(c) A set of $\Sigma$-Rel of relation symbols, together with a map assigning to each $R\in\Sigma$-Rel its type, which consists of a finite list of sorts: we write
$R monoarrow A_1\cdot\cdot\cdot A_n$
to indicate that $R$ has type $A_1,\dotsc,A_n$. (The number $n$ is called the arity or $R$; in the case $n=0$, $R$ is more usually called an atomic proposition.)
What is wrong with taking this as a licence to define the signature of signed graphs to be the folowing:
Let
$\Sigma$-Sort$:=$ $\{$ $vertex$ , $number$ $\}$
where $vertex$ and $number$ are to be taken to be just names for elements of a set, possibly to be interpreted elsewhere according to what their telling names suggest, in particular in proofs in which one need to have some arithmetic structure on the signs (which e.g. can be useful to define the basic signed-graph-theoretic notion of ’odd circuits’ via multiplication, instead of having to resort to an ’IsOdd’-predicate).
$\Sigma$-Fun$:=$ $\{\sigma,-,+\}$, the anonymous type-assigning map stipulated by Johnstone being the map which
maps $\sigma$ to the list $vertex$ $vertex$ $number$,
maps - to the list $number$,
maps + to the list $number$.
(Note that the $A_i$ lists are empty here; in particular the arity of both $-$ and $+$ is $0$.)
and $\Sigma$-Rel$:=$ $\{$ $\text{--}$ $\}$,
with $\text{--}$ being a relation-symbol,
the anonymous type-assigning map herebeing the map which
maps $\sigma$ to the list $vertex$ $vertex$.
The axioms of the theory of signed graphs then should be the four axioms
(irr) $\mathsf{T}\qquad \vdash_{v: vertex} \qquad \neg ( v\text{--} v)$,
(symm) $u\text{--} v\qquad \vdash_{u,v: vertex} \qquad v\text{--} u$,
(sign.symm.neg) $\sigma (u,v) = - \qquad \vdash_{u,v: vertex} \qquad \sigma (v,u) = -$,
(sign.symm.pos) $\sigma (u,v) = + \qquad \vdash_{u,v: vertex} \qquad \sigma (v,u) = +$ .
In particular, - and + here are function symbols of arity 0 hence constant symbols in the sense of Johnstone.
Just for my own peace of mind, setting aside whether one should use ’constant symbol’ in directed graph,
To my mind, this post is to the point; it tries to answer to a question of Todd’s what sense to make of my use of “constant symbols”.
I will have to interrupt for today now.
]]>Peter, where Hodges says
The elements of dom($A$) are called the elements of the structure $A$.
He is telling you that “elements of $A$” means “elements of $\dom(A)$”. Thus, when he follows with
A set of elements of $A$ called constant elements
he means a set of elements of $\dom(A)$ called constant elements. In other words, a subset $Const(A) \subseteq \dom(A)$.
Yet for the time being I would just like to know whether I overlooked/misapprehended something, on the bare logical/terminological/readingcompetency level.
If you think it meant anything other than what I just said, then I think you really misunderstood.
Where you quote Monk, you should probably examine what he says about interpreting the various items of a signature. (I don’t know what he says, I don’t have the book, but even blindfolded I would ask you to look that up.)
It doesn’t matter a whit that he doesn’t call them constant symbols. I might say “constant symbol” to signify that this is part of syntax, and then I can refer to a “constant” in a structure $A$ when interpreting a constant symbol in a structure.
In particular, Monk seems to have decided not to make the connection ’constants are 0-ary function symbols’, as far as I can see from his text. Do you agree?
Not that this seems relevant to what we’re discussing, but:
As I say, I don’t have the book, but I’m certainly prepared to agree, because for some reason, traditional logicians almost never lump in constant-(symbols) with function symbols. To a categorical logician it makes perfect sense to do so, however. Perhaps “aversion to the void” of having $0$ as an admissible arity, or some old-fashioned attitude like that. I don’t know.
]]>Terminological comment, mostly background literature quotes
Todd, Re # 83:
For the model theoretic references, consider the well-known book Hodges, A Shorter Model Theory, First Edition, and therein Section 1.1 “Structures” which says:
A structure $A$ is an object [I think with ’object’, Hodges here fait la prose sans le savoir, since categories only rarely appear in his book] with the following four ingredients. (1.1) A set called the domain of $A$, written dom($A$) or dom $A$ (some […]). The elements of dom($A$) are called the elements of the structure $A$. […] (1.2) A set of elements of $A$ called constant elements, each of which is named by one or more constants. If $c$ is a constant, we write $c^A$ for the constant element named $c$.
Apart from the minute terminological issue that I wrote “constant symbol” (which I think even clearer, to mark them out as names) instead of Hodges’ “constant” to refer to the names - and +, it seems to me that Hodges’ definition of “constant” is so permissive as to make my use of “constant symbol” consistent with Hodges’ book: note that he does not require dom($A$) and the set that he calls “a set of elements of $A$ called constant elements” to have anything to do with one another, nowhere does he write something like
Constants(A)$\subseteq$dom($A$).
Hodges takes ’$A$’ to be nothing else than something of a ’record’, so to speak, that one can apply ’operators’ like dom(.) and ’constants of (.)’ to, and the resulting sets upon applying these ’operations’ need not have anything to do with one another.
Note Hodges does not write ’The elements of $A$ are [..]’, rather “The elements of dom($A$) are […]’
Upon reflection, I might agree that these are strangely permissive definitions of “constants, allowing one to call just about anything a “constant symbol”, more precisely, allowing one to simply take any set one likes to be the “set of constants of the structure $A$”, which indeed seems not very structural.
Yet for the time being I would just like to know whether I overlooked/misapprehended something, on the bare logical/terminological/readingcompetency level.
It seems to me that I didn’t; consider, for additional evidence, e.g. these lecture notes of J.D.Monk tell us
A signature or […] is an ordered quadruple $\sigma$ $=$ (Fcn,Rel,Cn,ar) such that Fcn, Rel, Cn are pairwise disjoint sets, and ar is a function mapping Fcn$\cup$Rel into $\omega\setminus 1$. Members of Fcn, Rel, Cn are called function (or operation) symbols, relation symbols, and individual constants, respectively. […] The members of Cn are called individual constants. One might think of the function and relation symbols as constants of a different sort. [note that Monk here does not say ’constant symbols’]
Seems completely permissive to me. In particular, neither Hodges nor Monk demand that ’-’ and ’+’ be elements of $V$.
In particular, Monk seems to have decided not to make the connection ’constants are 0-ary function symbols’, as far as I can see from his text. Do you agree?
]]>Todd, re #70
because I don’t know what sense to make of that. If a signed graph is a structure on a set $V$, then a “constant” in the signature when interpreted in a structure is simply an element of $V$. I took it that in the quoted sentence you (Peter) meant the sign symbols $\{+, -\}$ to be constants, but that doesn’t make sense under how constants are standardly interpreted.
Todd, many thanks for these comments.
Still, I did exercise some “due diligence” (as they say) when I wrote “constant symbols”, and it still seems to me that my use of “constant symbols” was justified, at least by some standard references. I do not see why this is not a standard use of the term “constant symbol”.
Permit me to adduce two usual references, which to have quoted in this thread seems not useless, one from the more model-theoretic literature, the other from the more category theoretic one.
For referenceability, I post two relevant literature references in separate comments.
Please note: I recognize that these posts are not brief, yet they are mostly citations from textbooks, I will clearly mark them as such, so they should be clearly recognizable to be skippable and unimportant to anyone not interested in this particular terminological discussion.
]]>Some remarks on #55:
(1) There was a question raised about defining the incidence relation for a simple undirected graph, given by a pair $(V, E \hookrightarrow \binom{V}{2})$. The suggestion was to treat these entities as material ZF-sets and use the ZF operation of taking a union.
A structural option would be to view $\binom{V}{2}$ as a quotient, $q: V \times V \setminus \Delta \to \binom{V}{2}$, sending $(x, y)$ to the orbit of the evident involution $(x, y) \mapsto (y, x)$. Then define the incidence relation $I(v, e)$ by $\exists_w\; q(v, w) = e$. (With $q$ read as given, this can easily be expressed in the language of finite limits.) You come close to saying something like that under the third bullet of Remarks in #55, except at the end you revert to another ZF-ism about Kuratowski ordered pairs.
(2) The syntax of the definition of bidirected graph looks off. The turnstyle $\vdash$ is not a logical connective; it signifies an entailment relation between formulas, and the line
doesn’t quite parse (the quantification doesn’t span across the entailment sign); it should be replaced with e.g.
(But you can also just explain the concept in words without using the symbolism of formal logic. Cf. section 14 of Halmos’s excellent paper on writing mathematics. The picture under the sixth bullet point of Remarks is helpful in getting the idea of bidirected graph across; as earlier mentioned, I think this concept can also be described in terms of subdivision.)
]]>digraph seems an acceptable temporary place for these notions, and you know, one has to start somewhere
That’s where I disagree. The large mass of definitions collected at digraph made for a mess which then has to be sorted through by someone later. In my opinion, the somewhere that one starts at in this case is by writing the relevant mathematics from the bottom-up, at a page where the express purpose is adumbrated in the title.
I think it would be fine for example to state Power’s theorem at pasting scheme (or wherever). If it would be too unwieldy to include the proof there, a separate page can be created for that purpose.
(But even before one starts writing, it would be well to know what one is going to write. Personally, I would try to understand clearly what Powers has done first.)
]]>Re #77: I propose creating Power’s pasting theorem for such a surgical purpose.
nLab pages should be constructed with a bit of thought once they reach a certain length. A page on an important subject like digraph theory deserves a larger point of view than to be a support-system or depository for another envisioned to-be-created specialized page. Thus, it might be wholly appropriate to include an important theorem like Robbins’ theorem on digraph. That’s the type of thing a reader might expect to see. Not a long list of definitions which is mainly for the purpose of a much more specialized theorem like Power’s theorem.
Listen, we’re still jiggering stuff around. It’s a lot of work trying to figure out how to reorganize the definitions sensibly and fit them into a coherent story. My own approach would be to write up Power’s theorem on its own page, and certainly some (brief) mention of this specialized topic would not be totally out of place at digraph. Then we can see what definitions from a Power’s theorem page should be linked elsewhere.
]]>Todd, Re 74,
one could summarize it thus: I agree that some of the necessary concepts for Power’s proof should perhaps go to the very page pasting scheme, if the proof is documented there, it was just that at the time of writing, pasting scheme did not yet seem to me a fitting place for the notions like king, coking, plane digraph, a-b-path. (Imagine all of these in pasting scheme, with Power’s proof still missing; digraph seems an acceptable temporary place for these notions, and you know, one has to start somewhere.)
]]>and it seemed to be foreseeable that users seeing something directed-graph-like might go “hmm, looks like a directed graph, let’s search for ’directed graph’
And they should indeed find it there, either via ctrl-F or under Related Concepts.
Possibly I can see an argument that “oriented graph” could redirect to digraph, even though it’s a pretty special case. But “signed graph” is a completely distinct concept, and so is “bidirected graph”. I think one shouldn’t redirect either of those to directed graph, for example.
]]>Re 74
I imagine there are scores, maybe hundreds of individual concepts that appear in digraph theory, but digraph need not and probably should not be a dumping ground for all of them.
Thanks for this view. This really surprises me since I had taken care ( excepting the currently accidentally mistaken experimental definition of constructive DAG ) to only include what is necessary to conveniently document JAlg129. Please note the sentence
The choice of definitions documented here is biased towards (one of) the uses digraphs are put to in category theory, in particular in giving a rigorous justification of pasting diagrams. The most salient example of this is the emphasis given to plane digraphs in this article.
in digraph. It is a selection made with a purpose (from a digraph-theoretical perspective, it would for example be strange that no notion of higher connectedness of digraphs is covered, digraph-theorists would for example miss Robbins’ theorem, which one can arguably call the first theorem of digraph-theory, but this was not covered since this is not necessary to Power’s proof).
So if we are still aiming at one day creating a good documentation of Power’s Pasting Theorem, like you once seemed to agree, then the “miscellany of concepts” is rather a small select toolbox.
]]>Re 73: thanks Todd, this is an interesting opinion. I personally thought to do precisely the thing you caution against, just not thinking of it negatively as a “dumping ground”, rather as the most natural and useful place on the nLab for various notions of directed graphs, just because “directed graph” is, to me, so undefined, and it seemed to be foreseeable that users seeing something directed-graph-like might go “hmm, looks like a directed graph, let’s search for ’directed graph’ “. But, again, it is interesting that you think this is not a good idea.
]]>(accidentally reposted last message)
]]>Re #69: there are surely some things to say about flags and various functorial constructions on various categories of graphs, such as a suitable subdivision functor. Certainly I believe bidirectional graphs could be usefully compared to structures on subdivided graphs. But the placement of this type of material on the nLab should be given some consideration.
On a slightly related note, regarding placement: I’m not happy with the shape of digraph, particularly with the miscellany of concepts. I imagine there are scores, maybe hundreds of individual concepts that appear in digraph theory, but digraph need not and probably should not be a dumping ground for all of them. More useful I think from an nPOV is to outline the most important categorical properties and the most important functorial constructions (e.g., the functor $Symm$ does seem useful, and maybe subdivision merits some discussion). That would help to give the page cohesion. Concepts can be added to a Related Concepts section on an as-needed basis.
]]>