# Start a new discussion

## Not signed in

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

## Site Tag Cloud

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

• CommentRowNumber1.
• CommentAuthorTodd_Trimble
• CommentTimeAug 24th 2012

A long time ago we had a discussion at graph about notions of morphism. I have written an article category of simple graphs which collects some properties of the category under one of those definitions (corresponding better, I think, to graph-theoretic practice).

• CommentRowNumber2.
• CommentAuthorTobyBartels
• CommentTimeAug 24th 2012

Can you say explicitly what the morphisms are?

• CommentRowNumber3.
• CommentAuthorTodd_Trimble
• CommentTimeAug 24th 2012

I did at the article. They’re the relation-respecting morphisms if we take “simple graph” to mean a set with a symmetric reflexive relation.

• CommentRowNumber4.
• CommentAuthorTobyBartels
• CommentTimeAug 24th 2012
• (edited Aug 24th 2012)

But what does ‘respecting’ mean? Reflecting, preserving, or both?

Looking further into the discussion, I guess that it must be preserving. So I’ve written in what I think it needs.

• CommentRowNumber5.
• CommentAuthorTodd_Trimble
• CommentTimeAug 24th 2012

Preserving, yes.

• CommentRowNumber6.
• CommentAuthorUrs
• CommentTimeAug 24th 2012

One question: maybe I am not concentrating: but is it supposed to be symmetric relations and undirected graphs?

• CommentRowNumber7.
• CommentAuthorUrs
• CommentTimeAug 24th 2012

Another thing:

I feel it is about time to have floating TOCs “Relations - contents” and “Graph theory - contents”. But maybe that should just be one single TOC?

• CommentRowNumber8.
• CommentAuthorTodd_Trimble
• CommentTimeAug 24th 2012

Urs, yes, the article considers graphs in the most common sense used in graph theory. That means in particular undirected (plus some other conditions: loop-free, without multiplicity). It might seem strange to use reflexive relations for loop-free graphs, but there’s actually a good reason for it, which the article tries to explain.

• CommentRowNumber9.
• CommentAuthorUrs
• CommentTimeAug 24th 2012

Right, sorry. I was indeed not concentrating. :-)

• CommentRowNumber10.
• CommentAuthorPeter Heinig
• CommentTimeJun 14th 2017
• (edited Jun 14th 2017)
Continued the section on the three wide subcategories of category of simple graphs a little. In particular, added a little section, still rough around the edges, on context and importance of isomorphic embeddings, emphasizing the concept of generalized points. Will not edit category of simple graphs further during the next twelve hours or so.
• CommentRowNumber11.
• CommentAuthorTodd_Trimble
• CommentTimeJun 14th 2017
• (edited Jun 15th 2017)

Hey Peter, let’s maybe slow down a bit.

The article (with now a very bloated table of contents) seems to be going off in a very particular direction which, if anything, I think would be better to split off to a separate article. Actually what it looks like is that you intend to write in effect a journal article or preprint on a specialized topic at the intersection of graph theory and model theory; e.g., you write

Our goal is to give a proof that

• Mor(SimpGph.IsometricEmbeddings) is not coherently axiomatizable in the sense that there does not any set $\mathbb{T}$ of coherent sequents such that Mor(SimpGph.IsometricEmbeddings)$=$ $\{ f\colon f\models \mathbb{T}\}$.

In any case, it’s unclear to me what exactly you are planning here, or generally how you are thinking of using the nLab to further your work. I think we need to get clearer on this.

In the past we’ve had a number of people who want to use the nLab as a home for their personal projects, and unless we know them well and see that their research fits in organically with the nLab, it’s usually not gone well and we’ve had to turn them away. So we really do need to exercise some caution at this point.

• CommentRowNumber12.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017
• (edited Jun 15th 2017)

The intent is mostly mathematical communication and mathematical understanding, like you write in the opening paragraph of category of simple graphs.

people who want to use the nLab as a home for their personal projects

This is not the goal, or at least, not for personal projects which do not futher the nLab. Editing the articles should mostly further the nLab of course. The current state of category of simple graphs is only temporary, and yes, a separate article for the wide subcategories would be sensible.

