A Note on Random $k$-SAT for Moderately Growing $k$

Abstract

Consider a random instance $I$ of $k$-SAT with $n$ variables and $m$ clauses. Suppose that $\theta$, $c>0$ are any fixed real numbers. Let $k=k(n)\geq \big(\frac{1}{2}+\theta\big)\log_{2}n$. We prove that \begin{align}\nonumber\lim_{n\rightarrow\infty}Pr(I\ \mbox{is satifiable})=\left\{\begin{array}{cc}1&m\leq\big(1-\frac{c}{\sqrt{n}}\big)2^{k}n\ln 2 \\0&m\geq\big(1+\frac{c}{\sqrt{n}}\big)2^{k}n\ln 2. \\\end{array}\right.\end{align}