Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

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.

share|improve this question
1  
similar question was posted here cstheory.stackexchange.com/questions/12786/… –  DurgaDatta Oct 8 '12 at 4:53

2 Answers 2

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.