The current state of category of simple graphs is partly due to uncertainty

• when to use the sandbox,

• when to use the offline means,

• when to work directly in an existing article,

and exacerbated by various technical problems.

I know there is no universal answer to this. Will try to err more on the side of caution.

• CommentRowNumber13.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017
• (edited Jun 15th 2017)

• what is a usual term for the operation which associates to any category C
• the wide left cancellative subcategory D of C which has only the monos of C as its morphisms?
• the wide left cancellative subcategory D of C which has only the regular monos as its morphisms?

Then systematically go through all the properties you worked out for SimpGph and see what they imply for the respective subcategory, and document that. Only then go on asking further questions.

• CommentRowNumber14.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017

One particular point I would like to focus on for a while:

• pay more attention to what you worked out for the factorization systems, and illustrate you work with examples, etc. The “usual” epi-mono-factorization is much weaker than what you describe in your section of the article. Would you agree to have such a section within category of simple graphs?
• CommentRowNumber15.
• CommentAuthorUrs
• CommentTimeJun 15th 2017
• (edited Jun 15th 2017)

Peter, I find your section on “Three wide subcategories” does not read well at the moment. Besides trivial formatting issues (all cross-links/anchors are broken due to wrong syntax, overly heavy use of subsections for comparatively slim content, repeated code like “reftodo”) I find it has too high a ratio of prose not-to-the-point over content: The paragraph on trivia as to whether to put a subscript on the symbol for an identity morphism is longer than that concerning the actual definition of the three wide subcategories.

My suggestion is to do the following:

1. Remove all the subsections and have a single subsection “Subcategories” under the section “Properties”.

2. In that single subsection, proceed in a terse matter-of-fact Definition/Proposition/Proof style to bring your mathematical content into place.

3. When that is in place, then we can jointly look back at what we have and see if it justifies addition of general ruminations on the nature of category theory and notation.

• CommentRowNumber16.
• CommentAuthorTodd_Trimble
• CommentTimeJun 15th 2017

Re #14: I don’t know what you think is the “usual” epi-mono factorization, but there are two here:

• The (regular epi)-mono factorization,

• The epi-(regular mono) factorization

depending on whether you compose the middle factor of the ternary factorization over to the right or to the left, a situation described generally and in much more detail at ternary factorization system. (Both are useful.) Actually, I see that this is already said in the article, and the concrete description of regular monos and regular epis is pretty explicit I thought. If there are others who feel that examples are called for, we can put some in.

In fact the last sentence of that section was evidently written at a time when I was unaware that quasitoposes are coregular categories, so I can make the section even more succinct.

• CommentRowNumber17.
• CommentAuthorTodd_Trimble
• CommentTimeJun 15th 2017

Re #13: I would simply denote them as $Mono(C)$ and $RegMono(C)$, although I should warn that in general regular monomorphisms are not closed under composition. $Cat$ is an example where regular monos do not compose; there is discussion of this point at regular category (regular monos do compose in a regular category).

Then systematically go through all the properties you worked out for SimpGph and see what they imply for the respective subcategory

Well, I think it’s been recorded already. It was already observed that the underlying-set functor $\Gamma$ is faithful and therefore reflects monos, i.e., monos in $SimpGph$ are maps where the underlying function between sets of vertices is monic in $Set$ (injective). Regular monomorphisms, i.e., monomorphisms that arise as equalizers, are also easy to work out because $SimpGph(2, -): SimpGph \to Set$ preserves limits and therefore in particular equalizers. To be somewhat more explicit: limits in the full subcategory of separated presheaves are inherited from the ambient category of presheaves. I can go ahead and stick that in.

• CommentRowNumber18.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017

Thanks for the answers. Will try to implement Urs’ suggestions.

• CommentRowNumber19.
• CommentAuthorTodd_Trimble
• CommentTimeJun 15th 2017

Re #12: the part I quoted in #11 is still somewhat concerning to me, because it seems to take the article into rather specialized topics which seem more appropriate for a journal or preprint article. I’m trying to understand how the business of the model-theoretic aspects of isometric embeddings of graphs could really fit in organically at the Lab.

