The problem of determining the unsatisfiability threshold for random 3-SAT formulas consists in determining the clause to
variable ratio that marks the (experimentally observed) abrupt change from almost surely satisfiable formulas to almost surely
unsatisfiable. Up to now, there have been rigorously established increasingly better lower and upper bounds to the actual
threshold value. An upper bound of 4.506 was announced by Dubois et al. in 1999 but, to the best of our knowledge, no complete
proof has been made available from the authors yet. We consider the problem of bounding the threshold value from above using
methods that, we believe, are of interest on their own right. More specifically, we explain how the method of local maximum satisfying truth assignments can be combined withresu lts for coupon collector’s probabilities in order to achieve an upper bound for the unsatisfiability
threshold less than 4.571. Thus, we improve over the best, with an available complete proof, previous upper bound, which was
4.596. In order to obtain this value, we also establish a bound on the q-binomial coe.cients (a generalization of the binomial coefficients) which may be of independent interest.
Researchsu pported by EPSRC grant GR/L/77089.