Front for the arXiv
Fri, 9 May 2008
Front > math > PR > 0803 > arXiv:0803.3285
search | register | submit
journals | about | iFAQ

arXiv:0803.3285

[pdf] [ps] [dvi] [src] [arxiv]

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

[help e-mail] - for questions or comments about the Front
arXiv contact page - for questions about downloading and submitting e-prints