Room for Jim and Thomas Klimpel

« first day (29 days earlier) ← previous day next day → last day (323 days later) »

9:06 AM

@Jim No need to apologize for the "inconvenience", I'm glad to see that you corrected some of the handwaving. This helps me to see that you clearly know what you want to say, but only have problems writing it down properly.

(But please don't take those problems too lightly. I know somebody who has also started to rely on his audience to guess what he really wanted to say. He just got a paper rejected, and I didn't knew whether I should love or cry while reading the reviewers comments, just because for how wrong they guessed, and how incomplete the written down statements actually were.)

On the other hand, your updated description of how to combine the results from the subproblems indicate to me, that you really don't fully understand why it is more complicated than that. Especially, you are unable to see where group theory would enter into the process.

The fact that you now try to solve the bipartite graph isomorphism problem means that you got at least the problem where the subgroups are the full symmetric group. What you still don't get is that essentially any permutation group could occur as the subgroups from the two subproblems, and that hence you would have to solve a problem similar (...) to the string isomorphism problem (from Babai's recent breakthrough) while putting subresults together.

For example, you write "(ii) Each row is unique (No row is repeated in a set of rows /matrix)", because you have a certain reduction in mind. This reduction even works in a certain sense, but you do get a nontrivial subgroup from that reduction, and that group is not the full symmetric group. So it is more a reduction of the automorphism group than the combinatorial reduction of the graph isomorphism problem you hope for.

Jim

10:14 AM

“that you really don't fully understand why it is more complicated than that.” -Yes, this could be the case. If this is the case, I would like to have some help to understand how it fails. lets consider the answer, http://math.stackexchange.com/questions/1592854/isomorphism-of-non-symmetric-matrices/1598868#1598868
Consider the 1st iteration only. My claim is that, if $L_i$ is unchanged(arrangement of columns and rows), and everything else is changed, then every block matrix/ sub matrix can be rearranged exactly like $E_{1,i}$. Is this clam correct or incorrect?

Jim

10:57 AM

+ in polynomial time

3 hours later…

Thomas Klimpel

1:55 PM

@Jim Your problem is not whether individual claims are correct or incorrect, but how the different case distinction during the division phase influence what happens during the combine phase. You "feel" more or less that it should be possible to handle each of those special cases, but you don't understand yet, what it really means to handle them during the combine phase.

The easiest way for you to see what the different cases really imply might be to have a look at case 1. and 2. for Theorem (Babai 15) at jeremykun.com/2015/11/12/…

If you have duplicate rows, then you are essentially in case 2. It is a great "size" reduction in a certain sense, hence you get the feeling that you don't need to worry about that case, but you don't really understand what it implies for the combine phase. You should try to get an understanding for how group theory enters the picture during the combine phase.

Thomas Klimpel

2:13 PM

But maybe it would be easier to you, if you look at your original algorithm for general undirected graphs, and try to identify all the places where you didn't realize that you have to solve a bipartite graph isomorphism problem during the combine phase. Then you might get a better feeling for the other situations, where you didn't realize which actual complications will arise during the combine phase.

Jim

@ThomasKlimpel , for example(one possible question could be), are u saying that a local automorphism might not be compatible with global permutation ?

Jim

2:38 PM

@ThomasKlimpel I am really missing the point! :) , i mean , that is a different POV(case 1. and 2. for Theorem (Babai 15)), Please note that , if property (i),(ii) (in my solution)is absent in a matrix, we can divide(not the set definition of partition ) the global matrix based on this local information in the local matrix. and in all of them (and to all branch) ,if it is needed, I intend to use the same algorithm .

Anyway, probably I am making a mistake, in this case, if you have time, would you please construct an example(counterexample), that would help me lot.

Thomas Klimpel

3:33 PM

@Jim It's not really a different POV. You select a vertex (I'm talking about you original algorithm for general graphs here), and hope the you get a canonical coloring. Then you observe that one way why this could fail are identical rows, but that this case allows another reduction. But this reduction is a canonical equipartition, and you should try to understand the difference for your algorithm of a canonical coloring versus a canonical equipartition.

So you should try to think about your algorithm in terms of colorings. When you select a vertex, just give it a unique color. Then try to refine (use degree information) the colors of the other vertices based on this color. And then try to understand what an equipartition means in this context.

1 hour later…

Jim

4:50 PM

@ThomasKlimpel , I will reconsider, and try to realize the gap. anyway, it would be helpful if can give an example.

« first day (29 days earlier) ← previous day next day → last day (323 days later) »

all rooms