3 ms·
This would be big news if true (though not P=NP-big; graph isomorphism is an apparently-hard problem that isn't known to be NP-hard). From a cursory glance, it
by gjm11 17y ago
This would be big news if true (though not P=NP-big; graph isomorphism is an apparently-hard problem that isn't known to be NP-hard).
From a cursory glance, it doesn't look terribly promising, but I haven't made a serious attempt to see what he's doing and how it might work. Examples of not-terribly-promising things:
1. He proves what he calls "Assertion 1", then says that it "suggests" some other propositions that he calls "Conclusion 1", "Conclusion 2", "Conclusion 3". He doesn't offer any proofs of these; they don't seem to be obvious consequences of Assertion 1; they don't even seem very likely to be true. In particular, Assertion 1 has the form "if graphs G and G' are isomorphic, then [linear algebra stuff]" and Conclusion 2 (which he uses later) has the form "if [linear algebra stuff] then graphs G and G' are isomorphic".
2. He then defines this thing he calls a W-matrix, which seems like it basically encodes for a given vertex of a given graph which other vertices are at any given distance from it. He then appears to claim -- I'm not quite sure, because his notation is eccentric and it's late at night -- that equality of W-matrices is basically the same thing as similarity of vertices (i.e., whether some graph automorphism carries one to the other), and that doesn't look right to me.
I repeat that I haven't looked at this carefully, and I'm not an expert in the field anyway. But it's not compelling enough to make me want to spend much more time on it; I expect that if it turns out to be valid someone smarter than me will check it over and let the world know :-).
- pmb 17y agoAnyone can post to the ArXiv. So now wait a few weeks. One test: does his algorithm work for bipartite graphs? Another test: his algorithm uses real numbers. This is sketchy, as real numbers can't actually be represented in a computer. The paper is pretty poorly written for two reasons: English is clearly not this guy's first language (no crime there, as it is said that the language of science is "heavily accented english") but he is also using a little too much handwaving for my comfort. This is a pretty math-heavy result, and this is not an airtight proof in any sense. Basically: I agree with everything you said about it not being compelling enough for me to spend more time with it. Fun fact so that I'll say more than "I agree": if GI is in P, the the polynomial hierarchy collapses to a level that I forget, and if GI is NPC it collapses to a PI_2! Neat!
- mt2 17y ago> does his algorithm work for bipartite graphs? Please, download the program and test any graph you like ;)
- carterschonwald 17y agoAs an aside, theres some really beautiful results in graph theory that are only nicely expressible if you use linear algebra (aka spectral graph theory). That being said, there are several problems with the paper: 1) it seems to implicitly assuming (without realizing it) that any two graphs it is considering at k-regular for some unspecified k. This is barely more general than assuming that graphs are planar, so itd be easy to have pretty reasonable algorithm for such a case (i'm pretty sure there are bunches in the research literature). Also, it doesn't really seem to be addressing integrality of the linear programs, which i think is kinda key when using linear programs for combinatorics!
- mt2 17y ago> they don't seem to be obvious consequences of Assertion 1 They do seem! In a few words, this fragment was cited from peer reviewed article http://dx.doi.org/10.1007/s11172-006-0105-6 http://dx.doi.org/10.1007/s11172-006-0105-6 . > how it might work Please, download the program and see...