Not signed in (Sign In)

Not signed in

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

  • Sign in using OpenID

Discussion Tag Cloud

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

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).

nLab > nLab General Discussions: category of simple graphs with embeddings (proposed)

Bottom of Page

1 to 21 of 21

  1.  
    • CommentRowNumber1.
    • CommentAuthorPeter Heinig
    • CommentTimeJun 12th 2017
    • (edited Jun 15th 2017)

    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

    (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:

      • with colleagues I am working on a proof that the class of all reconstructible undirected simple graphs is not an elementary class 1 , which was not known before , sheds some light on why the topic of graph reconstruction is hard, and (to all appearances) could not be proved before the methods provided by our paper https://arxiv.org/abs/1606.02926
      • the proof seems essentially done, but the manuscript is far from finished and we are not satisfied with it,
      • in our proof there is one clear reason for focusing on, and working as much as possible in, the otherwise perhaps rather special category (isom.emb): we use Gaifman normal forms of first-order formulas, and, roughly speaking, to respect Gaifman normal forms, strong embeddings are not enough, one needs isometric embeddings.

    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

      • the article would compare three left cancellative categories which combinatorially are all different while it is not clear at the moment how different they are in terms of usual categorical notions of alikeness
      • while all of (weak.emb), (strong.emb) and (isom.emb) are left cancellative, none is a groupoid or a preorder

    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

      • there can be no **** wide subcategories, only definitions _of wide subcategories can be ****,
      • there are many examples of non-**** definitions of wide subcategories also within category theory,
      • in a sense, any definition of a wide subcategory can be made non-**** by just working from the bottom up, by going about defining the objects once again and then giving a reasonable definition of the morphisms one is interested in, essentially, by just avoiding the word “wide subcategory” when defining the category.

    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.

    • CommentRowNumber2.
    • CommentAuthorUrs
    • CommentTimeJun 12th 2017
    • (edited Jun 12th 2017)

    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.

    • CommentRowNumber3.
    • CommentAuthorTodd_Trimble
    • CommentTimeJun 12th 2017

    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?

    • CommentRowNumber4.
    • CommentAuthorMike Shulman
    • CommentTimeJun 13th 2017

    One way to avoid “evil” when defining wide subcategories is to work with displayed categories.

    • CommentRowNumber5.
    • CommentAuthorPeter Heinig
    • CommentTimeJun 13th 2017
    • (edited Jun 13th 2017)

    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 GG is connected if and only if there exists a weak embedding of some treeTT into GG such that TT has the same number of vertices as GG. Generically, such an embedding is never strong, GG usually having much more edges than TT. 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 GG implies that there is weak embedding into GG from any given tree with kk 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.

    • Currently, the definition of the morphisms of SimpGph is buried within the section “Simple graphs as relations”. The morphisms should get a separate section. (to be continued. have more to say on this, but would rather first like to contextualize the three notions of embeddings a little more)
    • It would improve the article not to disparage the sensible principle of avoiding the the negative condition of irreflexivity as a “maneuver”.
    • The definition in the current version of category of simple graphs (i.e. no directions, no multiple edges, but loops are allowed) is not unusual and not unheard of in the graph-theoretical literature, especially in the important sub-genre of what is called “Hom complexes of graphs” (Example: A. Dochtermann, Hom complexes and homotopy theory in the category of graphs, European Journal of Combinatorics 30 (2009) 490-509; probably no need to look that up now, especially since the meaning of “category of graphs” article does not (yet) precisely agree with the meaning of [category of simple graphs]]
    • CommentRowNumber6.
    • CommentAuthorPeter Heinig
    • CommentTimeJun 13th 2017
    • (edited Jun 13th 2017)
    • Why does category of simple graphs not agree with Dochtermann’s definition? Because Dochtermann allows loops but does not require every vertex to have one. Briefly:
      • (graph in the sense of Dochtermann)≅\cong(symmetric relation)

    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 Hom(G,H)\mathrm{Hom}(G,H) is not a hom-set. This (among other things, such as the distinction between Hom k\mathrm{Hom}_k and Hom 𝒞\mathrm{Hom}_{\mathcal{C}} in the theory of triangulated categories over a field kk) is one more reason for writing categorical hom-sets with the 𝒞(O 0,O 1)\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

      • the usual definition of functor category,
      • the fact that a quiver is a presheaf on the walking quiver,
      • the fact that there is no discussion about what are the morphisms in the walking quiver.

    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)

    • CommentRowNumber7.
    • CommentAuthorTodd_Trimble
    • CommentTimeJun 13th 2017
    • (edited Jun 13th 2017)

    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 VV and a collection of 2-element subsets of VV 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 EE. Given a simple graph GG, we define a relation EE by (x,y)∈E(x, y) \in E iff x=yx = y or {x,y}\{x, y\} is an edge of GG. Given a pair (V,E)(V, E), define a simple graph by declaring {x,y}\{x, y\} to be an edge iff x≠yx \neq y and (x,y)∈E(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↪V×VE \hookrightarrow V \times V aka a jointly monic span V←E→VV \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.

    • CommentRowNumber8.
    • CommentAuthorTodd_Trimble
    • CommentTimeJun 13th 2017
    • (edited Jun 13th 2017)

    Yes, weak embeddings are simply monos in SimpGphSimpGph. Strong embeddings are what category theorists call regular monomorphisms (in SimpGphSimpGph).

    I don’t know off-hand how to describe isometric embeddings in categorical language.

    • CommentRowNumber9.
    • CommentAuthorTodd_Trimble
    • CommentTimeJun 13th 2017
    • (edited Jun 13th 2017)

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

    • CommentRowNumber10.
    • CommentAuthorPeter Heinig
    • CommentTimeJun 13th 2017
    • (edited Jul 4th 2017)

    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.

    • The phrase

    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 […]

    • My phrase

    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)E(x,y) to say (x,y)∈E(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.

    • CommentRowNumber11.
    • CommentAuthorPeter Heinig
    • CommentTimeJun 13th 2017
    • (edited Jul 4th 2017)

    From considerations with terminal objects alone,

      • category of simple graphs is not equivalent (in the standard categorical sense) to the category of loopless undirected simple graphs with graph-homomorphisms,
      • category of simple graphs is not equivalent (in the standard categorical sense) to the category of graphs in the sense of Hom complexes and homotopy theory in the category of graphs, European Journal of Combinatorics 30 (2009) 490-509
    • CommentRowNumber12.
    • CommentAuthorTodd_Trimble
    • CommentTimeJun 13th 2017

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

    • CommentRowNumber13.
    • CommentAuthorTodd_Trimble
    • CommentTimeJun 13th 2017

    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.

    • CommentRowNumber14.
    • CommentAuthorPeter Heinig
    • CommentTimeJun 13th 2017

    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?

    • CommentRowNumber15.
    • CommentAuthorTodd_Trimble
    • CommentTimeJun 13th 2017

    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.

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

    • CommentRowNumber17.
    • CommentAuthorPeter Heinig
    • CommentTimeJun 13th 2017

    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.

    • CommentRowNumber18.
    • CommentAuthorPeter Heinig
    • CommentTimeJun 14th 2017
    • (edited Jun 14th 2017)
    [moved to more relevant thread]
    • CommentRowNumber19.
    • CommentAuthorPeter Heinig
    • CommentTimeJun 16th 2017
    • (edited Jun 16th 2017)

    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.

    • CommentRowNumber20.
    • CommentAuthorTodd_Trimble
    • CommentTimeJun 16th 2017

    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.

    • CommentRowNumber21.
    • CommentAuthorPeter Heinig
    • CommentTimeJun 16th 2017

    Thanks. Tried.

1 to 21 of 21

  1.