GRAPH THEORY a closer lo that,in fa t.it can be use o prod acoloring that is very likely to be good.This is because,for largeif then 《1 Hence.a random coloring of k is very likely not to contain a monochromatic K This means that if for ome reason.we s present a two o-coloring of the edge K1 without a mon can simply produce a random two-coorin by ping fair cotimes.We can then deliverhey the probability that it is less than 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 apowerfultool in combinatorics andgr aph theory.It is remely nd ir More re evelopment o rithr study of variot computationalproblems.In th e rest of this chapter,we present severa simple examples that demonstrate 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 menon a si vof0克5 otation=UBoi山edges ofmh graph on the set o every two distinct el ents x and yorVeither G.y)or ()sE.but not both.The nme tournamentsnatura since one can think of the set V as a set of players in which each pair participates in a single match.where (y)is in the tournament iff x beats y.We say that 7 has the property s.if.for every set of k Plavers.there is one that beats them all.For example. a directed triangle T =(V,E).where V=(1,2.3)and E=((1,2).(2,3).(3,1)). has s.Is it true that forevery finite k there is a tournament T (on more than k vertices) with the y S.As sho n by Erd6s (1963b).this proble raised by Schut can be solve applying prol bilistic Mo argu nents eve supply a rathe for th le n vertices in such a tournament.The basic(and natural)idea is that, large as a function of k,then a random tournament on the set V=1,...,n)of n players is very likely to have the property S.By a random tournament we mean here a tournament T on V obtained by choosing.for each 1 si<jsn,independently, either the edge (i,)or the edge (j,i),where each of these two choices is equallyGRAPH THEORY 5 and deterministic way of 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 = ⌊2k∕2⌋, then (n k ) ⋅ 2 1− ( k 2 ) < 21+k 2 k! ( n 2k∕2 )k ≤ 21+ k 2 k! ≪ 1. Hence, a random coloring of Kn is very likely not to contain a monochromaticK2 log n. This means that if, for some reason, we must present a two-coloring of the edges of K1024 without a monochromatic K20, we can simply produce a random two-coloring by flipping a fair coin ( 1024 2 ) times. We can then deliver the resulting coloring safely; the probability that it contains a monochromatic K20 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 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 demonstrate 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 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 elements x and y of V, either (x, y) or (y, x) 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 a single match, where (x, y) is in the tournament iff x beats y. We say that T has the property Sk if, for every set of k Players, there is one that 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 Sk? 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 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 of k, then a random tournament on the set V = {1, … , n} of n players is very likely to have the 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 (i, j) or the edge (j, i), where each of these two choices is equally