It is well known that many NP-complete problems exhibit phase transition. I am interested here in phase transition with respect to containment in the language, rather than the hardness of the input, relative to an algorithm.
To make the concept unambiguous, let us formally define it as follows. A language $L$ exhibits phase transition (with respect to containment), if
There is an order parameter $r(x)$, which is a polynomial time computable, real valued function of the instance.
There is a threshold $t$. It is either a real constant, or it may possibly depend on $n=|x|$, that is, $t=t(n)$.
For almost every $x$ with $r(x)<t$, we have $x\in L$. (Almost every means here: all but vanishingly many, that is, the proportion approaches 1, as $n\rightarrow\infty$).
For almost every $x$ with $r(x)>t$, we have $x\notin L$.
For almost every $x$, it holds that $r(x)\neq t$. (That is, the transitional region is "narrow.")
Many natural NP-complete problems exhibit phase transition in this sense. Examples are numerous variants of SAT, all monotone graph properties, various constraint satisfaction problems, and probably many others.
Question: Which are some "nice" exceptions? Is there a natural NP-complete problem, which (probably) does not have a phase transition in the above sense?