"Phase change" of a purely mathematical system

Question

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?

Answer 1

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).

Answer 2

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.

Answer 3

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.