GRAPH THEORY 3 producing a coloring with the desired properties.However,a closer look at the proof shows that,in fact,it can be used to produce,effectively,a coloring that is very likely to be good.This is because for then <1 Hence,a random coloring of K is very likely not to contain a monochromatic This means that if.for some reason,we must present a two-coloring edges of Kwithout a monochromatic K2o we can simply random two-coloring by flipping a fair coin()times We can the deliver the resulting coloring safely:the probability that it contains a monochromatic K2o is less than 211/20!,probably much smaller than our chances of making a mistake in any rigorous proof that a certain coloring is good!Therefore,in some cases the constructive method doe supply effective probabilistic algorithn Moreover,these algorithms can sometimes be converted into deterministic ones.This topic is discussed in some detail in Chapter 16. The probabilistic method is a powerful tool in Combinatorics and in Graph Theory. It is also extremely useful in Number Theory and in Combinatorial Geome has in the evelopment of effi nt algorithmic and in the study of various computational problems.In the rest of this chapter we present several simple examples that demonstrate some of the broad spectrum of topics in which this method is helpful.More compicated examples involving various more delicate probabilistic arguments,appear in the rest of the book 1.2 GRAPH THEORY A tournament on a set V of n players is an orientation T=(V,E)of the edges of the complete graph on the set of vertices V.Thus for every two distinct elementsx and y of V either(,y)or (y,is in E,but not both.The name"tournament"is natural, since one can think of the set V as a set of players in which each pair participates in asingle match,where(,y)is in the tourn ent iff beats y.We say that T has the property S if for every set of k players there is one who beats them all.For example,a directed triangle T3 =(V.E).where V=1,2,3)and E =(1,2),(2,3),(3,1), has S1.Is it true that for every finite k:there is a tournament T(on more than k vertices) with the property S?As s own by Erdos(1963b).this problem,raised by Schiitte can be solved almost trivially by applying probabilistic arguments.Moreover,these arguments even supply a rather sharp estimate for the minimum possible number of vertices in such a tournament The basic (and natural)idea is that if n is sufficiently large as a function ofk,then a random to nament on the set V={1,...,n}of n players is very likely to have property Sk.By a random tournament we mean here a tournament T'on V obtained by choosing,for each 1 i<j<n,independently, either the edge (ij)or the edge (j.i),where each of these two choices is equally likely.Observe that in this manner,all the 2()possible tournaments on V areGRAPH THEORY 3 producing a coloring with the desired properties. However, a closer look at the proof shows that, in fact, it can be used to produce, effectively, a coloring that is very likely to be good. This is because for large k, if n = |_2fc/ 2 J then \k) < k\ [2^> S k\ ^ Henee, a random coloring of Kn is very likely not to contain a monochromatic •f^iogn- This means that if, for some reason, we must present a two-coloring of the edges of KW2i without a monochromatic K2o we can simply produce a random two-coloring by flipping a fair coin ( 2 ) times. We can then deliver the resulting coloring safely; the probability that it contains a monochromatic X20 is less than 211/20!, probably much smaller than our chances of making a mistake in any rigorous proof that a certain coloring is good! Therefore, in some cases the probabilistic, nonconstructive method does supply effective probabilistic algorithms. Moreover, these algorithms can sometimes be converted into deterministic ones. This topic is discussed in some detail in Chapter 16. The probabilistic method is a powerful tool in Combinatorics and in Graph Theory. It is also extremely useful in Number Theory and in Combinatorial Geometry. More recently, it has been applied in the development of efficient algorithmic techniques and in the study of various computational problems. In the rest of this chapter we present several simple examples that demónstrate some of the broad spectrum of topics in which this method is helpful. More complicated examples, involving various more delicate probabilistic arguments, appear in the rest of the book. 1.2 GRAPH THEORY A toumament on a set V of n players is an orientation T = (V, E) of the edges of the complete graph on the set of vértices V. Thus for every two distinct elements x and y of V either (x, y) or (y, x) is in E, but not both. The ñame "toumament" is natural, since one can think of the set Vas a set of players in which each pair participates in a single match, where (x, y) is in the toumament iff x beats y. We say that T has the property Su if for every set of/c players there is one who beats them all. For example, a directed triangle T3 = (V, E), where V = {1,2,3} and £ = {(1,2), (2,3), (3,1)}, has S\. Is it true that for every finite k there is a toumament T (on more than k vértices) with the property Sfc? As shown by Erdos (1963b), this problem, raised by Schütte, can be solved almost trivially by applying probabilistic arguments. Moreover, these arguments even supply a rather sharp estímate for the mínimum possible number of vértices in such a toumament. The basic (and natural) idea is that if n is sufficiently large as a function of k, then a random toumament on the set V = {1,... , n} of n players is very likely to have property Sk. By a random toumament we mean here a toumament T onV obtained by choosing, for each 1 < i < j < n, independently, either the edge (i,j) or the edge (j, i), where each of these two choices is equally likely. Observe that in this manner, all the 2^J possible toumaments on V are