Regarding the introduction of the article and the bridge: it should not be interpreted as saying that the article would be written with an audience of graph theorists in mind. It’s biased much more on the side of category theorists who might be thinking of looking at some aspects of graph theory from a categorical point of view, with some notes which might assist them in crossing over.

There is in the nLab a constant balancing act, trying to find a comfortable level of presentation, avoiding the extremes of spoonfeeding and writing for the most elite among category theorists. FYI, my own standard is generally to try to write at a level that would be understandable to a 2nd or 3rd year graduate student who has had at least a year or two of serious categorical training and who is willing to work further in category theory, because my guess is that those who gravitate to the nLab in the first place might fit that description. The kinds of details such as those touched upon in the preceding comment become very routine for that kind of audience. The nLab being what it is, I don’t think we are writing primarily for people who need much of this kind of thing spelled out in great deal (such as graph theorists whose acquaintance with category theory is slight, relative to the audience I have in mind), although I might make some concessions on occasion.

Of course, I speak only for myself here. But my aesthetic sensibilities in such regards are very keenly felt, and right now I am uncomfortable with how your portion of the article looks, which stylistically is a very abrupt change indeed.

• CommentRowNumber20.
• CommentAuthorMike Shulman
• CommentTimeJun 15th 2017

While I agree with much of what Todd is saying, I don’t think that all nLab pages need to have the same audience. The primary pages on each topic should be written with a relatively consistent style and audience in mind; but I think there is room for other pages with other audiences. (Indeed, we do sometimes receive feedback that the average nLab page is written at too high a categorical level, even from people who I would have hoped would be in the intended audience, such as senior professors in topology or geometry with an interest in category theory.) It’s not as if we have a limited amount of space on the server; but it is the case that too much “bloat” in a given page makes it unreadable and less useful as a reference, and it is also the case that all nLab pages should fit somewhat within the overall mandate of “mathematics, physics, and philosophy from the nPOV”.

Therefore, I would be fine with having a separate page that’s like “the category of simple graphs for graph theorists interested in category theory”, where less categorical background is assumed — the present page being, as Todd says, more like “the category of simple graphs for category theorists interested in graph theory” — as long as that other page is also written from the nPOV and the relation between them is clearly spelled out with links.

I do also agree with Urs that the content-to-fluff ratio should be maximized, and moreover any fluff that is present should be directly relevant to the topic at hand. The nLab is a place for original work, and I do believe that there should be more interaction between category theory and fields like graph theory and model theory, and we often wish that we could attract more contributors. But we need to make sure that everything “fits together”, and this may be a learning process on both sides.

• CommentRowNumber21.
• CommentAuthorTodd_Trimble
• CommentTimeJun 15th 2017

While I agree with much of what Todd is saying, I don’t think that all nLab pages need to have the same audience.

I agree with that. I was mainly describing how I usually write in the nLab, and was complaining mainly about the inconsistency in style in the present article. We’ve had discussions about this kind of thing before, e.g., pages written for undergraduate topology students.

• CommentRowNumber22.
• CommentAuthorTodd_Trimble
• CommentTimeJun 15th 2017

Remark 3.2 in category of simple graphs gives some details touched upon in #17.

• CommentRowNumber23.
• CommentAuthorUrs
• CommentTimeJun 15th 2017
• (edited Jun 15th 2017)

I am all in favor of having presentations for different audiences (on different pages) and a page “category theory for graph theorists” might serve an excellent purpose.

What does not make sense, to my mind, is a lengthy discussion of notation for identity morphisms in the middle of a page that otherwise uses category theory freely. If such discussion is felt to be necessary, let’s move it to its own entry category theory for graph theorists!

A reader of an entry titled “category of simple graphs” must be expected to have a working knowledge of basic concepts and conventions of category theory. In any case, that page will not be the place to learn it. But it could usefully have a pointer at the beginning saying:

This page freely uses basic category theoretic terminology. Readers looking for background might want to first see category theory for graph theorists.

