Sharp thresholds and the partition function
Amin Coja‐Oghlan, Daniel Reichman · Journal of Physics Conference Series · 2013
Let Φ be a random k -CNF formula over n variables with clauses and let Z ( Φ ) be the number of satisfying assignments. Assume that k is sufficiently large and that r ≤ (1 − o k (1))2 k ln( k )/ k , where o k (1) denotes a certain function that tends to 0 as k gets large. We prove that in this case, Φ is satisfiable with probability 1 − O (1/ n ). Together with a recent result of Abbe and Montanari [arXiv:1006.3786], this implies that for such k,r the limit exists. The existence of this limit is related to the existence of a sharp threshold for satisfiability.