@ThomasKlimpel If I want to submit my draft to a journal, what do I need to do(consider my present condition)?

Present Condition- drive.google.com/open?id=0Bz9ECAgDBnbvNU5wS1VTWTZoTEE

@Jim Don't submit it to a journal. Laszlo Babai has already published a quasi-polynomial time algorithm for graph isomorphism. Even if you would manage to finish you algorithm in some reasonable sense, you would no longer have a key message. Before, you might have claimed that your approach is a promising strategy, which could eventually yield a quasi-polynominal time algorithm. And your basic strategy is not that different from that algorithm (it's commonly called individualization).

If you want to publish something, you should at least have a key message and a target audience. And you should be aware that even if you don't have a key message, your writing will send some key messages to its readers. For the current condition of your draft, I got the following messages: (1) You have some ideas, which are more or less clear in your mind. (2) You are willing to put in quite some effort to communicate those ideas to people who are willing to communicate with you.

@ThomasKlimpel "And your basic strategy is not that different from that algorithm (it's commonly called individualization)." - I think there is a misunderstanding.

For example, I don't claim to solve string Isomorphism (babai does), if I am not wrong , GI<SI.

(3) You still have room for improvement in your ability to communicate math in English, but you are already able to communicate in a sufficiently interactive context. (A journal submission is definitively not a "sufficiently interactive context", so I would advice against that at the current moment.)

@ThomasKlimpel I am familiar with basic individualization, and I have also used that , but that is not my core argument / strategy .

Mr. klimpel, I think , there is a chance , that you, might have misunderstood my solution.

@Jim Babai uses individualization as part his algorithm, and he uses it in a way that it is unlikely to ever yield a polynomial time algorithm. This is quite similar to how your algorithm uses individualization.

Either i am wrong or u misunderstood.

it is not explicitly "group theory", it reuces the size for smaller group.

Are you sure you got my solution( with due respect)?

I am saying that, following a certain divide and conquer technique, the algorithm reduces the maximum possible permutation.

" you would no longer have a key message."- mine is faster than babai, provided that it works! :)

@Jim Yes, I'm quite sure. Let me explain why: All the most obvious issues and questions I had with respect to the combine phase of your algorithm were addressed by the global strategy outlined by Babai, and the string isomorphism problem played a crucial role there. It was also much easier for me to follow Babai, because I had already thought about the exactly same issues in the context of your algorithm.

@ThomasKlimpel suggest me to read something so that I can realize. BTW , is it wrong that GI is a special case of String Isomorphism?

thus, solving GI does not yield SI, but solving SI solves GI?

You mentioned about SI (Strin ISo) earlier , that is why I started to doubt, I dont claim to solve SI in quasi time.

@Jim But nauty and Traces are still faster than your algorithm, and they do work in practice. So the crucial part of the work of Babai is to prove that his algorithm only takes quasi-polynomial time.

babai does both SI and GI , and that is an indication how different babai and I could be.

@ThomasKlimpel nauty, traces use 1 dim WL and other heuristic, and their worse case is exponential.

@ThomasKlimpel "I had with respect to the combine phase of your algorithm were addressed by the global strategy outlined by Babai, and the string isomorphism problem played a crucial role there."--- String permutation has nothing to do with mine, it is a more complicated structure, graph has some "convenient information " which is absent in String.

@Jim Indeed, they do use 1 dim WL, and this has quite some serious consequences. Can we stop the discussion about your algorithm for a minute, and discuss 1 dim WL, 2 dim WL and the Cai-Furrer-Immerman theorem? I do know the Cai-Furrer-Immerman construction from the thesis of Pascal Schweitzer, but I don't really know the corresponding theorem. Can you quickly summarize the conclusion of that theorem for me?

Like Group iso needs only Bijection, where GI needs a structural Bijection, which make GI harder than Group Iso.

@ThomasKlimpel yes we can :) . Cai-Furrer-Immerman said that using individualization technique outlined by WL method can not distinct 2 graphs in polynomial time, martin furrer actually constructed a graph as a counterexample. And it takes w(n) values to distinct GI(w=omega), which ensures that WL method can do GI in exponential time.

1992 paper, let me get it for you

google.com/…

