A lower bound for the 4-satisfiability threshold
F. Yu. Vorobyev · Discrete Mathematics and Applications · 2007
Let F k ( n , m ) be a random k -conjunctive normal form obtained by selecting uniformly and independently m out of all possible k -clauses on n variables. We prove that if F 4 ( n, rn ) is unsatisfiable with probability tending to one as n → ∞, then r ≥ 8.09. This sharpens the known lower bound r ≥ 7.91.