Probabilistic Methods in Combinatorics

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)}}} < 1 $$ then there exists a graph G on n vertices with clique number w(G) < k and independence number a(G) < k. (in terms of the Ramsey function, R(k,k) > 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.