Many intuitive knot invariants including Jones' polynomial are inspired by statistical mechanics. Further profound connections have been explored between knot theory and statistical mechanics. I was looking if similar connection have been found for graph invariants. I am interested to know if any attempts have been made form statistical physics community to solve graph isomorphism problem. Since both knot problem and graph isomorphism are problem about testing structural equivalence there might be connection between them.
Tell me more
×
Physics Stack Exchange is a question and answer site for
active researchers, academics and students of physics. It's 100% free, no registration required.
|
|
|||||
|
|
Efficient graph isomorphism testing requires very simple invariants, and most graphs can be distinguished with very simple counts (number of vertices, distributions of degrees of vertices, edges, etc.) In contrast, distinguishing knots is something much more involved. Thus I think that there are no relations between graph isomorphism and statistical mechanics. |
|||
|
|
|
Polynomial invariants like the Tutte polynomial can be realised as the partition function of a certain spin-model on the graph. Questions about zeros of this Tutte polynomial are related to the existence of phase transitions, but beyond this, I think that the questions asked about these objects by physicists and mathematicians are very different. |
|||
|
|
