Talk:Graph isomorphism

Software review

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)

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)

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)

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)

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)

(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)

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)

• 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)

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)

• The link to Skiena's explains that Mathematica uses Combinatorica package for GI, hence a separate link to Mathematica is redundant and constitutes an inexact credit. - 7-bubёn >t 01:31, 3 March 2009 (UTC)

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)

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)

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)

<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)

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)

Tim32 behavior

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)

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)

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)

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

GI in chemistry

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)

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)

See, Google scholar--Tim32 (talk) 22:54, 11 March 2009 (UTC)

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)

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)

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)

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)

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)

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)

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)

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)

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)

OK, so it appears it was referenced. Once. That doesn't make it notable. — Arthur Rubin (talk) 19:34, 13 March 2009 (UTC)

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)

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)

BTW, Ребята, раз вы все так хорошо понимаете по-русски, может, мы наши проблемы выясним на этом языке :)--Tim32 (talk) 22:02, 13 March 2009 (UTC)

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)

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)

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)

Complexity

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. Jwesley₇₈ 22:56, 31 March 2010 (UTC)

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)

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, Jwesley₇₈ 00:44, 1 April 2010 (UTC)

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!). Jwesley₇₈ 01:45, 1 April 2010 (UTC)

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)

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))

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)

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)

@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)

Hidden off-topic discussion; Wikipedia is not for the discussion of original research

• See also http://arxiv.org/abs/1004.1808v1 --Tim32 (talk) 08:10, 17 April 2010 (UTC)

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 ${\vec {B}}=(3,33,30,30)$, so that ${\vec {b}}=(1,11,10,10)$. Then the solution of the linear system is ${\vec {x}}=(18,26,27,25)$. Thus, b_i attains maximum at i = 2, whereas x_i 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)

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 b_i=max, then x_j=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)

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)

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)

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)

Hi Arthur, For example, I do remember your nonsense about Russian sci. journals ;-) --Tim32 (talk) 19:35, 23 April 2010 (UTC)

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)

• You are not right. The peer-reviewers for that paper were computer scientists from mathematical chemistry area.--Tim32 (talk) 20:32, 23 April 2010 (UTC)
• Also, you are not right: GI applications for chemistry is not mathematical question only.--Tim32 (talk) 20:34, 23 April 2010 (UTC)

Again, about remark by EmilJ. The bug is fixed. The text should be: "We can set such b_i=max..., that x_i=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)

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)

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)

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)

> 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)

> If ΔB > 0, then 0 < Δx < ΔB

> is clearly false.

Why? --Tim32 (talk) 08:37, 3 May 2010 (UTC)

Note, x is arithmetic mean of positive values!--Tim32 (talk) 09:13, 3 May 2010 (UTC)

> 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)

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 Mⁿ 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

$\Delta B_{1}=\Delta B+0.01\times \Delta x,$

then Δx₁ is still not less than ΔB₁, 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)

My mistake on Property 4. It's just badly written, and the ΔB should be ΔB_i. 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)

Why did you write "0 < ΔB coordinatewise","then Δx₁ is still not less than ΔB₁, 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 $\Delta B:=\Delta B+0.01\times \Delta x;$ 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)

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)

PPS Did you read my correction of Property 5 above? --Tim32 (talk) 10:57, 4 May 2010 (UTC)

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

$f_{h}{\underset {\sim }{\longleftrightarrow }}f'_{l}$

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. ${\text{If }}\Delta B\geq 0,{\text{ then }}\Delta x\geq 0{\text{ componentwise}}.$
2. If, in addition, ΔB is not identically 0, then Δx > 0 (componentwise).
3. ${\text{If }}\Delta B\geq 0,{\text{ then }}\max \Delta x\leq \max \Delta B.$
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:

$\min \Delta B\leq \min \Delta x\leq \max \Delta x\leq \max \Delta B,$

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)

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)

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)

PPS. Have you any problem for proof of Lemma 2 understanding?--Tim32 (talk) 08:45, 9 June 2010 (UTC)

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 W_i. The determinant and adjoint of (I-M) have denominator at most $\prod {(d_{i}+1)}$, and numerator at most nⁿ times that, so the lengths are polynominal in n, and hence (I-M)^-1 and hence W_i can be calculated as a rational number in polynomial time. — Arthur Rubin (talk) 08:59, 9 June 2010 (UTC)

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)

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

It seems that nobody found any error! So the paper is correct.--Tim32 (talk) 09:48, 21 October 2010 (UTC)

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)

Nonsense. There is a lot of links to arXiv in Wiki. For example, see Grigori Perelman.--Tim32 (talk) 16:44, 21 October 2010 (UTC)

Good, reliable source

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)

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

Laymans definition

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)

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)

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)

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)

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)

(quiz: find 3 problems with this definition :-) - Altenmann >t 09:17, 8 January 2014 (UTC)

possible breakthrough to watch out for

• https://www.sciencenews.org/article/new-algorithm-cracks-graph-problem

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

Fix definition?

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)