Mathematical Mozu Song

Index of the Contents

It contains the following articles, most of them are excerpt from theory-edge/algorithm-forge. →I guess that they are all in checkmate status in some sense. (2006-09-28)

1. An Infinitely Palindromic Square-Free Sequence: Our latest work. I discovered an infinitely square free sequence named "Mathematical Mozu Song", as well I found a morphism for Rivest sequence. The origin of the research was some consideration of perpetual checkmate status of chess/shogi-game.

2. An Efficient Factoring Algorithm by Repunit Number Method : It was a work around spring in 2005. The origin was my answer to a schoolgirl saying that multiplication and division are essentially equivalent. To confirm it myself I buried in the depth of the investigation on and on. We established an extension of Euler's totient function independently, which we call u-length function or Psi function.

3. A Polynomial Time Solution for Plesnik's Problem by Irrigation Canal Method : Plesnik showed that Hamiltonian problem is NP-Complete even if it is bounded to directed graphs of degree two. It is said to be the ultimate Hamiltonian problem. We attacked the line and gained pretty remarkable progress. We found that in this circumstance the problem turns to a kind of Eulerian cycle problem, but may head towards somewhat topological direction.

4. A Polynomial Time Algorithm for Matrix & Graph Isomorphism : We extended Graph Isomorphism to Matrix Isomorphism in course of nature. We tried a canonical graph numbering and eventually came up with the concept of "Critical State Experiment", a kind of partitioning but really an amazing method. In parallel we built an Isomorphism program named ELSIE. (Narcissus/Narkissos is another thread of Isomorphism experiment.)

5. The Final Solution for Kelly-Ulam Conjecture : A brief proof for Kelly-Ulam Conjecture. The article below is the record of our failure for the problem, and if you read the article, you would understand how K-U problem is tough and profound. However the final solution became in a sense very simple one. It uses a huge number for canonical labeling.

6. Kelly-Ulam Conjecture and Graph Numbering : We actually failed to prove vertex version K-U, but succeeded for edge version. This work was done summer in 2002. We used here the name of Psi numbers but this is quite different from the Psi function for factoring (No.2 article).

7. Strongly Intransitive Graphs and the Perfect Graph Conjecture : We attacked transitive graphs [alternatively comparability graphs]. I forgot the origin for now. It was a terribly steep mountain with ferocious blizzard. at the top of the hill we find a flag Gallai planted. We barely put them into an article. We intended to attack Berge's perfect graph conjecture from the perspective, but beyond our reach as you know well.→ We deviced a tool called OZ-cycle(odd zigzag cycle), a twisted pair of spanning cycles of odd order, one is normal and the other is anti-cycle(complemented one). We proved a theorem that a graph G is intransitive if and only if G has no OZ-cycles, which was also discovered by Ghouilla-Houri in 1962, and Gilmore and Hoffman in 1964 independently.

8. Universal Turing Machine with Active Graph: This is the most notorious trouble on me. I almost/actually kicked out from the list. By good fortune Lasse interacted with me till the last. I designed an Universal Turing Machine and reduced it to SAT in the similar way that Cook used in his paper. Thus I accept the theory and made an official apology to the audience. After math: I considered that if Cook is a pocket picker then I must be a holdup.

9. HCP to SAT Conversion Cubic Time Algorithm: A byproduct of Ariadne100 development. We wrote an O(n^3) time algorithm for HCP to SAT conversion. As far as we know this is the fastest transformation algorithm from HCP(Hamiltonian Circuit Problem) to SAT(Boolean Satisfiability Problem) ever known. This short article (including a pseudo C program) is mostly an excerpt from the article below but slightly rewritten today for better understanding.

10. Ariadne100 Hamiltonian Circuit Experiment Program: Hamiltonian problem is my best favorite problem. The base of Ariadne100 is Graph Contracting and Timing chart method. Graph Contracting Method is described in the article below, which makes it enable to search recursively. This program was publicly delivered to some extent. → A very few people know what is Timing Chart. But at least S. Busygin invented it independently and adopted for SAT01 Solver.

Ariadne100 has one more peculiar feature, ie speculation. When it encounters a hard problem, then it makes several random short trials and choices the most prospective course. The base of the forecast is the Timing Chart as it gives us some information as regard to their future.

11. Regarding the Solution of Hamiltonian Circuit Problem using Experimental Graphs or the Method of How to Control One's Fortune: My first and incomplete article. I almost abandoned this paper, but published it anyway. It is sure that this premature draft was circulated in some range, overly worldwide. Once the name was put in a wiki-page next to the name of Wiliam Rowan Hamilton. If you doubt it, check the URL then you will find the remainder. http://fixedreference.org/en/20040424/wikipedia/Hamiltonian_path

Ten years have passed since I began mathematics. Now I reached at my 60 years. Surely it is very hard to control one's fortune. But my fortune is really a [bunch of] good friends. I greatly appreciate you all my virtual colleagues here.

M.N.
Sep. 26, 2006
mailto:babalabo@...
http://babalabo.blogdns.com/labo/
http://www.aya.or.jp/~babalabo/
http://www.geocities.com/babalabo/

Source:http://tech.groups.yahoo.com/group/theory-edge/message/12425

PS: added a few lines at #7 and #9. MN(2006-09-27)
PS: inserted an article "HCP to SAT Conversion Cubic Time Algorithm" at #9 and renumbered. MN(2006-09-29)