![[arxiv]](/images/buttons/arxiv.png)
Title: Branching Process approach for 2-SAT thresholds
Authors: Elchanan Mossel (UC Berkeley), Arnab Sen (UC Berkeley)
Categories: math.PR Probability Theory
Comments: 14 pages, no figure
MSC: 60C05, 65C50
Abstract: It is well known that, as $n$ tends to infinity, the probability of
satisfiability for a random 2-SAT formula on $n$ variables, where each clause
occurs independently with probability $\alpha/2n$, exhibits a sharp threshold
at $\alpha=1$. We provide a simple conceptual proof of this fact based on
branching process arguments. We also study a generalized 2-SAT model in which
each clause occurs independently but with probability $\alpha_i/2n$ where $i
\in {0,1,2 }$ is the number of positive literals in that clause. We use
2-type branching process arguments to determine the satisfiability threshold
for this model in terms of the maximum eigenvalue of the branching matrix.
Owner: Arnab Sen
Version 1: Sat, 22 Mar 2008 18:05:50 GMT