ON-LINE LIST COLOURING OF RANDOM GRAPHS 9 Denote by Y,the random variable counting the number of erasers used for vertex v corresponding to medium sets,before eventually v gets a permanent colour.As in (8) Pr( 3np w log-n (np)/八√元logn) √logn o(n-1)+（1 9np ≤o(n-1)+exp Vw log n =o(n-1), and thus,as before,by a union bound,a.a.s.the desired bound for the number of erasers used for medium sets holds for all vertices. Combining bounds for the number of erasers used for large,medium,and small sets,we get that, regardless of the strategy used by Mr.Paint,Mrs.Correct uses at most (1+o(1))n/(2log(np)) erasers for each vertex,and the theorem follows. 4.PROOF OF THEOREM 2 As in the proof of Theorem 1,the lower bound follows immediately from(1),and so it remains to show that Mrs.Correct has a strategy that a.a.s.requires only O(n/log(np))erasers on each vertex(recall also(2)).We will use the same definitions for sets of being small,medium,and large as before,but we set here w=log log n;as pointed out right after Lemma 6,other choices of w are possible,but our choice gives the strongest result (as we assume the weakest condition).The argument for small sets remains exactly the same;a.a.s.it is enough to have o(n/log(np))erasers on each vertex to deal with all small sets that Mr.Paint may present.To deal with large sets,by Lemma 6,since we aim for a statement that holds a.a.s.,we may assume that whenever a large set is presented,Mrs.Correct can always find an independent set of size at least e(1-e)log(np)/(3p), keeps the colour on these vertices,and uses erasers for all remaining vertices.The number of large sets presented is therefore at most 3(e(1-E))-np/log(np)=O(n/log(np)),as needed.This is enough to determine the order of the on-line choice number but,if one aims for a better constant, then Remark 7 implies that for np=logn we are guaranteed to have an independent set of size i=i(C),where log(np)/p fC→∞ i=(1+o(1) (1-)log(np)/pifC∈[4，∞) log(np)/p fC∈(2,4). We will show below that the contribution of medium sets is of negligible order,and hence the upper bound on the number of erasers needed for large sets will also apply (up to lower order terms)to the total number of erasers needed.As a result,we will get the following bounds:(2+o(1)x(G) forC→o,(29+o1)x(G)forC∈4，o,amd(4+o1)x(G forC∈2,4). The strategy for medium sets has to be substantially modified.Suppose that a medium set S of size s is presented at some point of the game.Recall that np/(wlogn)<s<n/(w logn),where w =loglog n.Since we aim for a statement that holds a.a.s.,we may assume that Mrs.Correct can partition S in the following way:by applying Lemma 8(i)repeatedly,as long as at least so =10log n/p vertices are remaining,she can find independent sets of size [1/(9p)1,and remove them from S.(Note that for sparse graphs it might happen that s so and so the lemma cannot be applied even once.In such a situation,we simply move on to the next step.)If the number of remaining vertices,r,satisfies 2-sor<-+lso for some i=i(n)EN and r>np/(w log2n), then by Lemma 8(ii),she can find an independent set of size [i/(9p2)1.Then,she removes that independent set,and continues iteratively with the remaining vertices in S.Note that there are clearly M<log n/log 2 =O(logn)different sizes of independent sets corresponding to different values of i.Finally,if r<np/(wlogzn),she puts all the remaining vertices into a set J(not necessarily independent),and stops partitioningON-LINE LIST COLOURING OF RANDOM GRAPHS 9 Denote by Yv the random variable counting the number of erasers used for vertex v corresponding to medium sets, before eventually v gets a permanent colour. As in (8), Pr  Yv ≥ 3np √ ω log n  ≤ o(n −1 ) +  1 − ω log2 n 9np (np)/( √ ω log n) ≤ o(n −1 ) + exp  − √ ω log n 9  = o(n −1 ), and thus, as before, by a union bound, a.a.s. the desired bound for the number of erasers used for medium sets holds for all vertices. Combining bounds for the number of erasers used for large, medium, and small sets, we get that, regardless of the strategy used by Mr. Paint, Mrs. Correct uses at most (1 + o(1))n/(2 logb (np)) erasers for each vertex, and the theorem follows. 4. Proof of Theorem 2 As in the proof of Theorem 1, the lower bound follows immediately from (1), and so it remains to show that Mrs. Correct has a strategy that a.a.s. requires only O(n/ logb (np)) erasers on each vertex (recall also (2)). We will use the same definitions for sets of being small, medium, and large as before, but we set here ω = log log n; as pointed out right after Lemma 6, other choices of ω are possible, but our choice gives the strongest result (as we assume the weakest condition). The argument for small sets remains exactly the same; a.a.s. it is enough to have o(n/ logb (np)) erasers on each vertex to deal with all small sets that Mr. Paint may present. To deal with large sets, by Lemma 6, since we aim for a statement that holds a.a.s., we may assume that whenever a large set is presented, Mrs. Correct can always find an independent set of size at least ε(1 − ε) log(np)/(3p), keeps the colour on these vertices, and uses erasers for all remaining vertices. The number of large sets presented is therefore at most 3(ε(1 − ε))−1np/ log(np) = O(n/ logb (np)), as needed. This is enough to determine the order of the on-line choice number but, if one aims for a better constant, then Remark 7 implies that for np = logC+o(1) n we are guaranteed to have an independent set of size i = i(C), where i = (1 + o(1))    log(np)/p if C → ∞ (1 − 2 C ) log(np)/p if C ∈ [4,∞) 1 2 log(np)/p if C ∈ (2, 4). We will show below that the contribution of medium sets is of negligible order, and hence the upper bound on the number of erasers needed for large sets will also apply (up to lower order terms) to the total number of erasers needed. As a result, we will get the following bounds: (2 + o(1)χ(G) for C → ∞, ( 2C C−2 + o(1))χ(G) for C ∈ [4,∞), and (4 + o(1))χ(G) for C ∈ (2, 4). The strategy for medium sets has to be substantially modified. Suppose that a medium set S of size s is presented at some point of the game. Recall that np/(ω log2 n) < s < n/(ω log2 n), where ω = log log n. Since we aim for a statement that holds a.a.s., we may assume that Mrs. Correct can partition S in the following way: by applying Lemma 8(i) repeatedly, as long as at least s0 = 10 log n/p vertices are remaining, she can find independent sets of size ⌈1/(9p)⌉, and remove them from S. (Note that for sparse graphs it might happen that s < s0 and so the lemma cannot be applied even once. In such a situation, we simply move on to the next step.) If the number of remaining vertices, r, satisfies 2−i s0 ≤ r < 2 −i+1s0 for some i = i(n) ∈ N and r > np/(ω log2 n), then by Lemma 8(ii), she can find an independent set of size ⌈i/(9p2 i )⌉. Then, she removes that independent set, and continues iteratively with the remaining vertices in S. Note that there are clearly M ≤ log n/ log 2 = O(log n) different sizes of independent sets corresponding to different values of i. Finally, if r ≤ np/(ω log2 n), she puts all the remaining vertices into a set J (not necessarily independent), and stops partitioning