Вероятностные методы в комбинаторике

В 1947 году Пауль Эрдёш положил начало тому, что теперь называется вероятностным методом. Он показал, что если C(n,k) 2^{1 - C(k,2)} < 1, то существует граф G на n вершинах с числом клики ω(G) < k и числом независимости α(G) < k (в терминах функции Рамсея, R(k,k) > n). В современной терминологии он рассматривал случайный граф G(n, 0.5). Для каждого k-элементного множества S обозначим B_S «плохим» событием, что S является либо кликой, либо независимым множеством. Тогда Pr[B_S] = 2^{1 - C(k,2)}, поэтому Σ Pr[B_S] < 1; следовательно пересечение дополнений событий B_S непусто, и должен существовать граф, удовлетворяющий всем этим дополнениям.