ON-LINE LIST COLOURING OF RANDOM GRAPHS 5 Note that in the lemma we set w =loglog n;other functions tending to infinity slower than log log n,constant,or even tending to 0 not too quickly clearly would work as well,but would make the statement of the result weaker. Sketch of the proof.We follow the notation as in [9]and apply the greedy approach given there for each subgraph of size u.Let (1-E)log(up) up and p t=log(up) Note that a02 (1-e)log(np/(wlog2n))(1-e)(log(np)-(2+o(1))log logn) 2 (1-e)(e+(1))log(np)(1-e)elog(np) (2+e)p 3p since np>log2en.(Note that,if np log n,then we get the better estimate ao >(1-E)(1-2/C+o(1))log(np)/p; see Remark 7 below.)Moreover, (1-p)a0 exp(-pao(1+O(p)))=exp(-(1-E)log(up)(1+O(p))) exp(-(1-)log(up))=(up)-1+e since p =o(1/log n).For a fixed subgraph of size u,it follows from [9]that the probability that the algorithm fails to produce an independent set of size at least oo is at most exp(-t(1-p)aoue)=exp (up)(1+o(1)(up)-1+eue log(up) u1+ep(e+o(1)】 =exp log(up) By taking a union bound over all (（）s(告)'=exp(ubox(ne/w》≤ep6) sets of size u,the probability Pu that there exists a subgraph of size u for which the algorithm fails is at most up)(E+o(1)) exp -u log(up) -3log log （uopo)F(e+o(1) (-u log(oPo） -3log log n as the function f(x)=xe/logr is increasing for large enough x.Since uopo loge n/w log+o(四n, Pu≤exp (logn)(e+()(+o(1 (E+o(1))log log n )3log logn =exp（-u(ogn)+oa-3 log logn)）≤e“ Summing over all uo u<n,we see that the probability that the algorithm fails is at most ∑=oe-“=O(e-uo）=o(1),and the lemma follows..ON-LINE LIST COLOURING OF RANDOM GRAPHS 5 Note that in the lemma we set ω = log log n; other functions tending to infinity slower than log log n, constant, or even tending to 0 not too quickly clearly would work as well, but would make the statement of the result weaker. Sketch of the proof. We follow the notation as in [9] and apply the greedy approach given there for each subgraph of size u. Let α0 = (1 − ε) log(up) p and t = up log(up) . Note that α0 ≥ (1 − ε) log(np/(ω log2 n)) p = (1 − ε)(log(np) − (2 + o(1)) log log n) p ≥ (1 − ε)(ε + o(1)) log(np) (2 + ε)p ≥ (1 − ε)ε log(np) 3p , since np ≥ log2+ε n. (Note that, if np ≥ logC n, then we get the better estimate α0 ≥ (1 − ε)(1 − 2/C + o(1)) log(np)/p; see Remark 7 below.) Moreover, (1 − p) α0 = exp (−pα0(1 + O(p))) = exp (−(1 − ε) log(up)(1 + O(p))) ∼ exp (−(1 − ε) log(up)) = (up) −1+ε , since p = o(1/ log n). For a fixed subgraph of size u, it follows from [9] that the probability that the algorithm fails to produce an independent set of size at least α0 is at most exp (−t(1 − p) α0 uε) = exp  − (up)(1 + o(1))(up) −1+εuε log(up)  = exp  − u 1+εp ε (ε + o(1)) log(up)  . By taking a union bound over all  n u  ≤ ne u u = exp(u log(ne/u)) ≤ exp(3u log log n) sets of size u, the probability Pu that there exists a subgraph of size u for which the algorithm fails is at most exp  −u  (up) ε (ε + o(1)) log(up) − 3 log log n  ≤ exp  −u  (u0p0) ε (ε + o(1)) log(u0p0) − 3 log log n  , as the function f(x) = x ε/ log x is increasing for large enough x. Since u0p0 = logε n/ω = logε+o(1) n, Pu ≤ exp −u (log n) (ε+o(1))ε (ε + o(1)) (ε + o(1)) log log n − 3 log log n !! = exp  −u  (log n) ε 2+o(1) − 3 log log n  ≤ e −u . P Summing over all u0 ≤ u ≤ n, we see that the probability that the algorithm fails is at most n u=u0 e −u = O(e −u0 ) = o(1), and the lemma follows.