Nothing Special   »   [go: up one dir, main page]
Wikipedia

Talk:Graph isomorphism

Latest comment: 6 years ago by AndrewKepert in topic Fix definition?
Learn more about this page

Software review

edit
Latest comment: 15 years ago15 comments4 people in discussion

There seems to be a need to start this discussion. The article badly needs a more or less comprehensive review of available software for testing graph isomorphism. Here is just a couple of reasons for that:

  1. Testing graph isomorphism is of great practical importance; despite the uncertainty about its theoretical complexity, people still want to solve this problem in practice.
  2. Even if the worst case is hard to solve, many problem instances are easy and can be resolved by simple heuristics (e.g., the most trivial perhaps is comparison of the number of vertices of two graphs).

I started the section Software today but to my surprise some trolls immediate came into play and started deleting my additions without any explanation. Well, one of my items was indeed not that suitable for Wikipedia (thanks to Twri for pointing that out) but the others perfectly make sense. David Eppstein deleted my recent addition of a link to Combinatorica package for Mathematica CAS, motivating that it is "not primarily about isomorphism and would be several positions down on a list of notable isomorphism implementations". I believe that is not a legitimate reason for deletion since:

  1. This is a reputable package for widely used Mathematica CAS.
  2. This packages contains functions for testing/finding graph isomorphism and that makes it very relevant to including into Software section of Graph isomorphism article. It may be not "not primarily about isomorphism" as it contains a bunch of other discrete mathematics related functions, but that does not neglect its abilities of solving graph isomorphism problems.
  3. The statement about benchmarking is also an irrelevant argument: first, it is subjective without an appropriate citation; second, even if this package is not a state-of-art tool for graph isomorphism problems, it is still useful for many problems of this kind (and many users of Mathematica).

Based on the above explanation, the link to Combinatorica package should be restored in Software section. Maxal (talk) 00:18, 3 March 2009 (UTC)Reply

