## On the critical exponents of random *k*-SAT

There has been much recent interest in the satisfiability of random
Boolean formulas. A random *k*-SAT formula is the conjunction of *m*
random clauses, each of which is the disjunction of *k* literals (a
variable or its negation). It is known that when the number of
variables *n* is large, there is a sharp transition from
satisfiability to unsatisfiability; in the case of 2-SAT this
happens when *m/n*→ 1, for 3-SAT the critical ratio is
thought to be *m/n*\approx 4.2. The sharpness of this transition is
characterized by a critical exponent, sometimes called ν=ν_{k}
(the smaller the value of $\nu$ the sharper the transition).
Experiments have suggested that ν_{3}=1.5± 0.1,
ν_{4}=1.25±0.05, ν_{5}=1.1±0.05, ν_{6}=1.05±0.05, and heuristics have suggested that
ν_{k}→ 1 as *k*→∞.
We give here a simple proof
that each of these exponents is at least 2 (provided the exponent is
well-defined). This result holds for each of the three standard
ensembles of random *k*-SAT formulas: *m* clauses selected uniformly
at random without replacement, *m* clauses selected uniformly at
random with replacement, and each clause selected with probability
*p* independent of the other clauses. We also obtain similar results
for *q*-colorability and the appearance of a *q*-core in a random
graph.
PostScript version