Ulam's Conjecture - proof
- From: slug@xxxxxxxxx
- Date: 8 Jun 2006 04:10:26 -0700
Hi,
Yesterday my friend Przemek Drochomirecki asked about status of Ulam's
Conjecture.
http://mathworld.wolfram.com/UlamsConjecture.html
I've decided to present my "proof" on the group.
I'm not sure if it's correct and I'm waiting for your oppinion.
Best Regards
Blazej Podsiadlo
---------------------------------------------------------------------------------------------------------------------------------
Ulam's Conjecture
Let graph G have n points vi and graph H have n points ui, where n>=3.
Then if for each i, the subgraphs Gi=G-vi and Hi=H-ui are
isomorphic, then the graphs G and H are isomorphic.
--------------------------------------------------------------------------------------------------------------------------------
Proof:
Each graph could be represented as Adjacency Matrix.
(http://mathworld.wolfram.com/AdjacencyMatrix.html)
Having some graph G:
for ex:
n=4
A B C D
-----------
A | 1 0 0 1
B | 1 0 1 0
C | 0 0 0 1
D | 1 1 0 0
we can add some modifications:
1. label all edges, but each one shall receive a different label:
in our case it would be:
A B C D
-----------
A | a 0 0 b
B | c 0 d 0
C | 0 0 0 e
D | f g 0 0
2. extend to fully connected graph
A B C D
-----------
A | a 1 1 b
B | c 1 d 1
C | 1 1 1 e
D | f g 1 1
3. label all new edges, but each one shall receive a different label:
A B C D
-----------
A | a h i b
B | c j d k
C | l m n e
D | f g o p
// above representation can be converted to Adjacency Matrix, be lab
function: lab: label->{0,1}
Let's do for all subgraphs of G and H.
If we know that:
Gi ~ Hi => there is some function fi: {v1,v2, ..., v(i-1), v(i+1), ...,
vn} -> {u1,u2, ..., u(i-1), u(i+1), ..., un}
in other words there is some map between vertices in G and H.
Our modification have to be made in some specific way:
edges (vj, vk) and (fi(vj), fi(vk)) will be labeled by the same label.
in out example:
A B C D
-----------
A | 1 0 0 1
B | 1 0 1 0
C | 0 0 0 1
D | 1 1 0 0
firstly lets do it for G-{A}
A B C D
-----------
A | 1 0 0 1
B | 1 j d k
C | 0 m n e
D | 1 g o p
then for G-{B}
A B C D
-----------
A | a 0 i b
B | 1 j d k
C | l m n e
D | f g o p
and for G-{C}
A B C D
-----------
A | a h i b
B | c j d k
C | l m n e
D | f g o p
in this way we've just received LABELED form of graph G
*// :) by the way; it's enough to do it for 3 subgraphs :)
Let's assume that we've made it for both G and H.
in result G and H have the same set of labels.
----------------------------------------------------------------------
Let's talk for a moment about Adjacency Matrix.
Each vertice in graph G is represented as raw and column in Adjacency
Matrix;
if we change of order of columns and rows simultaneously,
they will be still representing the same graph.
in our ex:
A B C D
-----------
A | a h i b
B | c j d k
C | l m n e
D | f g o p
and
D B C A
-----------
D | p h i f
B | k j d c
C | e m n l
A | b g o a
represent the same graph.
// labeled graph has n! of different forms; (sic!)
So graph G:
1 2 ... i ... n
----------------
1| X
2| X
..| X
i|XXXXXXXXXXXXXXX
..| X
n| X
can be represented as:
1 2 . i-1 i+1 . n i
---------------------
1 | X
2 | X
.. | X
i-1| Gi X
i+1| X
.. | X
n | X
i |XXXXXXXXXXXXXXXXXX
to do it, we are changing in places (i, i+1), then (i+1, i+2) and so on
...., (n-1, n);
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
Very important is that:
set of values in row/column is unchangeable!!!!
so if labels x, y and z are in the same row/column before
transformation they will be there after!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
---------------------------------------------
so let's take the everything together:
1. from assumption
Gi ~ Hi and fi: Gi->Hi
2. G and H are labeled
and they are in form:
1 2 . i-1 i+1 . n i
---------------------
1 | X
2 | X
.. | X
i-1| Hi X
i+1| X
.. | X
n | X
i |XXXXXXXXXXXXXXXXXX
let's extend function fi to fi':
fi'=fi u {i->i}
then
fi'(G) has form:
1 2 . i-1 i+1 . n i
---------------------
1 | Y
2 | Y
.. | Y
i-1| fi(Gi)=Hi Y
i+1| Y
.. | Y
n | Y
i |YYYYYYYYYYYYYYYYYY
fi(Gi)=Hi means that in this range {1, .., n}\{i} fi(Gi) and Hi have
the same values/labels (in sense of indexes H(1,1) = G(1,1))
At this moment we can say that:
if values on X/Y positions in G and H are the same then G ~ H
to show it, let's get some raw from G:
1 2 . i-1 i i+1 . n
---------------------
j | x y z
let's assume that in this raw are values {x, y, z},
y is on i-position, so in Gi they are only {x, z}.
what does it give us?
in fi'(G)
1 2 . i-1 i+1 . n i
---------------------
fi(j) | Y
this unknown value/label Y have to be y,
because:
!! set of values in row/column is unchangeable !!!
even more:
Gi ~ Hi => fi (j) = j'
so rows j and j' has the same values in range {1..n}\{i}.
in H
let's assume that in this raw are values {x, y, z},
y is on i-position, so in Hi thay are only {x, z}.
so fi'(G)[j', i] = H[j', i] that means
fi'(G) = H for all positions expect (i,i),
but we know that G and H have the same set of labels, and all expect
"this last one" are used,
so there is only one value and it's the same in both G and H
representation.
so G ~ H and fi' is the isomorphism function between them.
.
- Prev by Date: Re: [NT] How many (minimum) arithmetic progressions descompose a set?
- Next by Date: Re: Funny wrong proofs
- Previous by thread: Re: [NT] How many (minimum) arithmetic progressions descompose a set?
- Next by thread: exam results
- Index(es):
Relevant Pages
|