The primary objection is adding external links without addition of encyclopedic content, especially about software and packages. Wikipedia is a repository of encyclopedic information about notable things described in reliable sources. A mere link to any software package is useless from these points of view and often look dubious: after all, people can use google themselves to find out what else in on web. I agree that a section about implementations is badly missing. And a proper solution would be to add it, to describe implementations other people (besides authors, friends and family members) think notable and state so in published materials. In particular, in the case at hand, if it is known which algorithm is implemented in Mathematica, then it may be briefly mentioned here. Otherwise a ref to Mathematica is of low relevance: it has thousands of functions, but we are not going to include external links to Mathematica into thousands of wikipedia articles. - 7-bubёn >t 00:35, 3 March 2009 (UTC)Reply
The authors of Combinatorica are respected scientists, there is a book published about solving problems with the Combinatorica package - isn't that all make this packages "notable"? Maxal (talk) 00:42, 3 March 2009 (UTC)Reply
It may be notable as a software package in general and yet not sufficiently notable in the much more specific context of implementations of graph isomorphism algorithms. —David Eppstein (talk) 00:55, 3 March 2009 (UTC)Reply
But it is notable enough for Mathematica users etc. Anyway, these all are still just subjective opinions. The facts are: it is a notable package, it is able to solve (some) graph isomorphism problems; and that makes it relevant for mentioning it in the current Wikipedia article. Maxal (talk) 01:07, 3 March 2009 (UTC)Reply
(Edit conflict) See our guidelines on external links, regarding what sorts of links include: “A well-chosen link to a directory of websites”. We already include such a well-chosen link, to Skiena's SUNYSB listing of graph isomorphism implementations. Therefore, we don't need to duplicate the contents of that link ourselves: Wikipedia is not a web directory. Additionally, it seems against our policies on maintaining a neutral encyclopedia to push for the inclusion of this link, for a package of routines for a specialized commercial piece of software (Mathematica) that only includes isomorphism as one among a large number of other routines, and not to push for links to highly-regarded packages that are specific to graph isomorphism such as Nauty. (For more on the relative significance of these different implementations, the ratings on the SUNYSB site might be relevant.) I continue to feel that the link to Combinatorica should not be included: there are five more-deserving links included on the SUNYSB list, and including all of them would head more towards being an indiscriminate web directory than being an encyclopedia. —David Eppstein (talk) 00:36, 3 March 2009 (UTC)Reply
I don't see why a link to Skiena's should prevent from mentioning various "notable" software implementations in Wikipedia article. Also notice that the package Combinatorica is not commercial itself (it is run under commercial Mathematica software but that does not make it commercial; and Mathematica is already described in Wikipedia). Links to other reputable software implementations are welcome as well. And there are not so many of them, so the article won't be "directory of websites" even if we include them all. Maxal (talk) 00:53, 3 March 2009 (UTC)Reply
  • Actually, Combinatorica is commercial, and not particularly a particularly good implementation of a graph isomorphism algorithm. (I'm a Mathematica user, and I cannot use Combinatorica without purchase.) — Arthur Rubin (talk) 01:31, 3 March 2009 (UTC)Reply
That's a non-sense. The package is freely available for download from the official website and distributed in the form of plain text Mathematica source code. Moreover, its header mentions the following licence:
This package may be copied in its entirety for nonprofit purposes only.
Sale, other than for the direct cost of the media, is prohibited.  This
copyright notice must accompany all copies.

Maxal (talk) 02:00, 3 March 2009 (UTC)Reply

The purpose of mentioning Mathematica is to indicate that the package won't run without it (i.e., this package is not a standalone application). Maxal (talk) 02:04, 3 March 2009 (UTC)Reply
Software I develop will not run without Microsoft Foundation Classes, yet my company does not put Microsoft in the first lines of its ad brochures. Hey, even with Microsoft it will not run without Intel chips. There is a healthy intellectual property threshold, and I don't believe it is inside Mathematica, rather than outside it, unless you present a solid proof otherwise. - 7-bubёn >t 02:16, 3 March 2009 (UTC)Reply
I explained why I gave a link to Mathematica - but I would not care if it is not mentioned at all. It is more important that Combinatorica package (and similar software) should be listed in the article. Maxal (talk) 02:21, 3 March 2009 (UTC)Reply
<sigh>. Let me reiterate: you may list anything you want sufficiently relevant, provided the you supply your additions with references to independent reliable sources which speak for notability and relevance of the software in question. These are among the most fundamental rules governing the content of wikipedia. A simple addition of external links to software packages does not conform these rules. - 7-bubёn >t 02:30, 3 March 2009 (UTC)Reply
Oh, I see now what you meant under "link to Mathematica". A brief search discovered, in particular, a book about teaching discrete math in high school; and a book about randomness in physics that both explicitly mention Combinatorica's graph isomorphism testing function IsomorphicQ. I bet there other similar references exist. Maxal (talk) 02:58, 3 March 2009 (UTC)Reply

Tim32 behavior

edit
Latest comment: 15 years ago4 comments4 people in discussion

I suggest to file a formal complaint against Tim32, since it appears that he persistently refuses to accept the local consensus. Despite all arguments seen above, there is no evidence of the possibility of peaceful resolution. I cannot do it myself, since I am not well versed in wikilawyerese, but I will second the motion. - 7-bubёn >t 20:21, 3 March 2009 (UTC)Reply

If the problems with Tim32 continue, I recommend consulting Wikipedia:Mediation Cabal, where some informal dispute resolution could occur. Dcoetzee 19:34, 10 March 2009 (UTC)Reply
The edits of User:Tim32 on this page look like self-promotion to me. That falls under the 'promotional editing' clause of our Conflict of Interest guideline, which is explained under WP:COI#Blocks. I think that we are getting close to the point where Tim32 should be given a final warning against inserting reference to his own work into Wikipedia articles. EdJohnston (talk) 20:28, 10 March 2009 (UTC)Reply

Now he's trying it at Graph isomorphism problem: [1]. — Emil J. 12:28, 24 June 2009 (UTC)Reply

GI in chemistry

edit
Latest comment: 15 years ago19 comments6 people in discussion

The article about GI applications in chemistry by Trofimov and Smolenskii cited in Arjeh M. Cohen , Jan Willem Knopper and Scott H. Murray, Automatic Proof of Graph Nonisomorphism, Mathematics in Computer Science, 2008, doi 10.1007/s11786-008-0052-8 --Tim32 (talk) 08:31, 10 March 2009 (UTC)Reply

It is mentioned in passing; even the second author's name is screwed up, which speaks of notability :-) No minimal discussion of the essence. - 7-bubёn >t 18:59, 10 March 2009 (UTC)Reply
See, Google scholar--Tim32 (talk) 22:54, 11 March 2009 (UTC)Reply
Yes, Google scholar does not find any citation to the paper you are pushing, we already know that. What was your point then? — Emil J. 10:50, 12 March 2009 (UTC)Reply
No, Google scholar found: Arjeh M. Cohen , Jan Willem Knopper and Scott H. Murray, Automatic Proof of Graph Nonisomorphism, Mathematics in Computer Science, 2008, doi 10.1007/s11786-008-0052-8--Tim32 (talk) 11:42, 12 March 2009 (UTC)Reply
No it did not. This is not the first time this user supplies us with info which he did not bother to verify himself. - 7-bubёn >t 17:19, 12 March 2009 (UTC)Reply
You did not find "doi 10.1007/s11786-008-0052-8" ? You did not find Automatic Proof of Graph Nonisomorphism paper  ? You did not find "Trofimov" in this paper? (See, ref [23] on page 19)--Tim32 (talk) 22:15, 12 March 2009 (UTC)Reply
I did not find it in Google scholar you provided. I have already described my findings. - 7-bubёn >t 23:14, 12 March 2009 (UTC)Reply
Click the link Google scholar, click link "Cited by 1" under the reference to the paper, Direct link Ok? --Tim32 (talk) 09:31, 13 March 2009 (UTC)Reply
You should have started from "direct link" in the first place. We are not to solve internet maze puzzles here. - 7-bubёn >t 16:12, 13 March 2009 (UTC)Reply
You should have started from google help! If your skills in Computer Sci. area are so low, then let you stop to write to this page as well as to other computer sci. pages, before you will improve your skills to search in google.--Tim32 (talk) 16:31, 13 March 2009 (UTC)Reply
PS. BTW, special Russian joke: кто играет 7 бубен - тот бывает зае... :)
Yep, I play preferans and that's what happened to me in wikipedia, hence the name. - 7-bubёn >t 20:12, 13 March 2009 (UTC)Reply
OK, so it appears it was referenced. Once. That doesn't make it notable. — Arthur Rubin (talk) 19:34, 13 March 2009 (UTC)Reply
Where had been written the rule: if Once, then That doesn't make it notable? How much you need? :))) Is it seriously?! :) --Tim32 (talk) 22:02, 13 March 2009 (UTC)Reply
7-bubёn! Sorry for your nic-name, but it seems you had selected this one especially for similar jokes ;)--Tim32 (talk) 22:02, 13 March 2009 (UTC)Reply
BTW, Ребята, раз вы все так хорошо понимаете по-русски, может, мы наши проблемы выясним на этом языке :)--Tim32 (talk) 22:02, 13 March 2009 (UTC)Reply
Translation: "Guys, once you understand so well in Russian, can we find out our problems in this language" Do not post in foreign languages on the Engish wikipedia please unless you provide a translation or strong justification, it is against policy and rude. Verbal chat 13:47, 24 June 2009 (UTC)Reply
I guess it was a joke no one bothered to comment. Please cite the policy you refer to. From my side, WP:AGF: if you cannot understand it, ignore it, unless it has implications on article content. After all, some write in English no one can understand :-) - Altenmann >t 15:29, 24 June 2009 (UTC)Reply
Was that a Google translation? AFAICS, it reads "Guys, since (or once?) you all understand Russian so well, maybe we will settle our problems using this language", not "find out". Anyway, as Altenmann said, it is a harmless joke. Gosh, it even sports a smiley. — Emil J. 16:04, 24 June 2009 (UTC)Reply

