@Alexis is that “homotopy category” the same one as the one you get from the model structure defined here?

]]>Added reference to “Homotopy in the Category of Graphs” paper.

]]>In general, category-names on the nLab tend to be a bit more verbose than people would use in common writing because of a need for global uniqueness. For instance, many topos-theorists write $Top$ for the 2-category of toposes, but we can’t do that because we use Top for the category of topological spaces (which is also very common), so we use Topos instead. So while $Sgr$ is fine for individual papers where it’s clear that the context is simple graphs, I think a more clear notation like $SimpGph$ is better for the nLab; for instance, $Sgr$ could also be an abbreviation for “semigroup”.

The answer to your question is no, there is no such “usual” notation.

]]>> common is to subscript the name of the category with the class of morphisms being considered if it is necessary to disambiguate

Along these lines, we get back to the question whether there is a "usual" way to denote a full subcategory C of a presheaf topos, in situations where C is more or less defined by a first-order condition on some of the set-maps $X(f)$, $f\in mor(C)$. Meanwhile, even if there is, it seems bound to be unwieldy, resulting in something like

usualnotationforfullsubcategoryofthosepresheavesXmakingthemap<X(*|->s),X(*|->t)>

aninjectivesetmap ( Set^{twosetswithfunctions^op})

Again, for brevity I would propose

Sgr

but am fine with another notation if others like it better. ]]>

But such long notation seems clearly not acceptable to most.

Yes; at the risk of sounding too dismissive I might respond that the point of *notation* is that it’s *shorter* than the corresponding English words. (-:

Using more cryptic abbreviations seems to convey the optionality of using this category better

I don’t think I have that reaction.

It is a problem in general that if there is more than one kind of morphism between a given class of objects, then naming the category after the objects is ambiguous. Some prominent category-theorists have in the past proposed that categories should really be named after their morphisms instead of their objects, but this hasn’t caught on since in most cases the objects do determine the morphisms “canonically”. There are a few exceptions like Rel and Prof where we do name after the morphisms because the objects are also the objects of some better-known category named after them (namely Set and Cat), but arguably those are really *double* categories being named after their horizontal 1-cells, which is a different convention to discuss. More common is to subscript the name of the category with the class of morphisms being considered if it is necessary to disambiguate; thus for instance we have $T Alg_l$ and $T Alg_p$ and $T Alg_s$ for the 2-categories of $T$-algebras with lax, pseudo, and strict morphisms respectively.

Personally, in my own manuscripts, I have resorted to just use the full version of what is (more or the less) the canonical English designation, in sans serif characters.This way one does not have to make such arbitrary and notational decisions, and modern technology makes this a viable option, in particular since it helps in not having to type the long version in order to produce it. (Yes, of course, one needs to have an idiosyncratic macro stored both in one’s own and in computer-memory, but this way one can spare others the abbreviation.). E.g. I always write $\mathsf{Quivers}$ instead of Quiv, and $\mathsf{AbelianGroups}$ instead of AbGrp or the like, both triggered by idiosyncratic macros. But such long notation seems clearly not acceptable to most. *Then* the question arises how to abbreviate. My suggestion was to apply the “functor” of “drop all the vowels and the plural-s” (and incidentally made the mistake of also dropping the “l”). To cut a long story short:

- I have solution for myself for this issue,
- this solution seems inacceptable publicly,
- I do not know how to decide about SimpGph.

I wouldn’t mind SimpGrph, and I don’t think I would even object to SimpGraph.

It seems to me that then one go for it and write it out as SimpleGraph, but *then* there is another issue:

- the closer you get to the plain English, the more it feels (to me) as if this is
*the*one and only category of simple graphs. (Using more cryptic abbreviations seems to convey the optionality of using this category better).

A theoretically and systematically-preferable alternative would be: * you identify one usual category-theoretic “operation” how SimpGph (in your sense) arises from the presheaf topos $\mathsf{Set}^{twosetswithallfunctions}$ * you invent a notation referring to this “operation” * you invent a notation similar to (I write heuristically, I do not intend the slice-category-meaning here) $\mathsf{Set}^{twosetswithallfunctions} / operation$

This would be “architectural” and systematic. It could be clunky though.

In summary:

*if*you have a clear preference, then, please, let it be known, and let us use this thenif in this case you prefer the choice to be made by someone else, I would prefer to reconsider and use the cryptic-yet-crisp

- Sgr

which in particular by its very non-intuitiveness does not feel like this the only simple graph there is.

]]>Yeah, I’ve reconsidered. Sorry, Peter. I’ve weighed the various options put forward by Mike, but decided I like $SimpGph$ the best after all. So I’ve rolled back.

]]>I could see an argument for SimpGra, on the principle that category-names are often just the first few letters of the name of the objects (Set, Cat, Ab, Alg, Mod). But Gra is probably no better than Gph. I wouldn’t mind SimpGrph, and I don’t think I would even object to SimpGraph.

]]>I think Mike has articulated well what prompted me to write $SimpGph$ in the first place (although I can imagine someone possibly puzzling over $Gph$). Maybe I should have deliberated longer.

]]>For what it’s worth, I prefer names to be pronouncable, so I prefer SimpGph over SmpGrph. Plenty of names of categories have vowels in them: we talk about Cat and Ab, not Ctgry and BlnGrp. And it takes an extra mental step for me to guess that “Smp” is an abbreviation for “Simple”, whereas with “Simp” it’s much easier.

]]>Sure, I can implement the change you want. Although I don’t see why it’s “more systematic”, the argument about pens carries some weight with me.

