Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Every so often I hear people talking about "phase transitions" in purely mathematical or computer-science contexts, where there is no physics in sight. Today, for example, I heard some people talking about "phase transitions" when coloring edges in random graphs.

Is this just a simple reuse of the physics term, or is there a more general mathematical concept of a "phase change", of which physical phase changes are one instance? If so, what are some illustrative purely mathematical/nonphysical examples?

share|improve this question
    
I think there is a connection via statistical mechanics, Ising models, percolation theory, etc. My naive impression is that there is a mathematical concept of phase transition (roughly speaking when the behavior of a system depends discontinuously on some continuous parameter) of which physical phase transitions are an instance. –  Qiaochu Yuan Apr 24 '12 at 22:27
    
@QiaochuYuan Yeah, I think so too. I'm hoping someone knowledgeable about those fields could elaborate or give references on how to make the connection precise. –  Nick Alger Apr 24 '12 at 23:40

3 Answers 3

up vote 2 down vote accepted
+100

In Where the Really Hard Problems Are the concept of phase change in NP complete problems is discussed. It has the sense of a narrow boundary region from physics, but not entirely the sense of fixing things (like the temperature of a melting solution).

share|improve this answer
    
Ahh, that seems to contain a discussion of two of the examples that I've run across. It seems like more of an analogy than a direct correspondence though. There's no analogs of "entropy", "temperature", "free energy", or other quantities you would expect in thermodynamic systems. :( –  Nick Alger Apr 23 '12 at 22:26

I don't have the reputation to post a comment but ...

"Where the Really Hard Problems Are" makes a critical error relative to where the really hard problems are.

Problems in the narrow "boundary region" can be easily moved to the "over constrained region" by adding n new variables and 6n new clauses. These clauses need only involve those n varaibles, but need not. This is a polynomial transformation that has no effect on the solution to the original problem.

I would suggest that using "phase change" in this context might be improper.

share|improve this answer

The most common example I can think of is in random graph theory, which serves as the mathematical model of all sorts of networks, where an abrupt transition occurs between the disconnected regime and the connected regime when the probability of the existence of an edge between two nodes exceeds $\log n/n$, where $n$ is the number of nodes (vertices). If calling that a "phase change" is an abuse, then so be it.

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.