Complexity

edit
Latest comment: 14 years ago42 comments7 people in discussion

The article says,

it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete.

This seems doubtful to me since problems in NP are assumed to *not* be NP-Complete until proven otherwise. The next statement also seems dubious:

one of only two of that list whose complexity remains unresolved.

I don't know the upper bound for the time complexity of determining whether two graphs are isomorphic, but I'm quite sure a bound is known. Jwesley78 22:56, 31 March 2010 (UTC)Reply

Your "this seems doubtful to me" statement makes no sense to me. It is true that:
  • At the time Garey and Johnson wrote their book, most "natural" problems in NP (natural in an intuitive sense meaning that researchers had looked at them as important problems to solve in some application area) were either known to be polynomial time or known to be NP-complete. Garey and Johnson listed a small number of exceptions as "open problems", of which Graph Isomorphism was one.
  • The complexity of all but two of their open problems has been resolved, in the sense that a polynomial time algorithm or an NP-completeness proof has been found. Graph isomorphism is still unresolved in this sense.
  • There are now a few other natural problems that are similarly known to be in NP, not known to have a polynomial time algorithm, and not known to be NP-complete. But just as it was true when Garey and Johnson wrote it, this set of problems is still small in comparison with the set of problems for which polynomial time algorithms or NP-completeness has been proved.