Edit: okay, done.

]]>Thanks.

Remarks:

symmetrically, one probably shouln’t expect too much from the new page, but I have few small things in mind, if I get round to carrying them out

renamed the page, giving it a title which is not as all-encompassing as the tentative one

a detail: this is entirely up to you, but personally I would prefer SimpGph to be renamed SmpGrph throughout your article: this is not longer but more systematic. Then the name is obtained by just dropping all vowels from “SimpleGraphs” (and, yes, dropping the plural-s, too, but this is customary, as in the names of the categories of groups and the category of sets). Also, then all letters used have one connected component only, which facilitates stroking them when writing with pen-like things. If you prefer to keep the name, it will be used on the separate page, too, though.

Looking forward

This is very much a side project for me (as are many things I add to the nLab), so I wouldn’t hold my breath for any fast-breaking developments. However, I might want to try out a few things in the near future, and of course I’d like to hear more what you have in mind on a separate page (as someone who really *does* know graph theory). I’ll see about performing the split.

Edit: okay, I’ve created the category of simple graphs from a graph-theoretic perspective and copied over the contents of what Peter had written from the previous revision. (Just a raw cut-and-paste.) The title can be regarded as a temporary placeholder if Peter doesn’t like it, and I hope he feels at his ease to edit and write whatever he likes there. I am gaining some confidence that the material can find a happy home at the nLab.

]]>On:

its own separate nLab article

I think you are right in thinking that the sections on the subcategories currently do not belong on the page category of simple graphs. On a superficial level

subcategories are not

*properties*(in any usual sense). While this of course could be remedied by restructuring the article, there of course remains the aesthetic issue of- the
*arbitrariness*of*which*subcategory to include into a general treatment like category of simple graphs. (If you have opinion of what subcategories*belong*to a treatment of a given category as a matter of course, then an interesting direction could be: you decide about the subcategory from a category-theoretic point of view, and then it is perhaps not clear what that subcategory corresponds to from a graph-theoretic point of view.) The decision which subcategory to analyze seems highly context-dependent to me.

- the

Feel free to remove both the full- and the wide-subcategories sections. Looking forward to read how you further develop the general treatment of category of simple graphs.

]]>Many thanks for these very helpful explanations.

]]>I was paraphrasing this from the previous revision

On Question (inequivalence). So far, not a single category-theoretic property has been mentioned which would distinguish any of the three from the others.

I was saying I don’t know what exactly it is you want here. One property is that $SimpGph$ is not a balanced category; this would distinguish regular monos from general monos. But perhaps it’s a moot point since those questions have been removed.

Edit: And not to harp on this since you might not wish to pursue it, but since I had to break off the above to meet a prior appointment, I’ll now complete the thought. The proposition is that any category in which all monos are regular is a balanced category, because then morphisms which are (epi and mono) are (epi and regular mono), but the latter are necessarily isomorphisms. That’s an easy exercise. So it suffices to observe that there are epi-monos in $SimpGph$ that are not isomorphisms.

