An asymptotic form of the Satisfiability Threshold Conjecture is true

You need to know: Supremum, infinum, big O and small o notations, boolean variables, their disjunction, conjunction, and negation, satisfiable and unsatisfiable formulas, basic probability theory: select objects from finite set uniformly, independently and with replacement.

Background: A k-clause is a disjunction of k Boolean variables, some of which may be negated. For a set $V_n$ of n Boolean variables, let $C_k(V_n)$ denote the set of all $2^kn^k$ possible k-clauses on $V_n$ . A random k-CNF formula $F_k(n, m)$ is formed by selecting uniformly, independently and with replacement m k-clauses from $C_k(V_n)$ and taking their conjunction. For each $k \geq 2$ , let $r_k$ be the supremum of r such that $F_k(n, rn)$ is satisfiable with probability tending to 1 as $n\to\infty$ .

The Theorem: On 4th September 2003, Dimitris Achlioptas and Yuval Peres submitted to the Journal of the AMS a paper in which they proved the existence of a sequence $\delta_k$ convergent to $0$ such that for all $k \geq 3$ , $r_k \geq 2^k \log 2 - (k + 1)\frac{\log 2}{2} - 1 - \delta_k.$

Short context: For each $k \geq 2$ , let $r^*_k$ be the infinum of r such that $F_k(n, rn)$ is unsatisfiable with probability tending to 1 as $n\to\infty$ . Obviously, $r_k \leq r_k^*$ . The Satisfiability Threshold Conjecture predicts that in fact $r_k = r_k^*$ for all $k\geq 3$ . Because it is known that $r_k^* \leq 2^k\log 2$ , the Theorem implies that $r_k = r_k^*(1-o(1))$ , which is an asymptotic form of the Satisfiability Threshold Conjecture.