Probabilistic Methods in Combinatorics
Joel Spencer · Birkhäuser Basel eBooks · 1995
In 1947 Paul Erdős [8] began what is now called the probabilistic method. He showed that if $$\left( {\begin{array}{*{20}{c}} n \\ k \\ \end{array} } \right){{2}^{{1 - \left( {\begin{array}{*{20}{c}} k \\ 2 \\ \end{array} } \right)}}} n.) In modern lanuage he considered the random graph G(n,.5) as described below. For each k-set S let BS denote the “bad” events that S is either a clique or an independent set. Then Pr[BS] = 21-(k/2) so that ΣPr[BS] < 1, hence ∧ $$ \wedge {\bar B_s}$$ ≠ ∅ and a graph satisfying ∧ $$ \wedge {\bar B_s}$$ must exist.