As for "a time bound is known", that is very different from determining whether it belongs to P or whether it is NP-complete, both of which are binary and mutually exclusive possibilities. Of course it might be possible to prove that (with the assumption that P≠NP) GI is neither in P nor NP-complete; that would also be a major result and is also still unknown. —David Eppstein (talk) 23:41, 31 March 2010 (UTC)Reply
OK, I need a little more clarification:
  1. I've run across many problems which are in NP , but are not known to be NP-complete or solvable in polynomial time. Perhaps, these would not be considered "natural problems"? I mentioned integer factorization, and discrete logarithm in my first comment, but also several graph recognition problems, e.g., unit distance.
  2. I'm showing my ignorance of complexity theory. Since it is known to be in NP, what is meant by "complexity remains unresolved"? I understand what you are saying, but saying it this way seems unclear to me. 01:10, 1 April 2010 (UTC)
Thanks, Jwesley78 00:44, 1 April 2010 (UTC)Reply
Saying that its complexity "remains unresolved" seems to assume that the problem is actually NP-complete or in P, but we're just not sure which one yet. It could very well be in neither. Integer factorization, for example, seems unlikely to be NP-complete, and equally unlikely to be in P (at least we all hope so!). Jwesley78 01:45, 1 April 2010 (UTC)Reply
Factorization is the other one on Garey and Johnson's list (or actually I think it was primality testing, which is now resolved, but close enough). Yes, there are other unresolved questions, but not large numbers of them in comparison to the large number of polynomial algorithms and the large number of NP-complete problems now known. As for "remains unresolved", a proof that (assuming P≠NP) the problem is neither in P nor NP-complete would also be a resolution. —David Eppstein (talk) 01:50, 1 April 2010 (UTC)Reply
I found an article from 2007 called "A Polynomial Time Algorithm for Graph Isomorphism". Here is the link http://arxiv.org/abs/0711.2010 I guess it means graph isomorphism doesn't belong to NP. (Jurica Tot (talk) 13:15, 11 April 2010 (UTC))Reply
Now I found yet another link to polynomial time algorithm for graph isomorphism also on the first page of google search for graph isomorphism algorithm. Here it is http://www.dharwadker.org/tevet/isomorphism/ They weren't there few weeks ago when I created my own polynomial algorithm. It's my bad luck. Jurica Tot (talk) 13:33, 11 April 2010 (UTC)Reply
Those papers are not peer reviewed and may well be wrong. In particular, for the arxiv one, arxiv's standards are to allow papers to be published even if the moderators think they're incorrect as long as they're on-topic. The Czerwinski arxiv one you point to is far from the only one to claim to prove the problem polynomial; it spends a lot of time and effort proving the obvious facts that for instances that are isomorphic it will say they are but it doesn't seem to have any attempt at a proof that non-isomorphic instances will be correctly distinguished from each other. —David Eppstein (talk) 16:40, 11 April 2010 (UTC)Reply
@Jurica Tot. Re: "I guess it means graph isomorphism doesn't belong to NP". The problem is in NP b/c a solution (or "certificate"), which in this case would be a bijective mapping of vertices in one graph to vertices in the other, can be verified in polynomial time; P is a subclass of NP. The assumption is that, if P != NP, that P is disjoint from NP-complete. Justin W Smith talk/stalk 17:34, 11 April 2010 (UTC)Reply
Hidden off-topic discussion; Wikipedia is not for the discussion of original research
Out of sheer curiosity, I've read two pages from the paper. That is, I started in the middle of page 2, where stuff begins, and I stopped upon reaching the first patent nonsense, namely Property 5 in the middle of page 4. Anyone who ever worked with random walks on graphs or Markov chains or expanders or a similar subject involving adjacency matrices will instantly recognize that this is dead wrong, nothing resembling this "Property" can hold true. But for definiteness, here's a simple counterexample: let the graph be the 4-cycle, and let the vector of initial weights be  , so that  . Then the solution of the linear system is  . Thus, bi attains maximum at i = 2, whereas xi attains maximum at i = 3. (It's just as easy to construct a counterexample on a graph of order three; I chose this one because it has the additional benefit of being regular.)—Emil J. 13:37, 22 April 2010 (UTC)Reply
Yes, EmilJ, you found a bug. Thank you very much! What do you think, how this bug may be fixed?
1) We can say if bi=max, then xj=max
2) We can delete Property 5 -- it has no sense for followed proof.
Anyhow this bug is not fatal error.--Tim32 (talk) 10:39, 23 April 2010 (UTC)Reply
Your paper is hopelessly unreadable; "fixing" it cannot be achieved by a small change to one lemma. But in-depth discussion of its merits does not belong here, except to note that (like many other failed attempts to prove GI in P on the arxiv) it should not be listed in this article unless/until it has been peer reviewed. —David Eppstein (talk) 15:13, 23 April 2010 (UTC)Reply
Dear David, I have already received many congratulations for this preprint, nobody (except you) said me "unreadable" (BTW unreadable paper would be rejected: please, see arXiv rules). For example, see above, EmilJ was able to read and to understand two pages from it and he found very useful counterexample (thanks again, EmilJ). But you are right, this is preprint only and so it should not be listed in this wiki article, in contrast with my initial peer reviewed paper, which link you had deleted without complete arguments (see GI Applications section). Anyhow I will be very thankful for anybody for constructive criticism ;-)--Tim32 (talk) 16:11, 23 April 2010 (UTC)Reply
If an allegedly peer-reviewed "post-modern" journal would accept nonsense, why would "arXiv" not. However, as most of us are not professional mathematicians (which is the appropriate field, whatever you might think), we are not qualified to determine whether one serious error is a show-stopper or a minor point. — Arthur Rubin (talk) 16:23, 23 April 2010 (UTC)Reply
Hi Arthur, For example, I do remember your nonsense about Russian sci. journals ;-) --Tim32 (talk) 19:35, 23 April 2010 (UTC)Reply
I'm still right. It's a mathematical question, so the peer-reviewers should be mathematicians, rather than chemists. — Arthur Rubin (talk) 20:21, 23 April 2010 (UTC)Reply
Again, about remark by EmilJ. The bug is fixed. The text should be: "We can set such bi=max..., that xi=max...". This property 5 is not used for proof, so this property will be renamed with "note" in the next version of the preprint. Thanks again. Any constructive criticism is welcome!--Tim32 (talk) 09:42, 2 May 2010 (UTC)Reply
Concur with David Eppstein, above. Also, unless "theorem" in computer science means something different than in mathematics, mathematicians should agree whether this paper contains a proved theorem. I think it safe to say that (at least some) professional mathematicians do not agree, at this point. — Arthur Rubin (talk) 13:27, 2 May 2010 (UTC)Reply
Dear Arthur Rubin,
I do understand every of your word, but I do not understand what did you want to say. It is too abstract to be understandable. Meanwhile, you did not answer my questions to you -- see above. --Tim32 (talk) 16:22, 2 May 2010 (UTC)Reply
It appears that your paper may be too concrete to be correct. Property 4 appears to be so badly stated that it's "not even wrong". There are a few potentially correct statements, but you haven't proved any.
  1. If ΔB ≥ 0, then Δx ≥ 0.
  2. If ΔB ≥ 0, and ΔB ≠ 0, then Δx > 0. (May require the graph to be connected.)
  3. If ΔB ≥ 0, then max Δx ≤ max ΔB.
