On the Diameter of the Set of Satisfying Assignments in Random Satisfiable k-CNF Formulas

It is known that random k-CNF formulas have a so-called satisfiability threshold at a density (namely, clause-variable ratio) of roughly 2kln2: at densities slightly below this threshold almost all k-CNF formulas are satisfiable, whereas slightly above this threshold almost no k-CNF formula is satisfiable. In the current work we consider satisfiable random formulas and inspect another parameter—the diameter of the solution space (that is, the maximal Hamming distance between a pair of satisfying assignments). It was previously shown that for all densities up to a density slightly below the satisfiability threshold the diameter is almost surely at least roughly n/2 (and n at much lower densities). At densities very much higher than the satisfiability threshold, the diameter is almost surely zero (a very dense satisfiable formula is expected to have only one satisfying assignment). In this paper we show that for all densities above a density that is slightly above the satisfiability threshold (more precisel...