TAIL BOUNDS FOR OCCUPANCY AND THE SATISFIABILITY THRESHOLD CONJECTURE

The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well-known conjecture on threshold phenomenon for the sa tisfiability problem. Consider random 3-SAT formulas with cn clauses o ver n variables, where each clause is chosen uniformly and independent ly from the space of all clauses of size 3. It has been conjectured th at there is a sharp threshold for satisfiability at c approximate to 4 .2. We provide a strong upper bound on the value of c, showing that fo r c > 4.758 a random 3-SAT formula is unsatisfiable with high probabil ity. This result is based on a structural property, possibly of indepe ndent interest, whose proof needs several applications of the occupanc y tail bounds. (C) 1995 John Wiley and Sons, Inc.