But you haven't proved, or even given a credible argument, for any of those. The statement:
If ΔB > 0, then 0 < Δx < ΔB (coordinatewise)
is clearly false.
I'd also like to know what you mean by "coincide to an accuracy" in conclusions 1 and 3. — Arthur Rubin (talk) 08:20, 3 May 2010 (UTC)Reply
> May require the graph to be connected.
See p.2: "Further, without loss of generality of the task, we will consider undirected connected graphs[...]". Thanks, --Tim32 (talk) 08:30, 3 May 2010 (UTC)Reply
> If ΔB > 0, then 0 < Δx < ΔB
> is clearly false.
Why? --Tim32 (talk) 08:37, 3 May 2010 (UTC)Reply
Note, x is arithmetic mean of positive values!--Tim32 (talk) 09:13, 3 May 2010 (UTC)Reply
> what you mean by "coincide to an accuracy"
You can find a lot "coincide to an accuracy" in Google, for example: "In other words, the spherical waves emitted by various points in the source, assuming it to have finite extent D, must coincide to an accuracy of about[...]" Stephen G. Lipson, Henry Lipson, David Stefan, Optical physics, 3rd ed, Cambridge University Press, 1995, p.163. What is the problem? --Tim32 (talk) 09:01, 3 May 2010 (UTC)Reply
In no particular order:
"Coincide to an accuracy of ε" makes sense, although not, generally, in a mathematical paper. "Coincide to an accuracy" without a specified value does not.
That "if ΔB ≥ 0, and ΔB ≠ 0, then Δx > 0" follows from the following: If M is a strictly sub-stochastic square matrix (all entries non-negative, all row sums less than 1) (and has some additional properties related to the connectivity of the graph, probably Mn has all entries positive for some positive n), then (I-M)-1 has all entries positive. This is true, as the power series for (I-M)-1 converges, but you haven't provided a proof or proof outline.
That Δx < ΔB (coordinatewise) is false, in general. Consider, first B = (1,0,0,...). As the correspoding Δx has all components non-zero, it's not the case that Δx < ΔB componentwise. However, it's not the case that 0 < ΔB coordinatewise, so this isn't a counterexample. However, if you set
 
