On the concentration of the number of solutions of random satisfiability formulas

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 O ( 1 / log ( n ) 1 + δ ) for some δ > 0 . We show that (possibly excluding a countable set of “exceptional” α 's) the number of solutions concentrates, i.e., there exists a non‐random function α ↦ ϕ s ( α ) such that, for any ε > 0 , we have Z ( F ) ∈ [ 2 n ( ϕ s − ε ) , 2 n ( ϕ s + ε ) ] with high probability. In particular, the assumption holds for all α < 1 , 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