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 ~ 4.2. The sharpness of this transition is characterized by a critical exponent, sometimes called nu=nu_k. An article in the journal Science reported a detailed study of nu, in which it was estimated that nu_3=1.5+-0.1, nu_4=1.25+-0.05, nu_5=1.1+-0.05, nu_6=1.05+-0.05, and nu_k -> 1 as k -> infinity. Similar estimates are given in a number of other articles as well. 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 standard ensembles of random k-SAT formulas: m clauses selected uniformly at random (either with or without 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.
Copyright. All Rights Reserved.