2000/05/31 by David B. Wilson
Computer Science · Mathematics · #Advanced Algebra and Logic #Constraint Satisfaction and Optimization #Critical exponent #Exponent #Formal Methods in Verification #Random element #Random function #Random graph #Random variable #Satisfiability #Simple (philosophy) #math.PR
paper · pdf · doi:10.1002/rsa.10050
published as Random Structures and Algorithms, 21(2):182--195, 2002 · 11 pages. v2 has revised introduction and updated references
arxiv created 2002/07/03 · openalex publication_date 2002/08/07 · arxiv updated 2012/06/19 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
Abstract 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 ν = ν k (the smaller the value of ν 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. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 182–195, 2002