On a problem of spencer |
| |
Authors: | J. B. Shearer |
| |
Affiliation: | (1) Department of Mathematics, U. C. Berkeley, 94720 Berkeley, CA, USA;(2) Present address: IBM Research, P.O.B. 218, 10598 Yorktown Heights, NY, USA |
| |
Abstract: | LetX 1, ...,X n be events in a probability space. Let ϱi be the probabilityX i occurs. Let ϱ be the probability that none of theX i occur. LetG be a graph on [n] so that for 1 ≦i≦n X i is independent of ≈X j ‖(i, j)∉G≈. Letf(d) be the sup of thosex such that if ϱ1, ..., ϱ n ≦x andG has maximum degree ≦d then ϱ>0. We showf(1)=1/2,f(d)=(d−1) d−1 d −d ford≧2. Hence df(d)=1/e. This answers a question posed by Spencer in [2]. We also find a sharp bound for ϱ in terms of the ϱ i andG. |
| |
Keywords: | 60 C 05 05 C 99 |
本文献已被 SpringerLink 等数据库收录! |
|