Of course, you still have to prove that last fact for $SimpGph$, and the only way to do that is give an example, and for that you use the same simple example everyone uses: $1 + 1 \hookrightarrow 2$, the same example used to show that not all monos are regular in the first place. So while one could mention various categorical properties that distinguish different notions of mono, e.g., the property of not being balanced would distinguish regular from plain monos, in the end you still have to give an example, and it’s not clear how categorical reformulations really brought you any closer. In some cases they can help of course, but not in this case I don’t think.

(Side comment is that balanced quastitoposes are toposes.)

]]>One of the questions raised in your addition to the article mentioned that “not one category-theoretic reason” was given for the fact that $Mono \neq RegMono$.

This reaction is incomprehensible to me, but I’ll take it on faith that there is good reason for it, and am not asking for explanations (I read what you wrote). We may be talking at cross purposes. There exist categories $\mathsf{C}$ in which $Mono(\mathsf{C})=RegMono(\mathsf{C})$, for example if $\mathsf{C}$ is the category of sets, or the category of groups, or any elementary topos.

]]>In fact, I’m not going to wait for permission: at some point I’ll perform the split (unless someone else does it first), and see about including links from whatever-it-is-to-be-titled to category of simple graphs, where appropriate and subject to personal time constraints.

How about “the category of simple graphs from a graph-theoretic perspective”?

That’s fine. Peter of course is welcome to retitle it if he wants and we can of course talk about that.

]]>How about “the category of simple graphs from a graph-theoretic perspective”?

]]>One of the questions raised in your addition to the article mentioned that “not one category-theoretic reason” was given for the fact that $Mono \neq RegMono$.

Here we begin to get into “nuking mosquitoes” territory. If were asked, I’d probably give the same obvious example as most anyone else, that $1 + 1 \hookrightarrow 2$ is a non-regular monic. I mean, one *could* say something over-elaborate which would sound silly to most people, almost a parody of category-speak, such as the fact that $SimpGph$ is a quasitopos but not a topos, and give some nuking-mosquitoes reason for that, but in the end it would really come down to something simple-minded like that example. (That example actually being germane to the entire discussion, being essentially the one $\neg\neg$-dense sieve inclusion that determines $SimpGph$ as the full subcategory of separated presheaves.) So I’m left wondering what type of “category-theoretic reason” you’d want to hear.

Now more than ever, I think what you have added to category of simple graphs should be split off to its own separate nLab article.

]]>The type of an element of Hom(G,H) in that paper is different from “set-map $vertexset(G)\rightarrow vertexset(H)$”. It is “set-map $vertexset(G)\rightarrow setofnonemptysubsetsofvertexsetof(H)$”.

]]>Re #41: no, I did not ask such a question. However, I was wondering how “Hom” was being used in some such paper you referred to earlier, to cause you to advise using the $C(a, b)$ notation over the $\hom(a, b)$ notation.

]]>[an earlier comment was transmitted and received]

]]>In 12 of the thread “category of simple graphs with embeddings (proposed)” it was asked why category of simple graphs is not equivalent (in the usual sense) to the “category of graphs” $\mathsf{C}$ in the sense of European J. Combin. 30 (2009) 490-509, which is the category of symmetric relations, with morphisms precisely the relation-preserving set-maps between the ground-sets of two relations.

A reason is simply that the latter category $\mathsf{C}$ has non-initial objects $O_0$ (example: the non-looped one-vertex graph) such that there is another object $O_1$ such that the hom-set $\mathsf{C}(O_1,O_0)$ is empty.
On the other hand, the category SimpGph category of simple graphs has every hom-set *non-empty*, except those of the form $SimpGph(G, (\emptyset,\emptyset) )$, where $(\emptyset,\emptyset)$ is its unique initial object.

Briefly: $\mathsf{C}$ allows unlooped graphs.

But the reason is not as strong as in the case of the perhaps most straighforward sense of “category of graphs” (just taking the meaning *irreflexive symmetric relation* and making that a category), where there is *no* terminal object: $\mathsf{C}$ does have terminal objects, but it also happens to have some of its hom-sets empty (and hom-sets into non-initial objects at that), which SimpGph avoids by having all graphs looped.

It might be good to add a brief remark to category of simple graphs to the effect that SimpGph is inequivalent to all (or more precisely specified) “categories of graphs” heretofore studied. Whether to actually do so, and how, others should decide.

(Incidentally, is there a standard term for “hom-set of the form $\mathsf{C}(O,\o{})$ with $\o{}$ some initial object of the category $\mathsf{C}$” ? Such hom-sets need not be empty, but often are.)

]]>