Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
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).
Can you say explicitly what the morphisms are?
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.
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.
Preserving, yes.
I have added some hyperlinks.
One question: maybe I am not concentrating: but is it supposed to be symmetric relations and undirected graphs?
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?
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.
Right, sorry. I was indeed not concentrating. :-)
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 of coherent sequents such that Mor(SimpGph.IsometricEmbeddings) .
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.
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.
A sytematic way to proceed could start with
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.
One particular point I would like to focus on for a while:
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:
Remove all the subsections and have a single subsection “Subcategories” under the section “Properties”.
In that single subsection, proceed in a terse matter-of-fact Definition/Proposition/Proof style to bring your mathematical content into place.
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.
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.
Re #13: I would simply denote them as and , although I should warn that in general regular monomorphisms are not closed under composition. 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 is faithful and therefore reflects monos, i.e., monos in are maps where the underlying function between sets of vertices is monic in (injective). Regular monomorphisms, i.e., monomorphisms that arise as equalizers, are also easy to work out because 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.
Thanks for the answers. Will try to implement Urs’ suggestions.
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.
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.
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.
Remark 3.2 in category of simple graphs gives some details touched upon in #17.
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.
Thanks for the comments.
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.
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 , 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 .
Re 17:
lthough I should warn that in general regular monomorphisms are not closed under composition. 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.
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.
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:
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”.
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.
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.
It’s not excluded that a single person may be an X-theorist and a Y-theorist at the same time.
in general regular monomorphisms are not closed under composition. 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 is mentioned in regular category.
EDIT: Of course, if one knows that ( regular category)(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 is composition-closed for any regular category, at least not transparently. The page hints at it, in the sense that if
(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 that closedness holds for regular categories
(Know the “go ahead and improve it” policy, but it might be better for someone else to do so, and this is not urgent.)
(…)
Re #33: my apologies; I misremembered what was on that page. The example about 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.
(reconsidered.thanks)
Okay, here’s maybe a better example: in , let be the arrow category. There’s a coequalizer
where the parallel arrows are the two inclusions that name the two objects of , and is the additive monoid of natural numbers regarded as a one-object category. There is also a coequalizer in . But the composite is not a regular epi. For a related example, see Example 4.4 here. Thus, in 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).
I think I probably disagree with the entirety of the editorializing in #36, but I’ll have to return to this later.
Thanks for the answers.
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 is not a set.
This was to say “but is a set which is not an object of ” (and the only category I know where goes without saying is )
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”.
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).
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” 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 has non-initial objects (example: the non-looped one-vertex graph) such that there is another object such that the hom-set is empty. On the other hand, the category SimpGph category of simple graphs has every hom-set non-empty, except those of the form , where is its unique initial object.
Briefly: 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: 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 with some initial object of the category ” ? Such hom-sets need not be empty, but often are.)
[an earlier comment was transmitted and received]
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 notation over the notation.
The type of an element of Hom(G,H) in that paper is different from “set-map ”. It is “set-map ”.
One of the questions raised in your addition to the article mentioned that “not one category-theoretic reason” was given for the fact that .
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 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 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 -dense sieve inclusion that determines 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.
How about “the category of simple graphs from a graph-theoretic perspective”?
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.
One of the questions raised in your addition to the article mentioned that “not one category-theoretic reason” was given for the fact that .
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 in which , for example if is the category of sets, or the category of groups, or any elementary topos.
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 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 that are not isomorphisms.
Of course, you still have to prove that last fact for , and the only way to do that is give an example, and for that you use the same simple example everyone uses: , 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.)
Many thanks for these very helpful explanations.
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
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.
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.
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.
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.
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.
I think Mike has articulated well what prompted me to write in the first place (although I can imagine someone possibly puzzling over ). Maybe I should have deliberated longer.
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.
Yeah, I’ve reconsidered. Sorry, Peter. I’ve weighed the various options put forward by Mike, but decided I like the best after all. So I’ve rolled back.
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 instead of Quiv, and 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 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:
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 * 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)
This would be “architectural” and systematic. It could be clunky though.
In summary:
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
which in particular by its very non-intuitiveness does not feel like this the only simple graph there is.
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 and and for the 2-categories of -algebras with lax, pseudo, and strict morphisms respectively.
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 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 is fine for individual papers where it’s clear that the context is simple graphs, I think a more clear notation like is better for the nLab; for instance, could also be an abbreviation for “semigroup”.
The answer to your question is no, there is no such “usual” notation.
@Alexis is that “homotopy category” the same one as the one you get from the model structure defined here?
I refixed it to something better.
1 to 66 of 66