The basic method What you need is that your brain is open. -Paul Erdos 1.1 THE PROBABILISTIC METHOD The probabilistic method is a powerful tool for tackling many problems in discrete mathematics.Roughly speaking.the method works as follows:Trying to prove that a space of structures and then shows that the desired properties hold in this structures and then shows that the desired properties hold in this space with positive probability. The method is best illustrated by examples.Here is a simple one.The Ramsey a花e我 -coloring of the edge a complete subgraph on k vertices all of whose edges are colored red)or there is a blue K.Ramsey (1929)showed that R(k,(is finite for any two integers k and e. Let us obtain a lower bound for the diagonal Ramsey numbers R(k,k). Proposition 1.1.I If()(<1 then()>n.Thus R(k,)/2 for allk≥3. The Probabilistic Method,Third Edition By Noga Alon and Joel Spencer Copyright2008 John Wiley&Sons.Inc.1 The Basic Method What you need is that your brain is open. - Paul Erdos 1.1 THE PROBABILISTIC METHOD The probabihstic method is a powerful tool for tackling many problems in discrete mathematics. Roughly speaking, the method works as follows: Trying to prove that a structure with certain desired properties exists, one defines an appropriate probability space of structures and then shows that the desired properties hold in this structures and then shows that the desired properties hold in this space with positive probability. The method is best illustrated by examples. Here is a simple one. The Ramsey number R(k, £) is the smallest integer n such that in any two-coloring of the edges of a complete graph on n vértices Kn by red and blue, either there is a red K^ (i.e., a complete subgraph on k vértices all of whose edges are colored red) or there is a blue K(. Ramsey (1929) showed that R(k, l) is finite for any two integers k and í. Let us obtain a lower bound for the diagonal Ramsey numbers R(k, k). Proposition 1.1.1 //(") •21 ~(^ < lthenR(k,k) > n. Thus R(k,k) > [2k l 2 \for all k > 3. The Probabilistic Method, Third Edition By Noga Alón and Joel Spencer Copyright © 2008 John Wiley & Sons, Inc. 1