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 for some . We show that (possibly excluding a countable set of exceptional ?'s) the number of solutions concentrates, i.e., there exists a non-random function such that, for any , we have with high probability. In particular, the assumption holds for all , 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, 362382, 2014
concentration satisfiability constraint satisfaction problems counting sharp threshold interpolation method