THE BASIC METHOD fixed set R of k vertices.let Ag be the event that the induced subgraph of K on R is monochromatic (i.e.,that either all its edges are red or they are all blue).Clearly. )Since there are possible choices for R,the probability that at least one of the.Thus wth positive prob. ability,no event Ag occurs and there is a two-coloring of K without a monochromatic K;that is,Rk,k)>n.Note that if k≥3 and we take n=l2kp」，then ()2)<2. !“2R万<1 and hence R(k,k)>2]for all k2 3. egpo心心e or the prbbilic mth} existence of a good colorir g.we do not present one explicitl rather s e way,that it exists. his example paper of P.Erdos from 1947.Althouh Szele had applied the probabiistie method to another combinatorial problem,mentioned in Chapter 2,already in 1943,Erdos was certainly the first to understand the full power of this method and apply 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- colori ngs of Kis larger than the of th nta Moreover nce of comb a probl vast maj lity spaces considered in the study inite,this the probab the probabilistis method in discrete mathematics.Thepretically thsed th s0 ost of th 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 Lovasz Local Lemma and the concentration via martingales by counting arguments,even when these are applied to finite probability Spaces for ex le,the proof of Propositio 1.1.1 which s ows that o-oin e an edg ally 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, sucha procedure may requiresteps:an amount of time that is exponential in the size =(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 ap proach suggested above for finding a good ceptable,and thi isis the re r remark that the of Proposition 1.1.1 is nonconstructive:it does not supply a constructive,efficient 4 THE BASIC METHOD fixed set R of k vertices, let AR be the event that the induced subgraph of Kn on R is monochromatic (i.e., that either all its edges are red or they are all blue). Clearly, Pr[AR] = 2 1− ( k 2 ) . Since there are (n k ) possible choices for R, the probability that at least one of the events AR occurs is at most (n k ) 2 1− ( k 2 ) < 1. Thus, with positive prob￾ability, no event AR occurs and there is a two-coloring ofKn without a monochromatic Kk; that is, R(k, k) > n. Note that if k ≥ 3 and we take n = ⌊2k∕2⌋, then (n k ) 2 1− ( k 2 ) < 21+k 2 k! ⋅ nk 2k2∕2 < 1 and hence R(k, k) > ⌊2k∕2⌋ 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. Erdos from 1947. Although Szele had a ˝ pplied the probabilistic method to another combinatorial problem, mentioned in Chapter 2, already in 1943, Erdos˝ was certainly the first to understand the full power of this method and apply 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 Kk. Moreover, since the vast majority of the probability spaces considered in the study of combinatorial problems are finite, 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, which shows that there is an edge two-coloring of Kn without a monochromatic K2log2n. 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 (n 2 ) steps; an amount of time that is exponential in the size [ = ( n 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