Structure of random r-SAT below the pure literal threshold

Alexander D. Scott, Gregory B. Sorkin

It is well known that there is a sharp density threshold for a random $r$-SAT formula to be satisfiable, and a similar, smaller, threshold for it to be satisfied by the pure litera…