then Δx1 is still not less than ΔB1, except in the first component.
The fact that you don't consider these problems obvious casts doubt on your expertise, I'm afraid. If those problems occured in a peer-reviewed paper, it would cast doubt on the reliability of the peer-reviewers and of the journal as a whole. — Arthur Rubin (talk) 15:15, 3 May 2010 (UTC)Reply
My mistake on Property 4. It's just badly written, and the ΔB should be ΔBi. The proof is still bogus, and my restatements are both easier to prove and better written. However, Property 5 is still false, Note 1 is false, the statement t(i) = j in Note 2 and Conclusion 5 appears to require Property 5, and Lemma 1 requires an even stronger coherence requirement; not even Property 5 would be enough. — Arthur Rubin (talk) 08:21, 4 May 2010 (UTC)Reply
Why did you write "0 < ΔB coordinatewise","then Δx1 is still not less than ΔB1, except in the first component"? Did you mean that ΔB is vector? In my paper ΔB is positive real number. What graph did you mean? See Algorithm 1 for more info, it did not use   but NewB :=newB+ΔB (Procedure P1). In my program ΔB=4.0. Also, it seems that you did not read Property 2. Why "Lemma 1 requires an even stronger coherence requirement"? If something seems to you "just badly written", then you have to rewrite it, to be sure that you understand my statement. I'm afraid, that similar bug report would be rejected by MSDN or by Wolfram MathWorld as unclear and so useless. Try again... --Tim32 (talk) 10:53, 4 May 2010 (UTC)Reply
PS BTW the paper had been classified not as "mathematical paper", but as Computer Science > Data Structures and Algorithms ;)--Tim32 (talk) 10:53, 4 May 2010 (UTC)Reply
PPS Did you read my correction of Property 5 above? --Tim32 (talk) 10:57, 4 May 2010 (UTC)Reply
Your correction to Property 5 above doesn't help where it's used later in Note 2 and Conclusion 5, and your assertion in Lemma 1, that the individual mappings
 