• CommentRowNumber24.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017
• (edited Jun 15th 2017)

May we use the labels “graph theorist” and “category theorist” less frequently?

Not that they were meaningless, and not that they should never be used (and I have, accidentally, used them too), but their use seems to do more harm than good, and they should be used less frequently. It is hard to think of situations where their use helps, but easy to see how they can get in the way of communication.

• CommentRowNumber25.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017
• (edited Jun 15th 2017)

Re # 16.

I don’t know what you think is the “usual” epi-mono

The word “usual” was indeed not clear: I meant the epi-mono-factorization in $\mathsf{Set}$, which of course, too, is not unique in the set-theoretic sense— there being a bijection between the permutations of the image(-set) and the epi-mono-factorizations—but which are unique in the vague sense of ” all notions of special epis and special monos coincide in $\mathsf{Set}$.

• CommentRowNumber26.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017

Re 17:

lthough I should warn that in general regular monomorphisms are not closed under composition. $Cat$ is an example where regular monos do not compose

Thanks for pointing out. Then there is a reason why it was not possible to derive this from the definitions.

• CommentRowNumber27.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017
• (edited Jun 15th 2017)

but it is the case that too much “bloat” in a given page makes it unreadable and less useful as a reference,

Entirely agree. Found the state of the section on the wide subcategories inappropriate, too. Like you may have noticed already, it has been removed.

• CommentRowNumber28.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017
• (edited Jun 15th 2017)

would be fine with having a separate page that’s like “the category of simple graphs for graph theorists interested in category theory”,

This might be useful. My main issues with this are:

• it is not clear what “for graph theorists” means. Depending on the interpretation, this amounts to the task of writing an introduction to category theory, for which there are many good introductions,
• the label “graph theorists” in the prospective title of that page; sure, writing “A for Bs” is a common genre, but personally I have my doubts about such titles.
• CommentRowNumber29.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017
• (edited Jun 15th 2017)

Re # 23.

In any case, that page will not be the place to learn it.

Entirely agree with Urs, which is why I have even removed the intended brief explanation of why the morphisms of SimpGph.RegularMonos (as combinatorially deifined) are precisely the regular monos: this would amount to an explanation of equalizers within category of simple graphs, which appears totally inappropriate. It has already been explained in detail in Section “Equalizers and coequalizers”.

• CommentRowNumber30.
• CommentAuthorUrs
• CommentTimeJun 15th 2017
• (edited Jun 15th 2017)

My main issues with this are: it is not clear what “for graph theorists” means.

It means just what you seem to be after. Clearly you have some particular audience in mind when you explain things like “unnatural isomorphisms” and the notation for identity morphisms etc. Much of the friction here results from some of us feeling this kind of explanation does not serve well on generic nLab pages. But since, evidently, you find that there is demand for this kind of explanation, the suggestion is: collect it all on one single page for background information! Call that page whatever you like, if “category theory for graph theorists” is not to your liking.

• CommentRowNumber31.
• CommentAuthorTodd_Trimble
• CommentTimeJun 15th 2017

Re #24: good point. Mathematicians are almost never just category theorists or just graph theorists or just anything, and any label which lends itself to stereotyping is something to watch out for. It could sometimes serve a descriptive function (e.g., I’ve heard Ross Street refer to the algebraist’s simplex category vs. the topologist’s simplex category), but “category theory for graph theorists” might be unwise.

Re #25: okay, I can insert a small note on this.

• CommentRowNumber32.
• CommentAuthorUrs
• CommentTimeJun 15th 2017

It’s not excluded that a single person may be an X-theorist and a Y-theorist at the same time.

• CommentRowNumber33.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017
• (edited Jun 16th 2017)

in general regular monomorphisms are not closed under composition. $Cat$ is an example where regular monos do not compose; there is discussion of this point at regular category (regular monos do compose in a regular category).

It eludes me (having scanned the page twice now) where, using notation suggested in #17, the non-composition-closedness of $RegMono(Cat)$ is mentioned in regular category.

EDIT: Of course, if one knows that ( $C$ regular category)$\Leftrightarrow$(any two composable regular monos compose to a regular mono), then the page mentions Cat in a relevant way.