that result also conclude/imply that purely combinatorial GI algo(in poly time) is not possible.

@Jim Cool, thanks. Let me browse it a bit...

ok

youtu.be/yMjJozJ6RsI

@ThomasKlimpel i have seen both 1,2 . Do you want me see any specific part?

@Jim I will continue browsing a bit, but I already see that this Cai-Furrer-Immerman theorem was not the reason, why I said "Babai uses individualization ... unlikely to ever yield a polynomial time algorithm. ...". I was rather thinking of what Babai says in the very last minute of the second video: "... because the methods are really geared towards quasi-polynomiality..."

ok

the problem is , I would like learn LUKS framework before I listen/ read BABai rigorously.

Anyway, individualization is little tool , it is required nonetheless. but it has limitation. So, something else need to be thought of.

@ThomasKlimpel , would you suggest me to read some literature so that I can realize what you are saying?

Think about why I asked this question (after studying your algorithm). Why does the answers mean that you might be forced to to the combine phase in the presence of arbitrary permutation groups? The main difference to the string isomorphism problem here is how you measure the size of the permutation group. Here, it' size is measured in terms of a graph which produces it as automorphism group. For the string isomorphism problem, it's size is just (something much smaller...)

One reduction I worked out quite early after watching Babai was to reduce graph isomorphism in the presence of string isomorphism to the string isomorphism problem over a binary alphabet. This helped me understand, why solving the string isomorphism problem is important for this type of approach towards the graph isomorphism problem.

@ThomasKlimpel certainly , string permutation problem is important as solution to this problem can be used in other areas. SI>GI> group Iso. I am aware of that . Also , I realized , SI is heavily depended on group th . Thats fine with me . But I am not claiming anything about SI !. are saying it is not possible to bypass SI for a GI solution? SI is essential for GI?

Luks , Babai used a framework which is linked with SI, but do you aware of any result that says It is impossible to solve GI without SI? Like CFI says it is impossible to solve GI in poly time using WL .

I am quite keen to learn Luks framework , but at the moment I need to know why my solution does not work. So,when u consider my solution, please don't bring SI, it will yield nothing. It has no relation, unless you show me one.

@Jim I say that SI (or rather generalized graph isomorphism where the symmetric group is replaced by a rather arbitrary permutation group) is a convenient framework for graph isomorphism, because such arbitrary permutation groups occur during the combine phase anyway. But their size is measured differently, hence GI is probably easier than SI.

of course it is a strong tool (not sure about "convenient" :) )

but I cant use that in my approach now!

:)

There might be a problem regrading automorphism of local graph, but that does not seem to be your concern.

If you ask me whether SI is essential for GI, I would say no. My reasoning is that nauty and Traces are quite successful without SI, and even without 2 dim WL. Especially Traces seems to use randomization so successful that it can practically handle any graph. This is interesting, because 2 dim WL seems to be required to be stronger than "spectral methods". At least the proof the WL is stronger than "spectral methods" refers to 2 dim WL.

@Jim My concern is the combine phase of your algorithm. As long as you don't understand why the automorphism groups of the subgraphs play a crucial role, I can't believe that your algorithm is really complete.

@ThomasKlimpel just tell me a situation in a concrete manner or give me statement to prove or give an example , otherwise none of us is sure! are sure that I am wrong?

it is ok to doubt, but if u don't give a concrete situation, i can not move further

@Jim You algorithm is either incorrect or incomplete. For example, your original algorithm (the version from August 20, 2015 you linked above will do) doesn't consider that case of solving bipartite graph isomorphism problem during combine phase. It's easy to give an example where your algorithm get forced to do so. Would such an example be good enough for you?

@ThomasKlimpel Give a graph that abide by the condition given in this document drive.google.com/open?id=0Bz9ECAgDBnbvNU5wS1VTWTZoTEE

this can not be drive.google.com/open?id=0Bz9ECAgDBnbvNk1BQS1qNlV4U2s

@ThomasKlimpel For the time being, keep "But how can you claim that isomorphism testing for those graphs would be trivial" aside , see whether "So you already try to exclude the case where the bipartite graph would occur most naturally" is true or false for all cases under the given condition. We should construct a common ground, then you can bring cases where you can refute.