Timeline for A weaker concept of graph homomorphism
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 5, 2017 at 18:15 | comment | added | silvascientist | @Jérôme JEAN-CHARLES No, those three graphs are not homeomorphic. $P_3$ and $P_4$ are homeomorphic, but they are not homeomorphic to $C_4$. But you are correct to point out that there is in fact a graph hom from $C_4$ to $C_3$, contrary to what OP claims. What can be said is that there is no hom $C_4 \to C_3$ that could make the diagram above commute, which would be "solved" by weak homomorphisms. | |
| Mar 3, 2015 at 1:03 | comment | added | Jérôme JEAN-CHARLES | ATTENTION: Your nice drawing is misleading: you forgot four arrows. In fact apart from $C_3$ the three others are homeomorphic and each have an Hom towards $C_3$. | |
| Nov 12, 2012 at 20:30 | comment | added | Hans-Peter Stricker | [@Mariano] I tried to explain and motivate my question, sorry for not having succeeded. My main points are: (i) As topological spaces $C_3$ and $C_4$ are isomorphic, and that is what I mean with "obvious/undeniable structural relatedness". (ii) I don't want there to be a morphism but only realized how little the step is to allow one. I feel the need for a reason not to take this step, but that is admittedly subjective. | |
| Nov 12, 2012 at 17:21 | answer | added | Andrej Bauer | timeline score: 6 | |
| Nov 12, 2012 at 16:30 | answer | added | Benjamin Steinberg | timeline score: 8 | |
| Nov 12, 2012 at 16:12 | comment | added | Mariano Suárez-Álvarez | My point is that one does not usually come up with a more or less random definition and then ask people around what it is good for and why others use another. You say that something is obvious and that something else is undeniable: but why do you want there to be a morphism between the graphs where there isn't? That someone somewhere has preferred the well-known definition of morphism is worth-knowing, but a motivation for your question would not be bad, either! | |
| Nov 12, 2012 at 9:40 | comment | added | Olivier | The usual definition also has attractive features from the point of view of algebraic graph theory: existence and uniqueness of cores,cores of vertex-transitive graphs are vertex-transitive of cardinal dividing the the cardinal of the graph etc... If you allow contraction of edges, this seems to disappear. | |
| Nov 12, 2012 at 8:17 | comment | added | Hans-Peter Stricker | [@Mariano] I'd like to know in which contexts and for what specific reasons the stronger notion of graph homomorphism is more useful - and thus successful - than the weaker. Patricia in her comment gave such a perfect reason. | |
| Nov 12, 2012 at 7:18 | history | edited | Hans-Peter Stricker | CC BY-SA 3.0 |
added 75 characters in body
|
| Nov 12, 2012 at 5:14 | comment | added | Mariano Suárez-Álvarez | Might be conceptually more appropriate for what, drawbacks when trying to do what ? Definitions do not exit in the vacuum; they are worth their usefulness in gold. What are you trying to achieve? | |
| Nov 12, 2012 at 0:41 | comment | added | Hans-Peter Stricker | [@Brendan] I guess it is true. And I hoped to make this clear: one of both is necessary - adding loops or weakening the definition. You confirm: both approaches are equivalent. Anyway: The (standard) category of (simple) graphs with (standard) homomorphisms reflects neither of them. But why seems none of them to be missed? | |
| Nov 11, 2012 at 23:32 | comment | added | Brendan McKay | Isn't it true that anything you can do with weak homomorphisms could be done by first adding loops everywhere then using usual homomorphisms? If so, I don't see what is gained. (Btw, topological graph theorists allow loops sometimes; even maps with a single vertex and lots of loops are interesting.) | |
| Nov 11, 2012 at 22:48 | history | edited | Hans-Peter Stricker | CC BY-SA 3.0 |
added 54 characters in body
|
| Nov 11, 2012 at 22:48 | comment | added | Patricia Hersh | I would guess that one reason for the emphasis on the existing definition is that it is convenient for graph coloring problems, since a coloring of $G$ with $r$ colors is a graph homomorphism from $G$ to $K_r$. But I've only been watching this area from afar, e.g. the development of topological lower bounds on chromatic numbers. | |
| Nov 11, 2012 at 22:38 | history | asked | Hans-Peter Stricker | CC BY-SA 3.0 |