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 structure with certain desired properties exists,one defines an appropriate prob- ability space of structures and then shows that the desired properties hold in these structures with positive probability.The method is best illustrated by examples.Here isa simple one.The Ran seymbe)is the smallest integ er n such that in edges of a c omplete graph two integersk and.Let us obtain a lower bound for the diagonal Ramsey numbers R(). Proposition .1.lr（g）-2-台)<l.then R(k,.>n.Thus R(k,>2P]or allk≥3. Proof.Consider a random two-coloring of the edges of K obtained by coloring each edge independently either red or blue,where each color is equally likely.For any 0 IPblae 0o wleyc1 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 structure with certain desired properties exists, one defines an appropriate prob￾ability space of structures and then shows that the desired properties hold in these structures 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 vertices Kn by red and blue, either there is a red Kk (i.e., 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 𝓁. Let us obtain a lower bound for the diagonal Ramsey numbers R(k, k). Proposition 1.1.1 If (n k ) ⋅ 2 1− ( k 2 ) < 1, then R(k, k) > n. Thus R(k, k) > ⌊2k∕2⌋ for all k ≥ 3. Proof. Consider a random two-coloring of the edges of Kn obtained by coloring each edge independently either red or blue, where each color is equally likely. For any The Probabilistic Method, Fourth Edition. Noga Alon and Joel H. Spencer. © 2016 John Wiley & Sons, Inc. Published 2016 by John Wiley & Sons, Inc