Timeline for Non-isomorphic graphs with bijective graph homomorphisms in both directions between them
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 30, 2020 at 23:06 | answer | added | Florian Lehner | timeline score: 3 | |
| Sep 4, 2017 at 15:00 | vote | accept | Dominic van der Zypen | ||
| S Sep 4, 2017 at 14:59 | history | suggested | Peter Heinig | CC BY-SA 3.0 |
Added clarification, following a comment.
|
| Sep 4, 2017 at 14:43 | review | Suggested edits | |||
| S Sep 4, 2017 at 14:59 | |||||
| Sep 4, 2017 at 14:42 | comment | added | Peter Heinig | @HenrikRüping: this is correct, of course. I think the OP took it to go without saying that 'simple' forbids this. But you are right in that one should make it absolutely unambiguous that 'graph' in the sense of model theory, i.e. 'irreflexive symmetric binary relation on a set' is meant. I will edit accordingly. | |
| Sep 4, 2017 at 14:39 | comment | added | HenrikRüping | Maybe it is worth clarifying which definition of graph you are using. If you allow multiple edges between two vertices, then you can find vertex bijections from the graph given by two points joined by one edge to the graph given by two points connected by two edges. | |
| Sep 4, 2017 at 14:35 | comment | added | Peter Heinig | Even assuming the full Aharoni--Berger-theorem, this is not clear (to me): the evident attempt via Cantor-Bernstein-Schröder Theorem does not work, because 'mapping back-and-forth' need not take you back to the prescribed pair of vertices. Not to speak of doing it without Aharoni--Berger. | |
| Sep 4, 2017 at 14:35 | comment | added | Peter Heinig | There is an (I think) interesting subproblem: under the hypotheses of OP, give as easy and clear proof as possible, perhaps with some reverse-mathematical analysis, that $\kappa(G)=\kappa(H)$, where $\kappa(\cdot)$ is the class-function on the class of all irreflexive symmetric binary relations which returns the vertex-connectivity of its argument. | |
| Sep 4, 2017 at 14:34 | answer | added | Jeremy Rickard | timeline score: 24 | |
| Sep 4, 2017 at 14:19 | comment | added | Nate Eldredge | @DirkLiebhold: To be explicit, let $G_1$ have two vertices $a,b$ and no edges; and let $G_2$ have the same two vertices $a,b$ with an edge between $a$ and $b$. Then the identity map from $G_1$ to $G_2$ is a bijective homomorphism but not an isomorphism. | |
| Sep 4, 2017 at 12:34 | answer | added | Peter Heinig | timeline score: 7 | |
| S Sep 4, 2017 at 12:26 | history | suggested | Peter Heinig | CC BY-SA 3.0 |
I clarified the question, giving it the only interpretation I can think of which does not make it vacuous.
|
| Sep 4, 2017 at 12:10 | review | Suggested edits | |||
| S Sep 4, 2017 at 12:26 | |||||
| Sep 4, 2017 at 10:52 | history | edited | Dominic van der Zypen | CC BY-SA 3.0 |
added 90 characters in body
|
| Sep 4, 2017 at 10:50 | comment | added | Dominic van der Zypen | @TobiasFritz Thanks for your comment, I could add "infinite" to the question | |
| Sep 4, 2017 at 10:49 | comment | added | Dominic van der Zypen | @DirkLiebhold No, compare to the situation in topology, where the existence of bijective continuous functions in either direction between spaces does not imply homeomorphy: mathoverflow.net/questions/30661/… | |
| Sep 4, 2017 at 10:36 | comment | added | Tobias Fritz | Not if $G$ and $H$ are finite. In order to show that $f_1$ is an isomorphism, it is enough to show that $H$ does not have more edges than $G$. But this follows from the bijectivity of $f_2$. | |
| Sep 4, 2017 at 10:00 | comment | added | Dirk | Isn't the existence of a bijective homomorphism exactly the definition of an isomorphism (not only for graphs but everywhere)? Could you maybe tell why you think that this might not be the case for graphs? Also important: Are your graphs allowed to be infinite, or are you only considering finite graphs? | |
| Sep 4, 2017 at 9:36 | history | asked | Dominic van der Zypen | CC BY-SA 3.0 |