@techreport{bollobas1999the,
author = {Bollobas, Bela and Borgs, Christian and Chayes, Jennifer and Kim, Jeong Han and Wilson, David},
title = {The Scaling Window of the 2-SAT Transition},
year = {1999},
month = {September},
abstract = {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&#150 δ for ∝ ∝ +. We show W ( n , δ) = (1 &#150 Θ ( 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 ( &#150 Θ ( n ε 3 )) above the window, and goes to one like 1 &#150 Θ ( 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.},
url = {http://approjects.co.za/?big=en-us/research/publication/the-scaling-window-of-the-2-sat-transition/},
pages = {51},
number = {MSR-TR-99-41},
}