zbMATH — the first resource for mathematics

On a problem of Spencer. (English) Zbl 0587.60012
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 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.

60C05 Combinatorial probability
05C99 Graph theory
Full Text: DOI
[1] P. Erdos andL. Lovász, Problems and Results on 3-Chromatic Hypergraphs and Some Related Questions,Infinite and Finite Sets, Colloquia Mathematica Societatis János Bolyai, Keszthely (Hungary), 1973, 609–627.
[2] J. Spencer, Asymptotic Lower Bounds for Ramsey Functions,Discrete Math.,20(1977), 69–76. · Zbl 0375.05033 · doi:10.1016/0012-365X(77)90044-9
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.