The harmonic mean formula for probabilities of unions: Applications to sparse random graphs (Q1823263)

Let \((A_ i:\) \(1\leq i\leq n)\) be a collection of events of a probability space with the property that, for all \(1\leq i,j\leq n\), there exists a permutation \(\pi\) of \(\{\) 1,2,...,n\(\}\) such that \(\pi (i)=j\) and \(P(A_{i_ 1}\cap...\cap A_{i_ r})=P(A_{\pi (i_ 1)}\cap...\cap A_{\pi (i_ r)}\) for all \(i_ 1,i_ 2,...,i_ r\). The elementary formula \(P(A_ 1\cup...\cup A_ n)=pnE(N^{-1}| A_ 1)\) is established, linking \(p=P(A_ i)\) for any i, and the number N of the \(A_ i\) which occur. This is a generalization of Boole's inequality, capable of application. Various applications are given or sketched, including further results concerning the independence number and `partition number' (defined as the minimal number of edges of a graph whose removal breaks G into subgraphs having equal numbers of vertices) of a sparse random graph on n vertices each edge of which is present with probability \(\alpha\) /n. For further applications, see the author, ``Applications of the Poisson clumping heuristic'' [Springer, New York (1988)].