ON-LINE LIST COLOURING OF RANDOM GRAPHS 7 any set S in the desired range,at least s/2 vertices of S have a degree of at most 4sp in the graph induced by S.By applying a greedy algorithm to these vertices,we can therefore always find an independent set of size at least (s/2)/(4sp+1)>1/(9p). Part (ii)is proved in a similar way.Fix i=i(n)E N such that (4) 9p2<i (since otherwise the statement is trivial),and a set SV(G)of size s satisfying the following: (5) 2-s0≤8<2-i+1s0: Since s is a natural number,we must have 2-i+lso >1.Therefore,2i<2so 2n (where we used that p 10logn/n),and thus (6) i≤log(2n)/log2≤2logn, for n large enough.Combining(5),(4),the fact that pso =10log n,and (6),we get s≥2-ts0>(9p/i)s0=(90/i)1ogn≥45. Note that for s≥45， It follows from the stronger version of Chernoff's bound(3)that Pr(B≥(+)Esl) exp(-(2/i)E]Esl) 28卫 ≤exp-4·2.i 2s2p ≤exp 一9 (Note that (2i/i)=(1+2 /i)log(1+2i/i)-2/i(2i/i)log(2i/i)~2i log2 as ioo.Moreover, it is straightforward to see that for every i∈N,p(2/i)）≥2'/4.) As before,by a union bound we get that with probability at most exp(s(logn-2'sp/9))there exists a set of size s not satisfying the condition.Since,by assumption,s >2-so =2-10log n/p, this probability is at most exp(-slog n/9),regardless of which precise interval [2-iso,2-i+1so) contains s.Summing the exp(-s log n/9)bound we obtained over all values 45 <s<so gives o(1). Therefore,we may assume that (deterministically),for any iN,every subset S of size s in the range(5)satisfies 1≤(+))p≤(+)字s Arguing as before,this guarantees that we can always find an independent set of size at least (s/2)/(4.22sp/i+1)≥i/(9.2p (At the last step,we used that 4.2isp/i+1 <4.2.2isp/i,which follows easily from (5),(6)and the definition of so.)The proof of the lemma is finished. 3.PROOF OF THEOREM 1 The lower bound follows immediately from (1).For the upper bound,we give a winning strategy for Mrs.Correct that a.a.s.requires only (1+o(1))n/(2log(np))erasers on each vertex,where b =1/(1-p).(Recall from (2)that a.a.s.x(G)~n/(2log6(np)).)We emphasize that most probabilistic statements hereafter in the proof will not refer to(n,p)but rather to the randomized strategy that Mrs.Correct uses to select each independent set,regardless of the strategy of Mr.Paint and assuming that G deterministically satisfies the conclusions of Corollary 5 and Lemma 8.SinceON-LINE LIST COLOURING OF RANDOM GRAPHS 7 any set S in the desired range, at least s/2 vertices of S have a degree of at most 4sp in the graph induced by S. By applying a greedy algorithm to these vertices, we can therefore always find an independent set of size at least (s/2)/(4sp + 1) ≥ 1/(9p). Part (ii) is proved in a similar way. Fix i = i(n) ∈ N such that (4) 9p2 i < i (since otherwise the statement is trivial), and a set S ⊆ V (G) of size s satisfying the following: (5) 2−i s0 ≤ s < 2 −i+1s0. Since s is a natural number, we must have 2−i+1s0 ≥ 1. Therefore, 2i ≤ 2s0 ≤ 2n (where we used that p ≥ 10 log n/n), and thus (6) i ≤ log(2n)/ log 2 ≤ 2 log n, for n large enough. Combining (5), (4), the fact that ps0 = 10 log n, and (6), we get s ≥ 2 −i s0 > (9p/i)s0 = (90/i) log n ≥ 45. Note that for s ≥ 45, E|ES| =  s 2  p ≥ s 2p 2.1 . It follows from the stronger version of Chernoff’s bound (3) that Pr  |ES| ≥  1 + 2 i i  E|ES|  = exp ￾ −ϕ(2i /i)E|ES|
≤ exp  − 2 i 4 · s 2p 2.1  ≤ exp  − 2 i s 2p 9  . (Note that ϕ(2i/i) = (1 + 2i/i) log(1 + 2i/i)− 2 i/i ∼ (2i/i) log(2i/i) ∼ 2 i log 2 as i → ∞. Moreover, it is straightforward to see that for every i ∈ N, ϕ(2i/i) ≥ 2 i/4.) As before, by a union bound we get that with probability at most exp(s(log n − 2 i sp/9)) there exists a set of size s not satisfying the condition. Since, by assumption, s ≥ 2 −i s0 = 2−i10 log n/p, this probability is at most exp(−s log n/9), regardless of which precise interval [2−i s0, 2 −i+1s0) contains s. Summing the exp(−s log n/9) bound we obtained over all values 45 ≤ s < s0 gives o(1). Therefore, we may assume that (deterministically), for any i ∈ N, every subset S of size s in the range (5) satisfies |ES| ≤  1 + 2 i i  s 2  p ≤  1 + 2 i i  s 2p 2 ≤ 2 i s 2 p/i. Arguing as before, this guarantees that we can always find an independent set of size at least (s/2)/(4 · 2 i sp/i + 1) ≥ i/(9 · 2 i p). (At the last step, we used that 4 · 2 i sp/i + 1 ≤ 4.2 · 2 i sp/i, which follows easily from (5), (6) and the definition of s0.) The proof of the lemma is finished. 3. Proof of Theorem 1 The lower bound follows immediately from (1). For the upper bound, we give a winning strategy for Mrs. Correct that a.a.s. requires only (1 + o(1))n/(2 logb (np)) erasers on each vertex, where b = 1/(1 − p). (Recall from (2) that a.a.s. χ(G) ∼ n/(2 logb (np)).) We emphasize that most probabilistic statements hereafter in the proof will not refer to G (n, p) but rather to the randomized strategy that Mrs. Correct uses to select each independent set, regardless of the strategy of Mr. Paint and assuming that G deterministically satisfies the conclusions of Corollary 5 and Lemma 8. Since