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.
1 to 21 of 21
Like suggested by someone else in this forum, here I propose creating an article, but will wait for agreement or disagreement before creating it.
The article would be called
category of simple graphs with embeddings
and would
be partly modelled on, and aiming for consistency with, the article category of simple graphs
treat and compare at least three wide subcategories of category of simple graphs, namely
(weak.emb) countable simple graphs with weak graph-embeddings
(strong.emb) countable simple graphs with all strong graph-embeddings
(isom.emb) countable simple graphs with all isometric graph-embeddings
Part of the motivation for this:
Apart from the personal motivation of giving structure to my n-th attempt to get the manuscript into a satisfying form, this comparison would perhaps also be mildy interesting from a pure categorical point of view, since
Part of my motivation for creating left cancellative categories is our interest in category (isom.emb).
Do you agree that such an article could fit into the nlab?
Incidentally, I know that wide subcategories are a concept to which sometimes a certain four-letter-word is applied. Nevertheless, it seems to me that
^{ 1 } Actually, it seems that we can prove something considerably stronger, namely that this class of graphs is not closed under elementary equivalence. (synonyms: the class is not elementarily closed$=$ the class is not $\Sigma\Delta$-elementary) Moreover, what we are mostly interested in is the non-elementarily-closedness (and hence non-elementarity) of various subclasses of the class of all vertex-reconstructible graphs. (Proving that the latter class is not elementarily closed does not need https://arxiv.org/abs/1606.02926) For example, it seems we can prove that the class of all vertex-reconstructible locally-finite forests is not elementarily closed. For proving that, the methods of https://arxiv.org/abs/1606.02926 appear essential.
Let’s not get formatting issues too much in the way. I suggest you start adding your material in a subsection of an existing entry, and once it has grown enough for us all to have a feeling for its scope, we can still easily split it off into a separate entry.
As Todd already amplified, we are eager to see you add content in your area of expertise. The fine tuning of the formatting is secondary and probably better done by/with the help of experienced regulars here. You should focus on getting the content into place. Anywhere.
This sounds intriguing. A few quick reactions:
I’d say any business about wide subcategories and the four-letter word (I suppose you mean “evil”) is probably nothing to worry about.
I’m curious to what extent we have articles that touch on these different notions of embedding. Are these notions easy to define? Can they be characterized using the language of category theory?
My instinct would be to start slow, possibly with short articles that define the different types of embedding you are interested in and how they relate to other notions in the nLab. Could we talk about this here in the nForum?
One way to avoid “evil” when defining wide subcategories is to work with displayed categories.
Thanks for the answers. Good idea to start by extending an existing entry. Would like to do this with category of simple graphs. Like suggested, will start with a few preliminary discussion here in the forum.
@Todd_Trimble: yes, they are easy to define:
Definition.
weak embedding $\cong$ graph-homomorphism whose vertex-map is injective
strong embedding$\cong$ graph-homomorphism which is a graph-isomorphism onto its image
isometric embedding$\cong$ graph-homomorphism such that the distance between any two vertices in the image of the embedded (w.r.t. the usual graph-metric) comes out equal no matter whether it is measured within the image, or within the ambient graph
Minimal counterexamples.
the map 0->0, 1->1 is a non-strong weak embedding of the graph 0—1 into the graph 0–1–2–0 (three-circuit)
the map 0->0, 1->1, 2->2, 3->3 is a non-isometric strong embedding of the graph H = 0–1–2–3 into the graph G = 0–1–2–3–4–0 (five-circuit)
Explanation of second example: there does not exist an edge between 0 and 3, neither in H nor in G. Thus, the embedding is strong. But the distance between 0 and 3 is three when measured within H, while it drops to two when measured within the ambient graph G. Intuitively, you allow more paths, which may happen to create a shorter path.
Remark. A usual technical term: H is not an isometric subgraph of G. There are many results about embedding graphs isometrically. Notably, every median graph can be isometrically embedded into a sufficiently high-dimensional hypercube.
Remarks.
(strong embedding)$\Rightarrow$(weak embedding)
(isometric embedding)$\Rightarrow$(strong embedding) in category of simple graphs. Caution: this implication is false for multigraphs: the “multi”graph consisting of one edge only isometrically embeds into the multigraph consisting of two parallel edges, but this is not a strong embedding, since when taking the structure induced by the image of that embedding you do not get the single-edge graph, but rather both edges. Focusing on category of simple graphs, this does not concern us further.
each of the classes of maps (weak embeddings), (strong embeddings), (isometric embeddings) are evidently closed under composition.
Currently I am most interested in isometric embeddings, for the reasons described in the opening post.
Weak embeddings are the standard notion when analyzing whether some property implies that an ambient structure must contain some good substructure, now matter how much the ambient structure overachieves by having edges which the desired substructure does not require. A basic example is the fact that a finite graph $G$ is connected if and only if there exists a weak embedding of some tree$T$ into $G$ such that $T$ has the same number of vertices as $G$. Generically, such an embedding is never strong, $G$ usually having much more edges than $T$. An open conjecture in that direction is the Loebl–Komlós–Sós Conjecture which posits that a certain vertex-degree-condition on a graph $G$ implies that there is weak embedding into $G$ from any given tree with $k$ vertices (an approximate solution was published by J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. Stein, E. Szemerédi; cf. e.g. SIAM J. Discrete Math., 31(2), 1072–1148 )
Strong embeddings are the standard notion of embedding in model theory. It is therefore somewhat debatable whether one should emphasize it by using the modifier “strong”, but this seems better, for clarity. This notion of embedding formalises the intuition that an embedding should be something such that when restricting the universe to the image of the embedding, the structure looks precisely like the thing-that-was-embedded.
one could call strong embeddings induced embeddings
strong embeddings are the standard notion in model theory because model theory likes to conceive of substructures by first restricting the universe to a subset, then taking the restriction of a structure to that subset. Intuitively, in model theory one tends to pick out substructures not by a map, but rather by shrinking the universe.
Now to you question of whether and how these notions can be expressed in the language of category theory. It is that all can be expressed, since the language of category theory is sufficiently universal. It is a very interesting question of how they can be expressed or circumscribed. Probably the Cech school of categorical graph theory has published something on this already, but I am not aware of it.
The obvious first question is:
What does a mono in category of simple graphs, precisely as it has been defined there, correspond to?
But before going into this, a few remarks on the article and how to perhaps develop it further.
Imposing the condition of reflexivity to some degree damages the flexibility gained by avoiding the hypothesis of irreflexivity. (Sure, at least a negative condition has been replaced by a positive one.)
Dochtermann opts for using a separate term “reflexive graph” for what is called “graph” in category of simple graphs. (Note: these definitions were not introduced by Dochtermann first, I am referring to his work here for simplicity, not to have to write too much bibliographic things).
Caution: “Hom complexes” in this part of the literature do not consist of hom-sets in the category-theoretic sense. More specifically, Dochtermann’s $\mathrm{Hom}(G,H)$ is not a hom-set. This (among other things, such as the distinction between $\mathrm{Hom}_k$ and $\mathrm{Hom}_{\mathcal{C}}$ in the theory of triangulated categories over a field $k$) is one more reason for writing categorical hom-sets with the $\mathcal{C}(O_0,O_1)$ notation whenevery possible, not by the “semantic” “Hom” notation)
I am curious why it was decide to use the condition of the relation being reflexive. It appears very useful to not make the negative assumption of the relation being irreflexive, but “not making the assumption irreflexive” =!= “making the assumption reflexive” . Especially since “irreflexive” is not the negation of “reflexive”.
The article category of simple graphs should briefly mention why the definition of morphism given is in some sense the “canonical one”. This should perhaps be done via saying things about algebraic theories, their usual notion of morphisms as those maps which preserve all structure, etc. One has this “that-is-the-notion-of-morphism” also in the definition of sketches and in the definition of quivers($=$category theorists’ digraphs). In the latter definition, the “canonicity of definition of morphism” of course comes from
Having opted in category of simple graphs, the description of graphs via relations , the path to the definition of morphism is not as clear. (to be continued; have to interrupt for quite a while now; the monos in SimpGph quite obviously are the weak embeddings)
There are various options in defining the notion of graph. One very common, maybe the most common AFAIK, is that a (simple) graph consists of a vertex set $V$ and a collection of 2-element subsets of $V$ called edges. This notion is mentioned in graph and was the one I was working with in the article, taking the point of view that the data of a simple graph carries no more and no less information than a set with a reflexive symmetric relation $E$. Given a simple graph $G$, we define a relation $E$ by $(x, y) \in E$ iff $x = y$ or $\{x, y\}$ is an edge of $G$. Given a pair $(V, E)$, define a simple graph by declaring $\{x, y\}$ to be an edge iff $x \neq y$ and $(x, y) \in E$.
Now allowing some loops is another option. We’re not calling that one “simple graph”, but of course one can still talk about it. The analogue would be to consider sets equipped with a symmetric relation, as you say. I think the category of such also has some very nice properties, for example I think it’s a topological Grothendieck quasitopos although I’d have to double-check. One also has a connected components functor, but unlike in the simple graph case it won’t preserve products. I personally wouldn’t say that’s any reason for not considering that category.
should briefly mention why the definition of morphism given is in some sense the “canonical one”
If you agree to that canonicity, more words can be added. (There are some words about this in graph minor.) There is an analogy with reflexive quivers, except that reflexive quivers are directed; a closer analogy would be to presheaves on the full subcategory of finite sets with just two objects, a 1-element set and a 2-element set. In fact simple graphs are just the separated presheaves for the $\neg\neg$-topology, as mentioned in the article.
But category of simple graphs is kind of a little pet project in the first place (I believe I’m the only author of it so far); if it’s too distracting, then I can simply port it (and maybe also graph minor) over to my private web and play with it there according to personal whim. (To be clear, I mean I can copy it over – not that I would vandalize the nLab copy!) One thing I’m really not interested in is a long discussion about what is the right notion of graph; I have reasons for being a little bit interested in category of simple graphs as it stands, but I’m not taking any hard lines about it. You could think of the article as it currently stands as playing more of a descriptive role, and also as a kind of exploration still in its baby stages.
At this point I might recommend adding some descriptive information to graph, such as what you said about Dochtermann.
Having opted in category of simple graphs, the description of graphs via relations , the path to the definition of morphism is not as clear.
It’s perfectly clear to a category theorist, since a relation $E \hookrightarrow V \times V$ aka a jointly monic span $V \leftarrow E \rightarrow V$ is just a special diagram. The separated presheaf condition captures what is special (joint monicity). But sure, some more words can be added.
Yes, weak embeddings are simply monos in $SimpGph$. Strong embeddings are what category theorists call regular monomorphisms (in $SimpGph$).
I don’t know off-hand how to describe isometric embeddings in categorical language.
I have now performed some edits at category of simple graphs that takes into account some of the discussion above. Maybe Peter likes this better (actually, this does seem like an improvement, so thanks for the input, Peter!).
Thanks for the answers. Liked the article before and after the edits, just wanted to raise the topic of the reflexivity issue once, to possibly learn something new.
It is not distracting (to me at least), to the contrary, please, keep working on it publicly. Personally I am fine with working precisely the same definitions as in category of simple graphs.
Remarks.
Having opted in category
was a typo, which accidentally almost resulted in an existing, but here, inappropriate, phrase (to opt-in). It was intended to write “Having opted to use, in category of simple graph, the description of graphs via […]
saying things about algebraic theories
was slightly misleading (though I did not claim that the theory of graphs was such a theory), since the usual first-order theory of graphs is not an algebraic theory in the technical sense: it has a relation-symbol, while algebraic theories do not have relation-symbols, rather work with function-symbols.
Would improve section “2. Simple graphs as rerlations” if you deleted “would’ and deleted “i.e., writing $E(x,y)$ to say $(x,y)\in E$” since the would is too conditional and since you told readers about the notation already two lines earlier. This way, the definition of the morphisms becomes easier to find.
Of course, your notion of undirected simple graph is the most usual one (if one takes the view that loop-at-each-vertex is equivalent to no-loop-at-each-vertex). One thought on this: The category of loopless simple undirected graphs (i.e. irreflexive symmetric relations) does not have any terminal object.
From considerations with terminal objects alone,
If graph-homomorphism means that edges are carried to edges, then yes of course. That’s just one of many reasons for a category theorist to prefer working in the category of simple graphs.
I’m not sure what the last bullet is referring to (and don’t have ready access to European Journal of Combinatorics), but okay, I guess that category of graphs lacks a terminal object. :-)
Okay, I fixed the stuff mentioned in the third bullet point of #10. Thanks.
Are you using SVG in your recent edit? There’s an awful lot of gobbledygook when I open the edit page. I would strongly urge not bothering with that and using iTeX instead. If you need some assistance, there are plenty of people who can help.
I may have more comments later, but I’ll wait for you to complete your current thoughts as indicated by the current table of contents for that page.
It would be very nice if the use of svg illustrations, or rather, what comes out at the svg-end of my (not-yet-effiicient-due-to-inexperience-with-the-nlabs-technology) pipeline, would be okay. The interplay of diagrams and graphs is an essential part of the usefulness of category theory. iTeX seems to be inadequate. TikZ is universal.
If I adopt the variant of including large svg illustrations from separate pages, would you then still strongly urge not to use it?
Well, if what you have in mind doesn’t produce huge amounts of stuff in the edit box to navigate around, then it might be okay. Others here should weigh in on the matter as well.
But I draw lots of category theory diagrams using iTeX and rarely encounter problems. If it’s graphs as in graph theory you want to draw, I suppose it could be a different story.
I agree with Todd that one should not clutter pages with SVG code. I would not mind isolating the verbosity of SVG/MathML to a separate page if it displayed correctly; my main issue with it is that it is not implemented properly in Webkit, so does not display correctly in many browsers. As I mentioned somewhere else, I suggest instead to create a vector graphic locally, and upload that to the nLab. If you’re keen to make the source code available, you could put in on github or somewhere.
Thanks for the advice. In particular, did not know about Webkit. Will think about it. Have to interrupt until sometime tomorrow now. In particular, will not have time to migrate the svg code to a separate page today. Will try to do so tomorrow, should it not have happened until then.
Re 12 and the question
I’m not sure what the last bullet is referring to which asks about #11 is answered over at this thread, which seems the more systematic place.
To link to a different thread, try this: this thread. See the source for the syntax. Your link was a link to create a new nLab article.
Thanks. Tried.
1 to 21 of 21