8 ALAN FRIEZE,DIETER MITSCHE,XAVIER PEREZ-GIMENEZ,AND PAWEL PRALAT p(loglogn)1/3(logn)2n-1/3,we can choose a function w=o(logn)tending to infinity with n and such that p>w(loglog n)1/3(log n)2n-1/3.Note that our choice of w satisfies the requirements of Corollary 5.Call a set S CV(G)large if S=s >n/(wlog2n),small if s np/(wlog2n), and medium otherwise. Whenever Mrs.Correct is presented a large set,she can,by Corollary 5 find an independent set of size ko =(2+o(1))log(np),and uses erasers for all remaining vertices.Note that,trivially,at most (7) 2(1)log,(mnp)=((1))2log(np) large sets can be presented to her before the end of the game,and hence,for all large sets at most that many erasers on each vertex are needed. Suppose now that a small set S is presented to Mrs.Correct.Then,she chooses a random vertex v E S and accepts the colour on that vertex;for all other vertices of the presented set erasers are used.(Note that this is clearly not a optimal strategy;Mrs.Correct could extend fu}to a maximal independent set but we do not use it in the argument and so we may pretend that a single vertex is accepted.Let X.denote the random variable counting the number of erasers used when small sets containing v are presented before eventually v gets a permanent colour(which does not necessarily happen when a small set is presented).We have (8) wlog2nmpl(vwlog n) <exp(-vwlogn)=o(n-1), np and thus,by a union bound,a.a.s.for all vertices the number of erasers used for small sets is at most (9) np Vwlogn 2log(np) and so is negligible. Now,we are going to deal with medium sets.First,note that the size of a medium set is at least np/(wlogn)>10log n/p for the range of p considered in this theorem and by our choice of w.Suppose that some medium set S is presented during the game.Applying Lemma 8 repeatedly, Mrs.Correct can partition S into independent sets of size [1/(9p)]and a remaining set J of size at most 10logn/p np/(wlog2n).The strategy is then the following:with probability 1/2 she chooses(uniformly at random)one of the independent sets of size [1/(9p)],and with probability 1/2 she chooses one vertex chosen uniformly at random fromJ(as before,this is clearly a suboptimal strategy but convenient to analyze).Selected vertices keep the colour;for the others erasers need to be used.We partition the vertices of S into two groups:group 1 consists of vertices belonging to independent sets,and group 2 consists of vertices ofJ.Our goal is to show that each vertex v appears in less than 3np/(vw log n)many medium sets,so that the total number of erasers needed to deal with these situations is negligible (see(9)). Suppose that some vertex v appears in at least 3np/(vw log n)medium sets.Each time,the corresponding medium set is split into two groups,and we cannot control in which group v ends up.However,by Chernoff's bound,with probability 1-o(n),at least np/(vwlogn)times the group to which v belongs is chosen.We condition on this event.Note that if group 2 is chosen and u belongs to this group,the probability that v is not selected is at most 1-wlog2n/(np)(as in(8) for small sets).Similarly,if group 1 is chosen and v belongs to this group,the probability that v is not chosen,is at most 1-wlogn/(9np),as each medium set has size at most n/(wlog2n).8 ALAN FRIEZE, DIETER MITSCHE, XAVIER PEREZ-GIM ´ ENEZ, AND PAWE L PRA LAT ´ p ≫ (log log n) 1/3 (log n) 2n −1/3 , we can choose a function ω = o(log n) tending to infinity with n and such that p ≥ ω(log log n) 1/3 (log n) 2n −1/3 . Note that our choice of ω satisfies the requirements of Corollary 5. Call a set S ⊆ V (G) large if |S| = s ≥ n/(ω log2 n), small if s ≤ np/(ω log2 n), and medium otherwise. Whenever Mrs. Correct is presented a large set, she can, by Corollary 5 find an independent set of size k0 = (2 + o(1)) logb (np), and uses erasers for all remaining vertices. Note that, trivially, at most (7) n (2 + o(1)) logb (np) = (1 + o(1)) n 2 logb (np) large sets can be presented to her before the end of the game, and hence, for all large sets at most that many erasers on each vertex are needed. Suppose now that a small set S is presented to Mrs. Correct. Then, she chooses a random vertex v ∈ S and accepts the colour on that vertex; for all other vertices of the presented set erasers are used. (Note that this is clearly not a optimal strategy; Mrs. Correct could extend {v} to a maximal independent set but we do not use it in the argument and so we may pretend that a single vertex is accepted.) Let Xv denote the random variable counting the number of erasers used when small sets containing v are presented before eventually v gets a permanent colour (which does not necessarily happen when a small set is presented). We have (8) Pr  Xv ≥ np √ ω log n  ≤  1 − ω log2 n np np/( √ ω log n) ≤ exp(− √ ω log n) = o(n −1 ), and thus, by a union bound, a.a.s. for all vertices the number of erasers used for small sets is at most (9) np √ ω log n = o  n 2 logb (np)  , and so is negligible. Now, we are going to deal with medium sets. First, note that the size of a medium set is at least np/(ω log2 n) ≥ 10 log n/p for the range of p considered in this theorem and by our choice of ω. Suppose that some medium set S is presented during the game. Applying Lemma 8 repeatedly, Mrs. Correct can partition S into independent sets of size ⌈1/(9p)⌉ and a remaining set J of size at most 10 log n/p ≤ np/(ω log2 n). The strategy is then the following: with probability 1/2 she chooses (uniformly at random) one of the independent sets of size ⌈1/(9p)⌉, and with probability 1/2 she chooses one vertex chosen uniformly at random from J (as before, this is clearly a suboptimal strategy but convenient to analyze). Selected vertices keep the colour; for the others erasers need to be used. We partition the vertices of S into two groups: group 1 consists of vertices belonging to independent sets, and group 2 consists of vertices of J. Our goal is to show that each vertex v appears in less than 3np/( √ ω log n) many medium sets, so that the total number of erasers needed to deal with these situations is negligible (see (9)). Suppose that some vertex v appears in at least 3np/( √ ω log n) medium sets. Each time, the corresponding medium set is split into two groups, and we cannot control in which group v ends up. However, by Chernoff’s bound, with probability 1 − o(n −1 ), at least np/( √ ω log n) times the group to which v belongs is chosen. We condition on this event. Note that if group 2 is chosen and v belongs to this group, the probability that v is not selected is at most 1− ω log2 n/(np) (as in (8) for small sets). Similarly, if group 1 is chosen and v belongs to this group, the probability that v is not chosen, is at most 1 − ω log2 n/(9np), as each medium set has size at most n/(ω log2 n)