On a problem of Spencer (Q1072210): Difference between revisions

Let \(X_ 1,...,X_ n\) be events in a probability space. Let \(\rho_ i\) be the probability that \(X_ i\) occurs. Let \(\rho\) be the probability that none of the \(X_ i\) occur. Let G be a graph on [n] so that for \(1\leq i\leq n\) \(X_ i\) is independent of \(\{X_ j| (i,j)\not\in G\}\). Let f(d) be the sup of those x such that if \(\rho_ 1,...,\rho_ n\leq x\) and G has maximum degree \(\leq d\) then \(\rho >0\). We show \(f(1)=1/2\), \(f(d)=(d-1)^{d-1}d^{-d}\) for \(d\geq 2\). Hence \(\lim_{d\to \infty}df(d)=1/e\). This answers a question posed by \textit{J. Spencer} in Discrete Math. 20(1977), 69-76 (1978; Zbl 0375.05033). We also find a sharp bound for \(\rho\) in terms of the \(\rho_ i\) and G.