Timeline for answer to Joshua Lederberg's influence on graph theory by Gordon Royle
Current License: CC BY-SA 4.0
Post Revisions
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 2 at 1:41 | comment | added | Timothy Chow | Update: It seems that Mechanization of Inductive Inference in Organic Chemistry was reprinted in a book. As I suspected, there is no Section 5 entitled "Topological Mapping," let alone any mention of non-Hamiltonian graphs. | |
| Mar 1 at 13:04 | comment | added | Timothy Chow | @ManfredWeis That is AI gossip for sure. This report says that Memo 54 is Mechanization of Inductive Inference in Organic Chemistry by Lederberg and Feigenbaum, not some weird title with "computer consciousness." I haven't been able to find the latter paper online, but my guess is that its contents are similar to DENDRAL and Meta-DENDRAL: Their Applications Dimension and that it doesn't contain the quoted passage. | |
| Mar 1 at 12:37 | comment | added | Manfred Weis | @TimothyChow I have the following: "In his 1967 paper, "Systematics of Organic Molecules, Graph Theory and Computer Consciousness" (Stanford Artificial Intelligence Memo No. 54), Lederberg introduces this specific construction in Section 5: Topological Mapping. The description of the 9-vertex "fragment" and its non-Hamiltonian properties begins with the following passage: "If we relax the requirement of 3-connectivity (...), non-Hamiltonian trivalent graphs can be found with as few as 18 vertices. The construction of such a graph is based on a 9-vertex fragment." I hope that helps | |
| Mar 1 at 11:03 | comment | added | Timothy Chow | @ManfredWeis I am still confused about how you know that Lederberg found a 9-vertex gadget and combined two of them to generate a planar cubic non-Hamiltonian biconnected graph. Did you read this claim in a NASA report? If not, where? | |
| Mar 1 at 6:46 | comment | added | Manfred Weis | @TimothyChow as I see it, Lederberg could ( ot maybe must ) have encountered such a graph when he put up a list of all convex polyhedral Hamilton cubic graphs up to order 18 but may not have considered it as important enough to mention explicitly. Regarding AI I am very skeptical about what is claimed; I had a case where they disagreed on the Hamiltonicity of a small graph | |
| Mar 1 at 3:12 | comment | added | Timothy Chow | @ManfredWeis When you say that you "know" this, is "AI gossip" the only source for this claim? If so, then an obvious possibility is that Lederberg never constructed such a thing. For what it's worth, if I ask Perplexity, "Did Joshua Lederberg construct a cubic non-Hamiltonian graph on 18 vertices?" it says "No." So there's some AI gossip to the contrary. | |
| Mar 1 at 1:49 | comment | added | Manfred Weis | @TimothyChow I only know that Lederberg found a 9-vertex gadget that allowed him to construct non-Hamiltonian cubic graphs and, that by combining two of them he could generate a planar cubic non-Hamiltonian biconnected graph, but despite intensive search I could not locate an explicit definition in the NASA reports that I have been directed to by online search, also by AI. "gossip" says that the 9-vertex gadget is similar to the Tutte fragment. | |
| Feb 28 at 21:17 | comment | added | Timothy Chow | @ManfredWeis I'm still curious as to what you know about the Lederberg graph and what your sources are. | |
| Feb 25 at 15:30 | comment | added | Manfred Weis | I suspect that it is not the Lederberg graph and if that is the case, your graph would be interesting because it would have taken about 60 years until a different graph with the same properties has been found | |
| Feb 24 at 6:16 | history | answered | Gordon Royle | CC BY-SA 4.0 |