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 Proposi￾tion 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 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[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 inde￾pendently, 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