Chapter 1
The Basic Method

-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 is the smallest integer n such that in any two-coloring of the edges of a complete graph on n vertices by red and blue, either there is a red (i.e., a complete subgraph on k vertices all of whose edges are colored red) or there is a blue . Ramsey 1929 showed that is finite for any two integers k and . Let us obtain a lower bound for the diagonal Ramsey numbers .

Proposition 1.1.1

If , then . Thus for all .

Proof.

Consider a random two-coloring of the edges of obtained by coloring each edge independently either red or blue, where each color is equally likely. For any fixed set R of k vertices, let be the event that the induced subgraph of 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 events occurs is at most . Thus, with positive probability, no event occurs and there is a two-coloring of without a monochromatic ; that is, . Note that if and we take , then

and hence for all .

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 applied 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 is larger than the number of those containing a monochromatic .

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 without a monochromatic . 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 steps; 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 approach suggested above for finding a good coloring of 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 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 , then

Hence, a random coloring of is very likely not to contain a monochromatic . This means that if, for some reason, we must present a two-coloring of the edges of without a monochromatic , we can simply produce a random two-coloring by flipping a fair coin times. We can then deliver the resulting coloring safely; the probability that it contains a monochromatic 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 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 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 or 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 is in the tournament iff x beats y. We say that T has the property if, for every set of k Players, there is one that beats them all. For example, a directed triangle , where and , has . Is it true that for every finite k there is a tournament T (on more than k vertices) with the property ? 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 of n players is very likely to have the property . By a random tournament we mean here a tournament T on V obtained by choosing, for each , independently, either the edge or the edge , where each of these two choices is equally likely. Observe that in this manner, all the 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 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 , then there is a tournament on n vertices that has the property .

Proof.

Consider a random tournament on the set . For every fixed subset K of size k of V, let be the event that there is no vertex that beats all the members of K. Clearly, . This is because, for each fixed vertex , the probability that v does not beat all the members of K is , and all these events corresponding to the various possible choices of v are independent. It follows that

Therefore, with positive probability, no event occurs; that is, there is a tournament on n vertices that has the property .

Let denote the minimum possible number of vertices of a tournament that has the property . Since and , Theorem 1.2.1 implies that . It is not too difficult to check that and . As proved by Szekeres (cf. Moon 1968), .

Can one find an explicit construction of tournaments with at most vertices having property ? Such a construction is known but is not trivial; it is described in Chapter 9.

A dominating set of an undirected graph is a set such that every vertex has at least one neighbor in U.

Theorem 1.2.2

Let be a graph on n vertices, with minimum degree . Then G has a dominating set of at most vertices.

Proof.

Let 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 be the random set of all vertices in that do not have any neighbor in X. The expected value of is clearly . For each fixed vertex , and its neighbors are not in . Since the expected value of a sum of random...