On the concentration of the number of solutions of random satisfiability formulas. Issue 3 (12th April 2013) - Abbe, Emmanuel; Montanari, Andrea
ABSTRACT Let Z(F) be the number of solutions of a random k‐satisfiability formula F with n variables and clause density α. Assume that the probability that F is unsatisfiable is <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9b5np" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />O(1/log(n)1+δ)</alternatives> for some <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9b5qs" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />δ>0</alternatives>. We show that (possibly excluding a countable set of "exceptional" α's) the number of solutions concentrates, i.e., there exists a non‐random function <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9b5tf" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />α↦ϕs(α)</alternatives> such that, for any <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9b5v0" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />ε>0</alternatives>, we have <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9b5zn" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Z(F)∈[2n(ϕs−ε), 2n(ϕs+ε)]</alternatives> with high probability. In particular, the assumption holds for all <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgh12v9b618" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />α<1</alternatives>, which proves the above concentration claim in the whole satisfiability regime of random 2‐SAT. We also extend these results to a broad class of constraint satisfaction problems. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 362–382, 2014