can be taken to have the same t is unsupported at he present time. It may be true, but your "argument" is absurd.
As for the correct way to state Property 4, it seems best done in 4 parts, where ΔB and Δx are vectors.
  1.  
  2. If, in addition, ΔB is not identically 0, then Δx > 0 (componentwise).
  3.  
  4. If, in addition, the vector B is not constant, then maxΔx < maxΔB.
Parts 1 and 2 follow from the substochastic matrix property above, and parts 3 and 4 follow from that, linearity, and property 3.
Alternatively, as vectors, the property can be written neatly as:
 
and, if any of the inequalities is proper, then all are. The proof becomes more complicated, basically using part 1 above and property 3 (and linearity) for the inequalities, and part 2 above to prove that the inequalities would be proper. — Arthur Rubin (talk) 16:35, 4 May 2010 (UTC)Reply
Thank you for your comments. The proof of Lemma 1 is corrected, now "the same t problem" is supported. I will update the paper in the near future.--Tim32 (talk) 08:05, 9 June 2010 (UTC)Reply
PS. "Coincide to an accuracy" will be replaced with "for any i there exists j such that the solutions of the systems ... coincide modulo a permutation of the coordinates ..." Ok?--Tim32 (talk) 08:45, 9 June 2010 (UTC)Reply
PPS. Have you any problem for proof of Lemma 2 understanding?--Tim32 (talk) 08:45, 9 June 2010 (UTC)Reply
Let's keep this off-Wiki; I'm still not convinced that Lemma 1 can be salvaged. If it can, I contend that the proof that GI is in P can be done without "coincide to an accuracy" clauses, by using rational arithmetic in calculating (I-M)-1 and hence Wi. The determinant and adjoint of (I-M) have denominator at most  , and numerator at most nn times that, so the lengths are polynominal in n, and hence (I-M)-1 and hence Wi can be calculated as a rational number in polynomial time. — Arthur Rubin (talk) 08:59, 9 June 2010 (UTC)Reply
Yes, you could not see the new proof, so you are still not convinced :) Please, wait for updated paper.--Tim32 (talk) 07:33, 10 June 2010 (UTC)Reply

The paper was updated: http://arxiv.org/abs/1004.1808 --Tim32 (talk) 07:48, 22 September 2010 (UTC)Reply

