Timeline for answer to Joshua Lederberg's influence on graph theory by Brendan McKay
Current License: CC BY-SA 4.0
Post Revisions
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 9 at 3:15 | comment | added | Brendan McKay | @TimothyChow The number of Eulerian orientations is one of the Tutte polynomial evaluations that is #P-hard, so testing a bound is NP-hard. This is used in a theory of physical lattices like water ice. I think there are other examples, like Ising models. Of course all such things are approximations of physical reality. Anyway the point is that being NP-hard is not necessarily an impediment to physical importance, though I don't know a clear-cut example of an NP-complete existence problem that fits the bill. | |
| Mar 9 at 0:12 | history | edited | Brendan McKay | CC BY-SA 4.0 |
added 40 characters in body
|
| Mar 8 at 9:40 | history | edited | Brendan McKay | CC BY-SA 4.0 |
added 17 characters in body
|
| Mar 8 at 5:46 | history | edited | Brendan McKay | CC BY-SA 4.0 |
added 15 characters in body
|
| Mar 8 at 5:11 | history | edited | Brendan McKay | CC BY-SA 4.0 |
added 189 characters in body
|
| Mar 8 at 5:04 | history | edited | Brendan McKay | CC BY-SA 4.0 |
added 189 characters in body
|
| Mar 8 at 4:56 | history | edited | Brendan McKay | CC BY-SA 4.0 |
added 189 characters in body
|
| Feb 25 at 12:26 | comment | added | Brendan McKay | @GordonRoyle In that paper he is on about graph generation, and one way to generate cubic graphs is to consider them as chords on a hamiltonian cycle. Then he says they rely on there being such a cycle, presumably because the known counterexamples are much bigger than the range of their computations. So I was not correct to say that hamiltonian cycles are unimportant for DENDRAL, though I still maintain that that have no have no chemical application in the sense of there not being a chemical behaviour of a molecule meaningfully related to whether it has a hamiltonian cycle. | |
| Feb 25 at 12:11 | history | edited | Brendan McKay | CC BY-SA 4.0 |
added 1 character in body
|
| Feb 25 at 2:25 | comment | added | Gordon Royle | This raises the question of why Lederberg was interested in Hamilton cycles? In the paper oeis.org/A000602/a000602_10.pdf about DENDRAL (note the two Ds) he devotes quite a bit of time talking about Hamilton cycles. He also uses the term gauche graph for a non-planar graph, which obviously did not catch on. | |
| Feb 24 at 12:10 | comment | added | Timothy Chow | Thanks for mentioning this. I was wondering how an NP-complete property could be physically or chemically important. | |
| Feb 24 at 8:08 | history | answered | Brendan McKay | CC BY-SA 4.0 |