4 THE BASIC METHOD equally likely;that is,the probability space considered is symmetric.It is worth we shall sometimes element of the space as a random with describing explicitly the probability distribution.Thus.for example,in the proof of Proposition 1.1.I 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-k)n-k<1 then there is a tournament on n vertices that has the property Si. 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)-.This is because for each 1-2enex fixed V-K,the probability that does not beat all the membe of K is and all these n-k events corresponding to the various possible choices of v are independent.It follows that Pr L IK- Therefore,with positive probability,noevent Ak occurs:that is,there is a tournament on n vertices that has the property Sk. Let f()denote the minimum possible number of vertices of a tournament that to check that f(1)=3 and f(2)=7.As proved by Szekeres [cf.Moon (1968)]. f()≥c91·k·2 Can one find an explicit construction of toura ments with at most c vertices having property S?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 vV-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 6>1.Then G has a dominating set of at most n[1+In(6+1)/(6+1)vertices. Proof.Let p e 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 haveany neighbor of y p Foreach fixed verte: vEV,PrvY]=Pr [v and its neighbors are not in X]<(1-p)5+ Since the expected value of a sum of random variables is the sum of their expectations (even 4 THE BASIC METHOD 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 lf (£)(1 — 2~k ) n ~ k < 1 then there is a tournament on n vértices that has the property Sf¿- 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 vértex that beats all the members of K. Clearly Pr [AK] = (1 — 2~~k ) n ~ k . This is because for each fixed vértex v G V — K, the probability that v does not beat all the members of K is 1 — 2~fc , and all these n — k events corresponding to the various possible choices of v are independent. It follows that Pr V ¿* KCV |/C|=fc < £ Pr[AK]=(f\(l-2'k ) n - k <l KCV V / \K\ = k Therefore, with positive probability, no event AK occurs; that is, there is a tournament on n vértices that has the property Sk- • Let f(k) denote the mínimum possible number of vértices of a tournament that has the property Sk. Since (£) < (en/k)k and (1 - 2~k ) n - k < e-^-k)/2k ^ Theorem 1.2.1 implies that f(k) < k2 • 2k • (ln2)(l + o(l)). It is not too difficult to check that /(l) = 3 and /(2) = 7. As proved by Szekeres [cf. Moon (1968)], /(fe) > ci • k-2k . Can one find an explicit construction of tournaments with at most c k vértices having property S^? 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 C V such that every vértex v G V — U has at least one neighbor in U. Theorem 1.2.2 Let G = (V, E) be a graph on n vértices, with mínimum degree 5 > 1. Then G has a dominating set of at most n[\ + ln(á + l)]/(¿ + 1) vértices. Proof. Let p G [0,1] be, for the moment, arbitrary. Let us pick, randomly and independently, each vértex of V with probability p. Let X be the (random) set of all vértices picked and let Y — Yx be the random set of all vértices in V - X that do not have any neighbor in X. The expected valué of |X \ is clearly np. For each fixed vértex v G V, Pr [v G Y] = Pr [v and its neighbors are not in X] < (1 — p)6+1 . Since the expected valué of a sum of random variables is the sum of their expectations (even