Kelly-Ulam Conjecture and Graph Numbering
--- Record of Our Failed Research Work ---
-------- 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