The Final Solution for Kelly-Ulam Conjecture
-- Dedicated to Koshin Isobe, a Buddhist nun
and my strict elemenary schoolmarm --
No.9662: 2004-04-30 08:51:18 -0000 The third night of dreams with the Psi girls
No.9648: 2004-04-28 06:48:47 -0000 The second night of dreams of the Psi Girls
No.9637: 2004-04-26 07:38:11 -0000 Graph Isomorphism on Geodesic Matrix
-------- Original Message
No.9662--------
Subject: [theory-edge] The third night of dreams with the Psi girls.
Date: Fri, 30 Apr 2004 08:51:18 -0000
From: "Michiro Nasu" michiro@...;
To: theory-edge@yahoogroups.com
Hi Daniele and all!
Thanks to Heaven again, one more longstandig graph problem,
the Kelly-Ulam Conjecture was just solved successively.
Twin babys...so heavy...hard-won...
<The Final Solution for Kelly-Ulam Conjecture>
Throughout this brief, we assume all graphs are undirected,
connected and finite.
Kelly-Ulam Conjecture: Let G have p vertices v_i and H have
p vertices u_i, with p≥3. If for each i, G-v_i and H-u_i
are isomorphic, then the graphs G and H are isomorphic. [1][2]
Of course we need some preparations beforehand. We may
call the graph G/H a parent graph and subgraphs such as
G-v_i child graphs. We will define another Psi number such
as a variation of the original. Further this time we use
adjacency matrices instead of distance matrices because a
"distance" in a child graph is not necessarily the same
with the one in the parent graph corresponding to it. For
example, even if the distance between two vertices x and y
is 4 in a child graph, the actual distance (the shortest
path) in the parent=81@graph may be 2. However as you can
verify easily, at least edges and P2s (paths of length 2)
are similar in the both parent and child graphs. In other
words, "Edges are edges at any places."
D7: Edge Psi number Q is defined as below as usual.
d_ij=0/1 : 1:d(i,j)=1, 0:otherwise w_i =SUM[j=1 to n]d_ij : =degree(v_i), 1≤Dw_i≤n-1 z_ij=d_ijw_j : 0≤z_ij≤n-1 Q_i =SUM[j=1 to n]z_ijX^(j-1) : X=n, 0<Q_i<n^n Q =SUM[i=1 to n]Q_iY^(i-1) : Y=n^n, 0<Q<(n^n)^n
T3: There exist the edge Psi numbers Q and Q' of graphs
G and G' respectively as Q=Q' iff G and G' are isomorphic.
Proof of T3: Exercise. Almost similar to
the proof of T1.
L2: Given two isomorphic graphs G and G'. Enumerate
every edge Psi numbers Q and Q' of G and G' respectively
and make multisets S and S' of them. Then S=S', that is,
the ith Psi number in S agrees to the ith Psi number in S'.
Proof of L2: Since G and G' are isomorphic, there exist
some edge Psi numbers Q and Q' such that Q=Q' by T3. Let
them be Q_0 and Q'_0. Then the adjacency matrices A_0 and
A'_0 obtained from them are exactly the same. Put them at
the top of the edge Psi number sequences S and S'. (To make
things simple, you had better let the labeling synchronize
here.) Permute A_0 and A'_0 by the same permutation p_1 and
let them be A_1 and A'_1. Apparently A_1 and A'_1 are
exactly the same. Get the edge Psi numbers Q_1 and Q'_1
from the adjacency matrices A_1 and A'_1, and put them at
the second position of the sequences S and S' respectively.
Repeat this operation with respect to the edge Psi numbers
Q_i and Q'_i, and the adjacency matrices A_i and A'_i with
the permutation p_i in some exhaustive order, and make n!
permutations and get n! edge Psi numbers pair. Obviously
the sequences S and S' are exactly the same as multisets.
That is, the sequences S and S' are either exactly the same
or none of them is equal obeying whether the graphs are
isomorphic or not. Further if there exists some adjacency
matrix A_i of G from S, then there always exists the matrix
A'_i of G' from S' such as exactly the same with A_i. QED.
Proof of the Conjecture: We solve the problem within the
range of connected graphs. Suppose finite and connected
undirected graphs G and G' such that G-v_i is isomorphic
to G'-v'_i for all i. Let the edge Psi number of a subgraph
G-v_i be Q(i). From the assumption and by T3, Q(i)=Q'(i)
for all i. We enumerate all of the n! Q(i)s by each
permutation p_i# and store the byproducts adjacency matrices
A(i,#) in the matrix AX, where AX is a nXn! matrix of the
adjacency matrix A(i,#) of the child graph G-v_i, and
respectively matrix A'X of the adjacency matrix A'(i,#) of
G'-v'_i, where # is the counter of the permutation p_i#.
We assume that the adjacency matrices AX and A'X are built
up by the similar method described in the proof of L2 such
that AX[i,#]=A'X[i,#] for all i,#. We look such an adjacency
matrix A(i,#) as a *piece*(A,i,#). At first we pick up a
piece(A,1,#) from AX[1,#], which exactly fits to the picture
frame G-v_1, and we find the similar piece(A',1,#) in
A'X[1,#]. Repeat this until we complete the whole tableau
of the adjacency matrices A and A' of G and G' respectively.
Corresponding pieces(A,i,#) and (A',i,#) represent exactly
the same adjacency sub-matrices of A and A' for all i,
which clearly cover the matrices A and A', hence it is
obvious that the adjacency matrix A of G is exactly the
same with the adjacency matrix A' of G'. Thus G and G' are
isomorphic. Now the Conjecture turns out the Theorem. To
extend the result to general graphs seems to be easy. QED.
You see? Do you think that this is not G' but a new graph?
No, it is not. Since the matrix A' built up of the pieces
is an existence. Where there is an edge in A', there exists
an edge in G' substantially. In other words, "Distance is
such a solid thing". Of course there exists no inconsistency
between the adjacency matrix A' and the graph G'. As you have
seen in the proof of L2, the two multisets of the Psi numbers
of graphs G and G' are all or nothing. That is, either all
are the same or all different. You cannot move any one edge
in the adjacency matrix A' without losing the perfect
correspondence among the sets of Psi number sequences.
[1] S.M. Ulam, A Collection of Mathematical Problems,
Wiley, New York, 1960.
[2] Fred Buckley and Frank Harary, Distance in Graphs,
PP 11, Addison-Wesley Publishing Company, 1990.
Michiro Nasu
Baba Laboratory : April 30, 2004
Email: babalabo@... (available at present)
TEL: (81)048-574-3623 (not available at present)
URL: http://www.aya.or.jp/~babalabo
ADDR: 1-3-72-2H Inari-Cho, Fukaya, Saitama Pre.
Japan 366-0026
PS: Thanks to all who read this brief to the end with patience.
Any comment, correction and suggestion would be appreciated. MN
-------- Original Message No.9648
--------
Subject: [theory-edge] The second night of dreams of the Psi Girls.
Date: Wed, 28 Apr 2004 06:48:47 -0000
From: "Michiro Nasu" michiro@...;
To: theory-edge@yahoogroups.com
Hi Daniele and all!
I would like to rewrite D4 as follows. We will find the
canonical geodesic matrix Z* as the minimum one.
D4: The canonical geodesic matrix Z* is a nXn matrix obtained
from an arbitrary matrix Z by the following procedure.
(1) For all i, sort the line sequence {Z_i1,Z_i2,...,Z_in} in
increasing order and let it be Z_i.
(2) Let the number O_i=digitize(Z_i), sort {O_1,O_2,...,O_n}
in increasing order and get the total order O.
(3) Divide {Z_i} into subsets G_1,G_2,...,G_m by ordering O,
where 1≤m≤n is the number of different O_i classes, G_1=
{Z_i|MIN{O_i}} and G_m={Z_i|MAX{O_i}}.
(4) Z_i is viewed like {the determined part|the undetermined
part}; At the beginning, the determined part is empty.
(5) Let the line/column index #=1 and the group index %=1.
(6) If G_% is empty, then increment the group index % by 1;
If %>m then goto (8).
(7) Take an arbitrary vertex V_x with O_x=MIN{O_i in G_%},
determine it at both the line # and the column # for Z*; Set
M(V_x)=#, where M is a mapping V->{1,2,...,n}; Increment the
index # by 1; Re-compute O_i=digitize(Z_i) for all i; Goto (6).
(8) Using the mapping M, arrange the sequence {Z_1,Z_2,...,Z_n}
and get the canonical geodesic matrix Z*.
(9) Applying the mapping M, permute the distance matrix D
and the weight sequence {W_i}, too.
Note: Letting N=n^n, Z_ij<N. "Digitize(Z_i)" means to compute
a N-decimal number from the sequence Z_i={Z_i1,Z_i2,...,Z_in}.
(The sequence order must be varied in time.) What we need
is just the ordering, so we may not actually "digitize",
nor count it in our computation cost.
When we "determine" a vertex V_x at the index # for Z*, each
column # in every line Z_i is *determined*. That is, the Omega
number Z_ix (an element of the geodesic matrix Z) is extracted
from the undetermined part of the sequence Z_i and appended at
the tail of the determined part. V_x comes from the line Z_x
with an N-decimal number O_x, and the vertex label x indicates
the Omega number Z_ix for all i. If you view the determined
part as the finished submatrix z* of Z*, then the right-bottom
corner of the submatrix z* is always 0 because Z_ii=D_ii*W_i
and the distance D_ii=0 for all i. (At the start you will see
just one 0 at the left-top corner of Z*.)
At step (3) every O_is in each G_% are the same, but once the
operation proceed, they become various. The sets G_1,G_2,...,
G_m obtained at the step represents permutation groups Of G.
As a pair of similar vertices V_i and V_j of G does never have
equal Psi numbers P_i and P_j, so for two isomorphic graphs G
and G', the obtained canonical labelings exactly correspond
without far more permutations.
Thank Heaven! We've got a perfect canonical labeling of G.
Now that we have the Psi Proof, Kelly-Ulam conjecture is
just an exercise. Please wait for my next post.
BTW C1 was a lemma but not a corollary...
Michiro
-------- Original Message No.9637
--------
Subject: [theory-edge] A solution of Graph Isomorphism Problem on Geodesic Matrix
Date: Mon, 26 Apr 2004 07:38:11 -0000
From: "Michiro Nasu" michiro@...;
To: theory-edge@yahoogroups.com
Hi Vlad and all!
So long time no see.
I'm very happy to meet you again and to be able to announce
that we've found a solution of such a longstanding issue as
Graph Isomorphism Recognition Problem. As our life is short,
let's proceed now.
<A solution of Graph Isomorphism Problem on Geodesic Matrix>
Throughout this brief, we assume that every graph is finite,
connected and undirected.
D1: The distance d(u,v) between two vertices u and v in G(V,E)
is the minimum length of a path joining them if any; otherwise
d(u,v)=oo. A shortest u-v path is called a u-v geodesic. [1]
Let |V|=n; the distance matrix D of G is a nXn matrix like,
D_ij = d(V_i,V_j), where 0≤D_ij≤n-1.
D2: We give a weight W_i to each vertex V_i of G as,
W_i = SUM[i=1 to n]n^(D_ij-1), where n-1≤W_i≤n^(n-1).
D3: The geodesic matrix Z is a nXn matrix defined as follows.
Z_ij=D_ijW_j, where 0≤Z_ij≤n^n.
D4: The canonical geodesic matrix Z* is a nXn matrix obtained
from an arbitrary matrix Z by the following procedure.
(1) For all i, sort the line sequence {Z_i1,Z_i2,...,Z_in} in
decreasing/increasing order which you like; Let it be Z_i.
(2) Regarding Z_is as huge numbers, sort {Z_1,Z_2,...,Z_n} in
decreasing/increasing order which you like and get the
mapping M:{1,2,...,n}->{1,2,...,n}, where the former is
the vertex labeling of G and the latter is the ordering.
(3) If there exists a pair of vertices of the same order, then
try (1) and (2) again in the column direction and adjust
the mapping M by supplementing with the column ordering.
(4) Disregard the same orders if of both (2) and (3).
(5) Using the mapping M obtained as a permutation, transform
the matrix Z and get the canonical geodesic matrix Z*.
(6) Applying the mapping M, permute the distance matrix D
and the weight sequence {W_i}.
D5: We assign the Psi number P_i to each vertex of G using
the canonical geodesic matrix Z* like,
P_i=SUM[j=1 to n]Z*_ijX^(j-1):X=n^n, where 0<P_i<n^n^n.
D6: The Psi number P of G is defined as follows using P_i of
each vertex.
P=SUM[i=1 to n]P_iY^(i-1):Y=n^n^n, where 0<P<n^n^n^n.
T1: If the Psi numbers P and P' of connected, unlabeled and
undirected two finite graphs G and G' are equal, then G
and G' are isomorphic. The converse is also true.
C1: If the Psi numbers P and P' of graphs G and G' agree,
then the distance matrices D and D' agree too.
Proof of C1: From the assumption, P=P'. Straight from this,
P_i=P'_i for all 1≤i≤n
is derived by D6. Further by D5, it comes to
Z*_ij=Z*'_ij for all 1≤i,j≤n
and by D3, we obtain
D_ijW_j=D'_ijW'_j for all 1≤i,j≤n.
Assume that C1 does not hold. That is, assume D_lm≠D'_lm
for some pair of vertices (V_l,V_m) and (V'_l,V'_m) of
respectively G and G'. Then as D_lmW_m=D'_lmW'_m, it comes
to W_m≠W'_m, whereby D_imW_m=D'_imW'_m for all i yields
D_im≠D'_im and also D_mi≠D'_mi for all 0≤i≤n.
Since D_miW_i=D'_miW'_i for all i, it turns out W_i≠W'_i
for all i. It needs no more accounting for D_ij≠D'_ij
for all i,j due to them. Considering the definition, this
never happens in finite graphs, hence it can be said that
D_ij=D'_ij for all 0≤i,j≤n.
Consequently when the Psi numbers of graphs G and G' agree,
the distance matrices D and D' absolutely agree too. QED.
Proof of T1: From the definition, it is obvious that the
converse is true. Assume P=P', then we obtain D=D' by C1.
Apparently the distance matrix D includes the adjacency
matrix A of graph G with elements of D_ij=1. Therefore
as to the adjacency matrices A and A' of the graphs, A=A'.
And two graphs G and G' come to be isomorphic. QED.
T2: There exists a polynomial time algorithm for Graph
Isomorphism Recognition Problem.
Proof of T2: We regard that the complexity for generating
the distance matrix D is as O(n^3). [2] The costs for the
computation of {W_i}, {Z_ij}, {P_i} and P are at most
O(n^2). Transformation to the canonical geodesic matrix
Z* may be performed with O(n^2logn) adopting a suitable
sorting-algorithm. However as the scalar values treated
surely become huge numbers, we must see its cost.
Considering the largest number P<n^n^n^n, the unit cost
of bitwise computation of scalar values does not exceed
n^3logn, whereupon O(n^6logn) is a sufficient estimation
of the total complexity. Hence our theorem holds. QED.
Conclusion: We showed that it is possible to compute
the Psi number of G in polynomial time from the distance
matrix D. Further we proved that it is able to judge the
isomorphism of graphs by their Psi numbers. Apparently
Psi numbers {P_i} of each vertex divides vertices of G
into permutation groups. You may prefer to arrange our
algorithm to one which runs without computing Psi numbers.
With such a method, the total complexity may reduce to
O(n^5logn). We introduced the algorithm above from the
standpoint to establish a graph invariant as Psi numbers.
[1] Fred Buckley and Frank Harary, Distance in Graphs,
PP 10, Addison-Wesley Publishing Company, 1990.
[2] Alfred V. Aho, John E. Hopcroft and Jeffrey D.
Ullman, The Design and Analysis of Computer Algorithms,
PP 195-201, Addison-Wesley Publishing Company, 1974.
Michiro Nasu
Baba Laboratory; April 26, 2004
Email: babalabo@... (available at present)
TEL: (81)048-574-3623 (not available at present)
URL: http://www.aya.or.jp/~babalabo
ADDR: 1-3-72-2H Inari-Cho, Fukaya, Saitama Pre., Japan 366-0026
PS: Any comment, correction and suggestion would be
appreciated. As our telephone company disconnected
our line, now we have no direct access to Internet,
although we will try to keep in touch with the Net
on every opportunity. If you like, write me through
snail mail to the address above.
I greatly appreciate those affectionate owners and the
fellows of theory-edge and algorithm-forge for their
kind support for me. I would like to dedicate this
minute letter to my beloved teacher Koshin Isobe, who
taught me at my elementary school in a village, where
I was her pupil in the 1st, 2nd, 5th and 6th grades.