2 THE BASIC METHOD 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 fixed et A be the event that the induced subgrap ofo R is monochromatic (i.e.,that either all its edges are red or they are all blue).Clearly, Pr[AR=2-().Since there are (possible choices for R.the probability that at least one of the events Ar occurs is at most ()1.Thus.with positive probability,no event AR occurs and there is a two-coloring of K without monochromatic K'k;that is,R(k,)>n.Note that if k 3 and we take n =2k/2 then (-<2 ‘2n<1 and hence R(k,k)>2/2 for all k 3. ■ This simple example der strates the essence of the probabilistic method.To prove the existence of a good coloring we do not present one explicitly.but rather show,in a nonconstructive way.that it exists.This example appeared in a paper of P.Erdos from 1947.Although Szele had applied the probabilistic method to another combinatorial problem,me ntioned in Chapter 2,already in 1943,Erdos was cer understood the full power of ths method and over the vears to numerous problems.One can.of course.claim that the probability is not essential in the proof given above.An equally simple proof can be described by counting:we just check that the total number of two-colorings of K is larger than the number of those containing a m ochromatic Kk. Moreover.since the vast majority of the probability spaces considered in the study of combinatorial problems are finite spaces,this claim applies to most of the applications of the probabilistic method in discrete mathematics.Theoretically this 1S, indeed,the case. However,in practice,the probability is essential. It be hopeless to replace the applications of many of the tools appearing in this book including,for example,the second moment method,the Lovasz Local Lemma and the concentration via martingales by counting arguments,even when these are applied to finite probabil ity space The probabilistic method has an interesting algorithmic aspect.Consider,for example,the proof of Proposition 1.1.1 that shows that there is an edge two-coloring of K without a monochromatic K2 Can we actually find such a coloring? question,as asked,may so nd ridicul ossible coloring is finite,so we can try them all until we find the desired one. However,such a quiresteps;anamount of time that isexponential in the size he problm.Algorithms whosen m ismoreo the size of the problem are usually considered impractical.The class of problems that can be solved in polynomial time,usually denoted by P[see,e.g.,Aho,Hopcroft and Ullman (1974)1,is,in a sense.the class of all solvable problems.In this sense,the acceptable,and this is the reason for our remark that the proof of Proposition 1.1.1 is nonconstructive;it does not supply a constructive,efficient and deterministic way of 2 THE BASIC METHOD 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 fixed set i? of k vértices, let AR be the event that the induced subgraph of Kn on R is monochromatic (Le., that either all its edges are red or they are all blue). Clearly, Pr[^4ñ] = 21 -' - 2 '. Since there are (£) possible choices for R, the probability that at least one of the events AR occurs is at most (^)2l ~\2> < 1. Thus, with positive probability, no event AR occurs and there is a two-coloring of Kn without a monochromatic Kk; that is, R(k, k) > n. Note that if k > 3 and we take n = |_2fc/ 2 J then / n \ i (k\ 21+i nk U > ía)< ifcr-2wí < 1 and henee R(k, k) > |_2fc/ 2 J for all k > 3. • This simple example demonstrates the essence of the probabilistic method. To prove the existence of a good coloring we do not present one explicitly, but rather show, in a nonconstructive way, that it exists. This example appeared in a paper of P. Erdós from 1947. Although Szele had applied the probabilistic method to another combinatorial problem, mentioned in Chapter 2, already in 1943, Erdós was certainly the first one who understood the full power of this method and applied it successfully over the years to numerous problems. One can, of course, claim that the probability is not essential in the proof given above. An equally simple proof can be described by counting; we just check that the total number of two-colorings of Kn is larger than the number of those containing a monochromatic K¡-. Moreover, since the vast majority of the probability spaces considered in the study of combinatorial problems are finite spaces, this claim applies to most of the applications of the probabilistic method in discrete mathematics. Theoretically, this is, indeed, the case. However, in practice, the probability is essential. It would be hopeless to replace the applications of many of the tools appearing in this book, including, for example, the second moment method, the Lovász Local Lemma and the concentration via martingales by counting arguments, even when these are applied to finite probability spaces. The probabilistic method has an interesting algorithmic aspect. Consider, for example, the proof of Proposition 1.1.1 that shows that there is an edge two-coloring of Kn without a monochromatic i^2iog2n- Can we actually find such a coloring? This question, as asked, may sound ridiculous; the total number of possible colorings is finite, so we can try them all until we find the desired one. However, such a procedure may require 2\2> steps; an amount of time that is exponential in the size [= (2)] of the problem. Algorithms whose running time is more than polynomial in the size of the problem are usually considered impractical. The class of problems that can be solved in polynomial time, usually denoted by P [see, e.g., Aho, Hopcroft and Ullman (1974)], is, in a sense, the class of all solvable problems. In this sense, the exhaustive search approach suggested above for finding a good coloring of Kn is not acceptable, and this is the reason for our remark that the proof of Proposition 1.1.1 is nonconstructive; it does not supply a constructive, efficient and deterministic way of