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

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 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)∈[2n(ϕs−ε),2n(ϕ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