The Scaling Window of the 2-SAT Transition

We consider the random 2-satisfiability problem, in which each instance is a formula that is the conjunction of m clauses of the form x ∧ 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 ratio m/n → ∝ , the problem is known to have a phase transition at ∝ 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 scaling of the maximal window W(n, δ ) = (∝_(n, δ ), ∝ + (n, δ)) such that the probability of satisfiability is greater than 1– δ for ∝ ∝ +. We show W ( n , δ) = (1 – Θ ( n -1/3 ), 1 + Θ ( n -1/3 )), where the constants implicit in Θ depend on δ . 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 + ε ) n , where ε may depend on n as long as | ε | n 1/3 is sufficiently large, we show the probability of satisfiability decays like exp ( – Θ ( n ε 3 )) above the window, and goes to one like 1 – Θ ( n -1 | ε| -3 ) below the window. 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. Using this order parameter, we prove that the 2-SAT phase transition is continuous with an order parameter critical exponent of 1. We also determine the values of two other critical exponents, showing that the exponents of 2-SAT are identical to those of the random graph.