The story with sharp thresholds for random constraint satisfaction problems somewhat fits into this picture. In the random k-SAT problem with $n$ Boolean variables, one includes each of the $2^k \binom{n}{k}$ potential clauses independently with probability $p$, where $p$ is chosen so that the expected clause density (number of clauses over number of variables) is some fixed constant $\alpha$.

It is very widely believed that for each $k$ there is a critical density $\alpha_k$ such that for all $\epsilon > 0$ the following holds:

- if $\alpha \leq (1-\epsilon)\alpha_k$ then the resulting formula is satisfiable with probability $1-o(1)$;
- if $\alpha \geq (1+\epsilon)\alpha_k$ then the resulting formula is unsatisfiable with probability $1-o(1)$.

However in general the existence of this $\alpha_k$ is unknown. Friedgut's Theorem [Fri99] comes extremely close to showing that $\alpha_k$ exists. His result implies that for each $k$ the above statement is true for a *sequence* of real numbers $\alpha_k(n)$ depending on the number of variables. (It is also easy to show that $\alpha_k(n)$ is bounded in the range $[1,2^k \ln 2]$ for all $n$.) It's utterly inconceivable that this sequence could oscillate, rather than tend to a limit, but in general this hasn't been proven.

For each $k$, the value of $\alpha_k$ is "known", via sophisticated heuristics from statistical physics [MPZ02, MMZ06]. In this sense, we sort of have an example answering Sylvain's question.

In a recent major breakthrough, Ding, Sly, and Sun rigorously established the physics prediction for $\alpha_k$ for all sufficiently large $k$. It is worth mentioning that this does not obviate the need for Friedgut's Theorem; by virtue of that theorem, it was enough for Ding--Sly--Sun to show that

- if $\alpha < \alpha_k$, the random k-SAT formula is satisfiable with probability bounded away from 0.

[Fri99] *Ehud Friedgut*, **Sharp thresholds of graph properties, and the $k$-sat problem**, *J. Amer. Math. Soc.* **12** (1999), no. 4, 1017--1054.

[MMZ06] *Stephan Mertens, Marc Mézard, and Riccardo Zecchina*, **Threshold values of random $K$-SAT from the cavity method**, *Random Structures Algorithms* **28** (2006), no. 3, 340--373.