Moreover (this was not claimed by you to be contained in regular category, I know), that page also seems not to contain the information that $RegMono(C)$ is composition-closed for any regular category, at least not transparently. The page hints at it, in the sense that if

• one reads until the Proposition at the end of Section “Factorization properties”
• knows that factorization system is taken to in particular imply closedness under composition,
• knows that one may “dualize” by replacing the pair “regular epimorphisms,monomorphisms” in the statement of that proposition by the pair “epimorphisms,regular monomorphisms”.

(Incidentally, the link labelled “factorization system” links to the page “orthogonal factorization system”; this may be intentional and good since that page is currently more developed than “factorization system”.)

Of course, the pages cannot cater to all needs, but it might improve the treatment to

• mention the examples of
• the category Cat,
• the category of semigroups,
• EDIT: also mention the example given by Todd_Trimble in # 37 of the thread “category of simple graphs” to give examples of categories in which there exist composable regular monos whose composition is not regular,
• mention that closedness holds for regular categories

• explicitly dualize the statement of the mentioned proposition.

(Know the “go ahead and improve it” policy, but it might be better for someone else to do so, and this is not urgent.)

• CommentRowNumber34.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017
• (edited Jun 19th 2017)

(…)

• CommentRowNumber35.
• CommentAuthorTodd_Trimble
• CommentTimeJun 15th 2017

Re #33: my apologies; I misremembered what was on that page. The example about $Cat$ on that page is that regular epis are not stable under pullback, which is one of the conditions for a regular category.

In fact, I must doubly apologize because I was conflating “monomorphism” with “epimorphism”; I should have said earlier that regular epimorphisms compose in a regular category. Regular monomorphisms compose in a coregular category.

So for now let me just link to place where the non-composability of regular monomorphisms is discussed: here. It’s not very satisfactory, but off the top of my head I don’t have a better example. Sorry to have made you chase down rabbit holes.

• CommentRowNumber36.
• CommentAuthorPeter Heinig
• CommentTimeJun 15th 2017
• (edited Jun 16th 2017)

(reconsidered.thanks)

• CommentRowNumber37.
• CommentAuthorTodd_Trimble
• CommentTimeJun 15th 2017

Okay, here’s maybe a better example: in $Cat$, let $\mathbf{2}$ be the arrow category. There’s a coequalizer

$1 \rightrightarrows \mathbf{2} \to \mathbb{N}$

where the parallel arrows are the two inclusions that name the two objects of $\mathbf{2}$, and $\mathbb{N}$ is the additive monoid of natural numbers regarded as a one-object category. There is also a coequalizer $\mathbb{N} \to \mathbb{Z}/3$ in $Cat$. But the composite is not a regular epi. For a related example, see Example 4.4 here. Thus, in $Cat^{op}$ the composite of regular monos need not be a regular mono.

I can add this example in later. Another more complicated example is in The Joy of Cats, 7J(a).

• CommentRowNumber38.
• CommentAuthorTodd_Trimble
• CommentTimeJun 15th 2017

I think I probably disagree with the entirety of the editorializing in #36, but I’ll have to return to this later.

• CommentRowNumber39.
• CommentAuthorPeter Heinig
• CommentTimeJun 16th 2017
• (edited Jun 16th 2017)

at37 I gather that #37 addresses, or adds to, the square-marked list in #33. Will add a reference to your example into that list, for further use if someone should decide to edit regular category

at38 Looking forward to reading more about it. No need to write much about it though; if you agree, then that is a reason not to make the changes; it was not claimed that these three points were errors. And I can imagine that one might prefer the more model-theoretic flavor of “amalgamation” in this context.

As to

, but $H$ is not a set.

This was to say “but $H$ is a set which is not an object of $\mathsf{Set}$” (and the only category I know where $\hookrightarrow$ goes without saying is $\mathsf{Set}$)

As to

various issues with

One issue is that usually one takes “limits of functors”’, not of objects (sure objects can be viewed as functors); another issues (probable not serious given that you direct the article primarily in a category-theoretic direction) is that within graph theory there is another notion of “limit of a graph”.

