  It is known that random k-CNF formulas have a so-called satisfiability
threshold at a density (namely, clause-variable ratio) of roughly 2^k\ln 2: 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 precisely at ratio (1+ \eps)2^k \ln 2,
\eps=\eps(k) tending to 0 as k grows) the diameter is almost surely
O(k2^{-k}n). This shows that a relatively small change in the density around
the satisfiability threshold (a multiplicative (1 + \eps) factor), makes a
dramatic change in the diameter. This drop in the diameter cannot be attributed
to the fact that a larger fraction of the formulas is not satisfiable (and
hence have diameter 0), because the non-satisfiable formulas are excluded from
consideration by our conditioning that the formula is satisfiable.
