
doi: 10.1007/bf02579368
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.
Graph theory, Combinatorial probability, probabilistic method, existence of combinatorial configurations, random graph
Graph theory, Combinatorial probability, probabilistic method, existence of combinatorial configurations, random graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 82 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 1% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
