The Scaling Window of the 2-SAT Transition

Béla Bollobás, Christian Borgs, Jennifer T. Chayes, Jeong Han Kim, David B. Wilson

We consider the random 2-satisfiability problem, in which each instance is a formula which is the conjunction of $m$ clauses of the form $x\vee y$, chosen uniformly at random from among all 2-clauses on $n$ Boolean variables and their negations. As $m$ and $n$ tend to infinity in the fixed ratio $\alpha = m/n$, the problem is known to have a phase transition at $\alpha_c = 1$, below which the probability that the formula is satisfiable tends to one and above which it tends to zero. We determine the finite-size scaling about this transition, namely the window $W(n,\delta) = (\alpha_-(n,\delta), \alpha_+(n,\delta))$ such that the probability of satisfiability is greater than $1-\delta$ for $\alpha < \alpha_-$ and it is less than $\delta$ for $\alpha > \alpha_+$. We show $$ W(n,\delta)=(1-\Theta(n^{-1/3}), 1+\Theta(n^{-1/3})), $$ where the constants implicit in $\Theta$ depend on $\delta$. We also determine the rates at which the probability of satisfiability approaches one and zero at the boundaries of the window. Namely, for $m=(1+\varepsilon)n$, where $\varepsilon$ may depend on $n$ as long as $|\varepsilon|$ is sufficiently small and $|\varepsilon| n^{1/3}$ is sufficiently large, we show that the probability of satisfiability decays like $ \exp\left(-\Theta\left({n\varepsilon^3}\right)\right) $ above threshold, and goes to one like $ 1-\Theta\left( n^{-1}|\varepsilon|^{-3}\right) $ below threshold. We prove these results by defining an order parameter for the transition and establishing its scaling behavior in $n$ both inside and outside the window. As a corollary, we prove that the 2-SAT phase transition is continuous with an order parameter critical exponent of 1. This is the first complete analysis of finite-size scaling in a constraint satisfaction problem.

Random Structures and Algorithms, to appear.
DVI version
PostScript version PDF version