Room for Jim and vzn

1:35 AM

@Jim ok viewer works on other computer. but academia.edu seems to require a signup to download the pdf. & ipad wont let me hilight in the viewer. argh. the pdfsr link works ok.

now, was not expecting a lot different. this might be a bit tedious/ painful but trust me, necessary to progress.

if you want to be a scientist, the excuse that english is not your native language is not gonna cut it. also, its not an excuse for unclear/ imprecise writing. which is the same in any language.

> Graph Isomorphism of strongly regular graph is a hard problem due to coloring difficulty, individual refinement does not work in polynomial time.

this 1st sentence is a mishmash of ideas just as the overall concept is. (microcosm reflecting the macrocosm.)

GI is hard because... [x]. what is [x]? coloring a regular graph is a different problem than GI. it might be related to solving GI via some construction/ ref, but you havent explained that at all.

you havent defined "individual refinement" either.

so the paper basically "falls" at sentence 1.

so, try again!

but, some extra point. srg(...) is not defined in your paper. simply writing srg(...) is not a definition. srg(...) maybe defined in other papers. you can copy the defn from there. etc

"dividing" a matrix into "submatrices" may be a real/ legitimate operation but again you havent defined it. you seem almost not to define anything. set up your definitions and then proceed from there.

Jim

5:18 AM

@vzn 1. that was the 'introduction' paragraph. It has no relation to the main idea. I gave some introductory line as I could not jump on to my idea. You can skip that paragraph. Do you still want me to rewrite(at the moment), let me know? 2. Do I write my explanation here on SE or make another pdf?

@vzn i would like to start from here.

@vzn also from here.

You are asking to explain the parameters of srg= Strongly Regular Graph written in between brackets, the idea is true for any parameters of srg(at the moment) so I did not gave any specific parameters.

Jim

5:48 AM

"dividing" a matrix into "submatrices" : A symmetric matrix of a given graph can be divided into 4 parts=submatrices using the adjacency of any given vertex of that graph. pick any vertex x of graph G, vertices of G either adjacent to vertex x or not.

if you keep all vertices adjacent to x together, say, first 5 vertices= column/ row are adjacent to x, these 5 vertices= column/ row creates a symmetric matrix as 5 vertices create a sub graph of G. same thing happens to all non adjacent vertices. In the post on SE , matrices C,D was obtained based on the last vertex=10th vertex. remaining 2 matrices are non-square and one is transposed of another (in the post E and transpose of E) .

vzn

2:54 PM

@Jim every sentence counts. every sentence has a relation to the main idea. the introductory line is not clearly introducing anything. nothing can be skipped. everything must hold together.

@Jim rewrite it

& take a look at this page & see what you think of any of those papers/ "proofs"

did you notice 1 is related to graph isomorphism? and there are probably dozens more on arxiv (not on that page)

@Jim you dont understand, srg(...) means nothing until you define what it means. merely writing it out means nothing.

Jim

3:30 PM

@vzn I know the incident of Ted Swart . Did not know that Yannakakis's work is related to GI.

@vzn So , I should give definition of strongly regular graph before I mention it, in general , before I use any existing term, I should mention it, is that what you mean?

@vzn, by this time , you have read the whole doc(it consists 2 page only :) ), did you get the idea, at least, informally ? It might have some unclear paragraph , but it must tell you something about the idea , what is thought on that?

@vzn huge , will take some time!! starting now.

vzn

4:25 PM

@Jim have the general idea from your original post with my answer. thought from day 1 (along with audience upvoting your question) your general direction has value & is in line with other methods.

@Jim if you are using/ analyzing [x] in the paper then define [x]. if you are not using [x] then dont complicate the paper with reference to [x].

advanced GI algorithms tend to operate on/ "deconstruct" properties of the adjacency matrix.

hence GI =? P possibly reduces to some basic question about the nature of adjacency matrices, presumably of regular graphs (as in your approach).

@Jim "huge"? lol... think of how much has been written on GI over decades, maybe even centuries... the problem nearly (naturally) dates to the inception/ invention of graphs by Euler...

Jim

@vzn this is clearly inexperience , i thought , everybody knows about SRG. You can also consider that it is just a overview . But, lesson is learned.

vzn

@Jim know about RGs but what is the difference between SRGs and RGs? not an expert. it only takes a few sentences to define stuff & you can copy defns from other papers if you want/ need to.

Jim

@vzn euler ?? no idea!! =D , yes , you will find out how much I know.

vzn

ps:

writing clearly ←→ thinking clearly

Jim

4:40 PM

@vzn yes , agree, lesson learnt.

vzn

also:

rome wasnt built in a day ;)

← learning too! relying on you to teach me! :)

Jim

@vzn hmm, realizing at the moment... yap, rome...

@vzn considering feedback I got, you should run if anyone like me come to teach you!!! =D =D

Jim

4:53 PM

@vzn "your general direction has value & is in line with other methods." would you please elaborate "is in line with other methods." please?

vzn

5:09 PM

@Jim have already learned some. "learning happens!"

@Jim as in my answer to your posted question

Jim

5:36 PM

@vzn mathoverflow.net/questions/96858/… , by another pioneer , Mckay, is not related or anyway in my direction(if I understood the post correctly). your another ref: needs time!!

vzn

6:49 PM

@Jim saw that while searching for refs related to your posted question. some rough similarities to your approach.

Jim

@vzn I think i can assure you its not :) !!

Jim

7:34 PM

@vzn both Introduction and SRG was not necessary in that doc.

Ok study time :) , i ll keep checking this chat room , keep messaging!! , bye.

vzn

8:08 PM

@Jim afaict "cells" are the "separate partitions" of the vertices.

Jim

@vzn "a partition is equitable if for any two vertices v,w in the same cell, and any cell C, it holds that v,w have the same number of neighbours in C. " one difference is that "the same number of neighbours", to me , afaic, different approach with "slightest similarity" .

vzn

8:31 PM

@Jim hes looking/ working on GI, vertex partitions, regular graphs. notice also there is no direct answer to his question, only a 1v "extended comment". on MathOverflow no less.

afaik its widely believed GI is harder than P. a proof would seem almost/ nearly as hard as P≠NP.

Jim

8:48 PM

@vzn mean GI would not be in P?? i believe GI is not in P though it would cause some "hierarchy problem " if it is proven that GI is NP complete or something like that/

@vzn ll look carefully.

@vzn , is it more clear than earlier?

@vzn should I leave a comment there with my post's URL?

vzn

10:02 PM

@Jim its not ready yet but mckay might answer emails

@Jim it is tricky to consider "submatrices" of the adjacency matrix unless you immediately consider/ explain reordering rows/ columns.

re P vs NP/ GI take a look at ladners theorem.

NP-intermediate

In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since the other direction is trivial, we can say that P = NP if and only if NPI is empty. Under the assumption that P ≠ NP, Ladner explicitly constructs a problem in NPI, although this problem is artificial and otherwise...

afaik GI is conjectured harder than P and not NP complete. ie "NPI"

seemingly, proving any problem "NPI hard" would essentially be also a P≠NP proof.

Transcript for

$Mathematics$ Room for Jim and vzn