A remark on random 2-SAT

AbstractIt is known that almost all 2-CNF-formulas where the number of clauses is n(1−ϵ),ϵ>0 a constant, n the number of variables are satisfiable. For n(1+ϵ) clauses they are known to be unsatisfiable. We strengthen the first result and show that for each ϵ=ϵ(n)⩾(1/(lnn))1/2 (hence ϵ may approach 0) the first of the results above still holds