Kelly-Ulam Conjecture and Graph Numbering

--- Record of Our Failed Research Work ---


Baba Laboratory
Michiro Nasu

-------- Original Message No.5601 --------
Subject:
[theory-edge] Kelly-Ulam Conjecture and Graph Numbering
Date: Tue, 11 Jun 2002 16:02:35 +0900
From: "Michiro Nasu" michiro@...;
To: theory-edge@yahoogroups.com

Hi Vlad and all!

I uploaded a short paper (17 21 pages) regarding the Kelly-Ulam Conjecture to the archive of algorithm-forge. http://groups.yahoo.com/group/algorithm-forge/files/K-U.pdf

eventually we failed to prove K-U. however we succeeded to prove the edge-version K-U. this work is due to your suggestion in the first place. I am grateful to you for that. the paper consists of 8 sections but almost parts of the paper is the record of our failures.

1. Introduction
2. Psi Numbering System
3. Psi Number Theorem
4. Kelly-Ulam Conjecture
5. K-U Counterexamples
6. Edge-Reconstruction Conjecture
7. Edge-Version Kelly-Ulam Theorem
8. Conclusion

at section 3, we introduce several basic theorems for Psi numbers. we fail at section 4 to prove K-U conjecture and at section 5, we consider the K-U counterexample. at section 6, we fail again to prove the edge-version K-U. finally at section 7, we show that there exist no counterexamples for edge-version K-U. we introduce 7 different Psi numbers throughout the paper.

(1)labeled Psi number
(2)unlabeled Psi number
(3)natural Psi number
(4)supernatural Psi number
(5)edge-labeled Psi number
(6)edge-deck Psi number
(7)edge-fragment-deck Psi number

Psi numbers (1)-(4) are for the vertex-version K-U and (5)-(7) are numbers for the edge-version K-U. in general the former is simpler than the latter. to derive the final result of edge-version K-U theorem, we need not (1)-(4). so you may pass over the sections 3-5. Currently the proof for the theorem 6.1 is incomplete but I believe that it is not the crucial flaw of the paper for the validity of the theorem/definition of the Psi number is of no doubt. we neglect it as it is just a bit lengthy and annoying.

please take a look at the paper and let me know anything that you noticed. any questions/suggestions/refutations would be greatly appreciated.

regards,
Michiro Nasu
email: nasukun@...
URL: http://www.aya.or.jp/~babalabo/

JUMP to the paper: Kelly-Ulam Conjecture and Graph Numbering