## The Scaling Window of the 2-SAT Transition

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.

math.CO/9909031

DVI version

PostScript version
PDF version