{
  "id": "math/0005136",
  "version": "v2",
  "published": "2000-05-13T15:44:27.000Z",
  "updated": "2002-07-03T05:41:12.000Z",
  "title": "On the critical exponents of random k-SAT",
  "authors": [
    "David B. Wilson"
  ],
  "comment": "11 pages. v2 has revised introduction and updated references",
  "journal": "Random Structures and Algorithms, 21(2):182--195, 2002",
  "doi": "10.1002/rsa.10050",
  "categories": [
    "math.PR"
  ],
  "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 \\nu=\\nu_k (the smaller the value of \\nu the sharper the transition). Experiments have suggested 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 heuristics have suggested that \\nu_k --> 1 as k --> infinity. 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.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2002-07-03T05:41:12.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "critical exponent",
      "random k-sat formula",
      "random boolean formulas",
      "simple proof"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2000math......5136W"
    }
  }
}