Timeline for Non-isomorphic graphs with isomorphic edge vectors
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 8, 2016 at 22:38 | vote | accept | Nik Weaver | ||
| Mar 8, 2016 at 21:55 | answer | added | Fedor Petrov | timeline score: 2 | |
| Mar 8, 2016 at 18:40 | comment | added | Nik Weaver | @GerhardPaseman: I think it's okay. A set of edge vectors is a cycle if for some choice of orientations they sum to 0, and this is not true of any proper subset. That property will be maintained under linear isomorphisms. | |
| Mar 8, 2016 at 18:36 | comment | added | Gerhard Paseman | It may be clear to you, but I do not find it so direct. Many "simple algorithms" for GI fail because e.g. they do not distinguish between a cycle of length 2k and two cycles of length k. I am being cautious in my comment above. Gerhard "'Simple Algorithms' Mean Something Else" Paseman, 2016.03.08. | |
| Mar 8, 2016 at 17:19 | comment | added | Fedor Petrov | @Gerhard Of course, cycles correspond to cycles, since being a cycle is equivalent to being linearly dependent. | |
| Mar 8, 2016 at 17:02 | comment | added | Gerhard Paseman | It seems such a linear map induces a bijection on cycles of the two graphs (but I have no proof). Running with this premise, I see two possibilities: Try two non-isomorphic regular graphs and augment each with a central vertex and see what you get for a counterexample; assume no cex exists for question two, focus on polytime algorithms to finding a linear isomorphism, and use this to one-up Babai with a polytime solution for the hard part of GI. Gerhard "In A Friendly, Way, Naturally" Paseman, 2016.03.08. | |
| Mar 8, 2016 at 16:40 | comment | added | Fedor Petrov | (cont.) Note that if $H$ and $K$ both have central vertices, they are isomorphic by obvious reasons. But the problem is that intermediate graph may have not central vertices, while first and final graphs somehow have it. | |
| Mar 8, 2016 at 16:39 | comment | added | Fedor Petrov | To be more specific. Assume that we have two graphs $G_1$, $G_2$ on disjoint sets $V_1,V_2$, vertices $v_1,u_1\in V_1$; $v_2,u_2\in V_2$. We may glue $v_1$ with $v_2$ and $u_1$ with $u_2$, so take graph $H$, and we may instead glue $v_1$ with $u_2$ and $u_1$ with $v_2$, so take graph $K$. Cycle matroids of $H$ and $K$ are isomorphic. Whitney's theorem that if two graphs are isomorphic, then they may be obtained one from another by a sequence of such twists. | |
| Mar 8, 2016 at 16:32 | comment | added | Fedor Petrov | Hm, is it possible? Whitney 2-isomorphism theorem (see e.g. www-ma2.upc.edu/demier/tesidina4.pdf ) provides all possible examples of graphs with isomorphic cyclic matroids (this is a priori even bit weaker that what you are asking for), but it rarely produces central vertices. | |
| Mar 8, 2016 at 16:10 | history | edited | Nik Weaver | CC BY-SA 3.0 |
edited title
|
| Mar 8, 2016 at 16:04 | history | asked | Nik Weaver | CC BY-SA 3.0 |