It seems that nobody found any error! So the paper is correct.--Tim32 (talk) 09:48, 21 October 2010 (UTC)Reply
Nonsense. I, at least, haven't really had time to look at it. However, even if it were correct, it's not published, so it cannot be used in Wikipedia. — Arthur Rubin (talk) 14:46, 21 October 2010 (UTC)Reply
Nonsense. There is a lot of links to arXiv in Wiki. For example, see Grigori Perelman.--Tim32 (talk) 16:44, 21 October 2010 (UTC)Reply

Good, reliable source

edit
Latest comment: 10 years ago2 comments2 people in discussion

There is a good paper from 1977 summing up approaches to graph isomorphism until then, search for "The Graph Isomorphism Disease" from Ronald C. Read and Derek G. Corneil. — Preceding unsigned comment added by 134.93.143.232 (talk) 11:29, 11 October 2013 (UTC)Reply

It is about Graph isomorphism problem; listed there, too - Altenmann >t 08:32, 8 January 2014 (UTC)Reply

Laymans definition

edit
Latest comment: 10 years ago6 comments4 people in discussion

I took the liberty of adding a laymen's definition near the top of the article for the less mathematically inclined to form a concept of the subject. As a programmer, it took me a few minutes of rereading the opening section to decipher what a graph isomorphism is - I am sure my definition can be reworded to be more precise but still maintaining readability for non mathematicians that have an interest in this Wikipedia article (we do exist). I realise the 'simple english' Wikipedia site exists but surely there can be a middle ground Norlesh (talk) 11:49, 7 January 2014 (UTC)Reply

I'm afraid I don't understand that definition, so I can't suggest a rewording which makes sense and is much less complicated than the formal definition. However, as a mathematician, I couldn't report on what makes a definition understandable to the layman. Perhaps:
Two graphs are isomorphic if they have the same number of vertices and there are numberings of the graphs so vertex pairs with the same numbers are connected in one graph if they are connected in the other.
(Emphasis added to note where the mapping between the graphs corresponds.) — Arthur Rubin (talk) 17:14, 7 January 2014 (UTC)Reply
I agree that this is an improvement over Norlesh's attempt at a definition, which could easily be misread to imply (incorrectly) that all 3-regular graphs on the same numbers of vertices are isomorphic. —David Eppstein (talk) 19:21, 7 January 2014 (UTC)Reply
He-he, this is the trouble with "layman's" definitions: you have to try really hard to make it readable and reasonably correct and unambiguous . The second version is not (quiz: find 7 reasons why :-). Now, again, does a layman know what is graph? May be he thinks it is a chart? To avoid the latter problem I'd suggest to put the informal definition into section "example" and rename it 'Informal definition'. Now we still need a 'GI for Dummies' ... - Altenmann >t 08:49, 8 January 2014 (UTC)Reply
Something like this: "A graph labeling is an assignment of a unique label to every vertex of a graph. Two graphs are said to be isomorphic if they have the same number of vertices and there are labelings of the two graphs such that two labels are connected by an edge in one graph if and only if they are connected by an edge in the other." - Altenmann >t 09:15, 8 January 2014 (UTC)Reply
(quiz: find 3 problems with this definition :-) - Altenmann >t 09:17, 8 January 2014 (UTC)Reply

possible breakthrough to watch out for

edit
Latest comment: 9 years ago1 comment1 person in discussion

--Kmhkmh (talk) 01:48, 13 November 2015 (UTC)Reply

Fix definition?

edit
Latest comment: 6 years ago1 comment1 person in discussion

The definition as stated applies only in the context where graphs have no parallel edges. This is a lot of people's favourite definition of "graph", but it is not universal. See Graph (discrete mathematics). FWIW I prefer "graph" to be able to include parallels and loops, and "simple graph" to be without loops or parallels. Andrew Kepert (talk) 23:47, 6 December 2018 (UTC)Reply

Add topic
Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Graph_isomorphism&oldid=1212670010"