Abstract:
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\to\infty$, then $r\ge8.09$. This sharpens the known lower bound $r\ge7.91$.