• CommentRowNumber40.
• CommentAuthorPeter Heinig
• CommentTimeJun 16th 2017
• (edited Jun 16th 2017)

Changed the names of the wide subcategories in category of simple graphs so as to (almost) implement the notation suggested by Todd_Trimble in #17. (For evident reasons having to do with the usual notation of hom-sets, a parenthesis-layer was omitted).

• CommentRowNumber41.
• CommentAuthorPeter Heinig
• CommentTimeJun 16th 2017
• (edited Jun 16th 2017)

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.)

• CommentRowNumber42.
• CommentAuthorTodd_Trimble
• CommentTimeJun 16th 2017
• (edited Jun 17th 2017)

[an earlier comment was transmitted and received]

• CommentRowNumber43.
• CommentAuthorTodd_Trimble
• CommentTimeJun 16th 2017
• (edited Jun 17th 2017)

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.

• CommentRowNumber44.
• CommentAuthorPeter Heinig
• CommentTimeJun 16th 2017

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)$”.

• CommentRowNumber45.
• CommentAuthorTodd_Trimble
• CommentTimeJun 16th 2017
• (edited Jun 17th 2017)

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.

• CommentRowNumber46.
• CommentAuthorMike Shulman
• CommentTimeJun 16th 2017

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

• CommentRowNumber47.
• CommentAuthorTodd_Trimble
• CommentTimeJun 16th 2017

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.

• CommentRowNumber48.
• CommentAuthorPeter Heinig
• CommentTimeJun 16th 2017

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.

• CommentRowNumber49.
• CommentAuthorTodd_Trimble
• CommentTimeJun 16th 2017
• (edited Jun 16th 2017)

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.)

• CommentRowNumber50.
• CommentAuthorPeter Heinig
• CommentTimeJun 17th 2017

Many thanks for these very helpful explanations.

• CommentRowNumber51.
• CommentAuthorPeter Heinig
• CommentTimeJun 17th 2017
• (edited Jun 17th 2017)

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.

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.

• CommentRowNumber52.
• CommentAuthorTodd_Trimble
• CommentTimeJun 17th 2017
• (edited Jun 17th 2017)

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.

• CommentRowNumber53.
• CommentAuthorPeter Heinig
• CommentTimeJun 17th 2017
• (edited Jun 17th 2017)

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.

• CommentRowNumber54.
• CommentAuthorTodd_Trimble
• CommentTimeJun 17th 2017
• (edited Jun 17th 2017)

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.

• CommentRowNumber55.
• CommentAuthorMike Shulman
• CommentTimeJun 17th 2017

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.

• CommentRowNumber56.
• CommentAuthorTodd_Trimble
• CommentTimeJun 17th 2017

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.

• CommentRowNumber57.
• CommentAuthorMike Shulman
• CommentTimeJun 17th 2017

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.

• CommentRowNumber58.
• CommentAuthorTodd_Trimble
• CommentTimeJun 18th 2017

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.

• CommentRowNumber59.
• CommentAuthorPeter Heinig
• CommentTimeJun 18th 2017
• (edited Jun 18th 2017)

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 then
• if 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.

• CommentRowNumber60.
• CommentAuthorMike Shulman
• CommentTimeJun 18th 2017

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.

• CommentRowNumber61.
• CommentAuthorPeter Heinig
• CommentTimeJun 18th 2017
• (edited Jun 18th 2017)

> 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.
• CommentRowNumber62.
• CommentAuthorMike Shulman
• CommentTimeJun 18th 2017

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.

• CommentRowNumber63.
• CommentAuthorAlexisHazell
• CommentTimeJan 8th 2019

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

• CommentRowNumber64.
• CommentAuthorAli Caglayan
• CommentTimeJan 8th 2019
• (edited Jan 8th 2019)

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

1. Fix grammatical typo

Anonymous

• CommentRowNumber66.
• CommentAuthorTodd_Trimble
• CommentTimeSep 11th 2019
• (edited Sep 11th 2019)

I refixed it to something better.