On the concentration of multivariate polynomials with small expectation

Let t1, …, tn be independent, but not necessarily identical, 0, 1 random variables. We prove a general large deviation bound for multivariate polynomials (in t1, …, tn) with small expectation order O (polylog (n) ). Few applications in random graphs and combinatorial number theory will be discussed. Our result is closely related to a classical result of Janson Random Struct Algorithms 1 (1990), 221–230. Both of them can be applied in similar situations. On the other hand, our result is symmetric, while Janson's inequality only deals with the lower tail probability. © 2000 John Wiley & Sons, Inc. Random Struct. Alg. , 16: 344–363, 2000