PART I METHODS
PART I METHODS
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 wleyc
1 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 probability 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
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 probability, 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
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 equally
GRAPH 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
6 THE BASIC METHOD likely.Observe that in this manner.all the possible touramentson areeqully likely:that is,the probability space considered is symmetric.It is worth noting that use in applications symmetric probability spaces In these cases,we e shall refer an element of the as a random element,without des ribi of Proposi tion 1.1.1 random two-colorings of K were considered:that is,all possible colorings were equally likely.Similarly,in the proof of the next simple result we study random tournaments on V. Theorem 1.2.1 If(1-2-ky<1,then there is a tournament onn vertices that has the property S Proof.Consider arandomtournament on the set V=(1,....n).For every fixed sub set K of size k of V.let Ak be the event that there is no vertex that beats all the members of K.Clearly,Pr[Ag]=(1-2-y"-.This is because,for each fixed vertex vV-K,the probability that vdoes not beat all the members of K is 1-2-,and all these n-k events corresponding to the various possible choices of vare independent. It follows that Pr Axs Pr[Axl=()(1-2-5y-<1. Therefore,with positive probability,no event Ag occurs;that is,there is a tournament on n vertices that has the property S Let f(k)denote the minimum possible number of vertices of a tournament that has the propertySince(日<（月and(l-2-t*ypt<e-t-/t,Theorem 1.2.1 implies that f()2..(In 2)(1+(1)).It is not too difficult to check that f(1)=3 and f(2)=7.As proved by Szekeres (cf.Moon (1968)).f(k)2c.k.2. Can one find an explicit construction of tournaments with at most c vertices having property Such a construction is known but is not trivial;it is described in Chapter 9. et of an undirected graph G=(V,E)is a set U V such that every Theorem 1.LeG(V,E)begraphinmumdegree Then G has a dominating set of at most n- vertices. ò+1 Proof.Letp [0.1]be,for the moment,arbitrary.Let us pick,randomly and inde- pendently.each vertex of V with probabilityp.Letbe the (random)seof llvertices dom set of all verticesin that don neighbor in X.The expected value of is clearly np.For each fixed vertex
6 THE BASIC METHOD likely. Observe that in this manner, all the 2 ( n 2 ) possible tournaments on V are equally likely; that is, the probability space considered is symmetric. It is worth noting that we often use in applications symmetric probability spaces. In these cases, we shall sometimes refer to an element of the space as a random element, without describing explicitly the probability distribution . Thus, for example, in the proof of Proposition 1.1.1 random two-colorings of Kn were considered; that is, all possible colorings were equally likely. Similarly, in the proof of the next simple result we study random tournaments on V. Theorem 1.2.1 If (n k ) (1 − 2−k) n−k < 1, then there is a tournament on n vertices that has the property Sk. Proof. Consider a random tournament on the set V = {1, … , n}. For every fixed subset K of size k of V, let AK be the event that there is no vertex that beats all the members of K. Clearly, Pr[AK]=(1 − 2−k) n−k. This is because, for each fixed vertex 𝑣 ∈ V − K, the probability that 𝑣 does not beat all the members of K is 1 − 2−k, and all these n − k events corresponding to the various possible choices of 𝑣 are independent. It follows that Pr ⎡ ⎢ ⎢ ⎣ ∨ K⊂V |K|=k AK ⎤ ⎥ ⎥ ⎦ ≤ ∑ K⊂V |K|=k Pr[AK] = (n k ) (1 − 2−k ) n−k < 1. Therefore, with positive probability, no event AK occurs; that is, there is a tournament on n vertices that has the property Sk. ◾ Let f(k) denote the minimum possible number of vertices of a tournament that has the property Sk. Since ( n k ) < ( en k )k and (1 − 2−k) n−k < e−(n−k)∕2k , Theorem 1.2.1 implies that f(k) ≤ k2 ⋅ 2k ⋅ (ln 2)(1 + o(1)). It is not too difficult to check that f(1) = 3 and f(2) = 7. As proved by Szekeres (cf. Moon (1968)), f(k) ≥ c1 ⋅ k ⋅ 2k. Can one find an explicit construction of tournaments with at most ck 2 vertices having property Sk? Such a construction is known but is not trivial; it is described in Chapter 9. A dominating set of an undirected graph G = (V, E) is a set U ⊆ V such that every vertex 𝑣 ∈ V − U has at least one neighbor in U. Theorem 1.2.2 Let G = (V, E) be a graph on n vertices, with minimum degree 𝛿 > 1. Then G has a dominating set of at most n 1 + ln (𝛿 + 1) 𝛿 + 1 vertices. Proof. Let p ∈ [0, 1] be, for the moment, arbitrary. Let us pick, randomly and independently, each vertex of V with probability p. Let X be the (random) set of all vertices picked and let Y = YX be the random set of all vertices in V − X that do not have any neighbor in X. The expected value of |X| is clearly np. For each fixed vertex 𝑣 ∈ V