6 ALAN FRIEZE,DIETER MITSCHE,XAVIER PEREZ-GIMENEZ,AND PAWEL PRALAT Remark 7.Lemma 6 is sufficient to determine the order of the on-line choice number for sparse random graphs.We comment on improvements in order to obtain the smallest leading constant in the upper bound.From the proof of the lemma it is clear that the bound on the size of the independent set can be improved for denser graphs.More precisely,for np log"n (for w-oo but still p o(1/log n)),we can obtain independent sets of size at least (1-2e)log(np)/p for any arbitrarily small e,and so we are asymptotically just a factor 2+o(1)off from the bound of Corollary 5. On the other hand,for C being a constant larger than 2,and np=log()n,we can obtain independent sets of size at least (1-)(1-2/C+o(1))log(np)/p (again,for any arbitrarily small e),so by Lemma 6 we are off by a factor 2/(1-2/C)+o(1)=2C/(C-2)+o(1).We will now show that for log2+en/np=o(n-5/6),however,the independence number obtained is by at most a factor 4+o(1)off from the one obtained by Corollary 5.First,as shown above,given u n/(wlog2n),there are at most exp(3uloglogn)sets of size u,and the expected number of edges induced by each such set is (2)p.By Chernoff's bound,the probability that the number of edges induced by one of them deviates by an additive (2)p/log logn factor from its expected value is at most exp(-(1/log logn)2u2p/5).Hence,with probability at most exp(u(3log logn-(logn)(1/loglogn)2/(5w)))<exp(-u), there exists a set of size u that does not satisfy the condition.Summing over all n/(w log2n)< u<n,we see that a.a.s.for all such sets we have (1+o(1))u2p/2 edges.On the other hand, note that for this range of p,the expected number of pairs of triangles sharing one vertex in G is e(n5p5)=o(1),and thus by Markov's inequality,a.a.s.every vertex is in at most one triangle. It follows that there exists a set D of edges which is a matching such that after removing D the graph is triangle-free.Since in G the average degree of every set of size u is up(1+o(1)),the same also holds for G\D.Since G\D is triangle-free,by Shearer's lemma [14],an independent set of size (1+o(1))log(np)/p can be found.By eliminating at most half of the set (one vertex for each edge in D),we obtain an independent set in the original graph.It follows that for every set of size u,there exists an independent set of size at least log(np)/((2+o(1))p),being therefore at most a factor 4+o(1)off from the size obtained by Corollary 5. We will also need the following observation. Lemma8.LetG∈g(m,p),forl0logn/m≤p≤1，and set so=l0logn/p.Then,a.a.s.the following holds: (i)every set SCV(G)with so <S<n contains an independent set of size at least 1/(9p); (ii)for every iE N and every set SC V(G)with 2-iso S<2-i+1so,S contains an independent set of size at least i/(9p2). Before we move to the proof of the lemma,let us note that the lower bound on p is not used in the proof of part (i),which becomes a trivial statement if p 10log n/n.For part (ii),we could easily relax this bound to p1/n(for any constant>0)by changing some of the constants in the statement.Furthermore,part (i)is trivially true for p >1/9,and part (ii)is only non-trivial for all i satisfying 9p2<i. Proof.For part (i),let us fix a set S with S]=s satisfying so <s <n.Denote by Es the set of edges induced by S.We have EEs=(2)p~s2p/2.By Chernoff's bound,with probability at least 1-exp(-EEsl/4),we have |Esl <s2p.By taking a union bound over all ()exp(s logn)subsets of size s,with probability at most exp(s(logn-sp/9))there exists a set of size s not satisfying the condition.Since,by assumption,s>so 10log n/p,this probability is at most exp(-slogn/9), and so summing over all s>so,the claim holds a.a.s.for all s in the desired range.We may therefore assume that (deterministically)every subset of size s>so satisfies Es<s2p.Then,for6 ALAN FRIEZE, DIETER MITSCHE, XAVIER PEREZ-GIM ´ ENEZ, AND PAWE L PRA LAT ´ Remark 7. Lemma 6 is sufficient to determine the order of the on-line choice number for sparse random graphs. We comment on improvements in order to obtain the smallest leading constant in the upper bound. From the proof of the lemma it is clear that the bound on the size of the independent set can be improved for denser graphs. More precisely, for np ≥ logω n (for ω → ∞ but still p = o(1/ log n)), we can obtain independent sets of size at least (1 − 2ε) log(np)/p for any arbitrarily small ε, and so we are asymptotically just a factor 2 + o(1) off from the bound of Corollary 5. On the other hand, for C being a constant larger than 2, and np = logC+o(1) n, we can obtain independent sets of size at least (1 − ε)(1 − 2/C + o(1)) log(np)/p (again, for any arbitrarily small ε), so by Lemma 6 we are off by a factor 2/(1 − 2/C) + o(1) = 2C/(C − 2) + o(1). We will now show that for log2+ε n/n ≤ p = o(n −5/6 ), however, the independence number obtained is by at most a factor 4 + o(1) off from the one obtained by Corollary 5. First, as shown above, given u ≥ n/(ω log2 n), there are at most exp(3u log log n) sets of size u, and the expected number of edges induced by each such set is ￾ u 2
p. By Chernoff’s bound, the probability that the number of edges induced by one of them deviates by an additive ￾ u 2
p/ log log n factor from its expected value is at most exp ￾ −(1/ log log n) 2u 2p/5
. Hence, with probability at most exp ￾ u(3 log log n − (log n) ε (1/ log log n) 2 /(5ω))
≤ exp (−u), there exists a set of size u that does not satisfy the condition. Summing over all n/(ω log2 n) ≤ u ≤ n, we see that a.a.s. for all such sets we have (1 + o(1))u 2p/2 edges. On the other hand, note that for this range of p, the expected number of pairs of triangles sharing one vertex in G is Θ(n 5p 6 ) = o(1), and thus by Markov’s inequality, a.a.s. every vertex is in at most one triangle. It follows that there exists a set D of edges which is a matching such that after removing D the graph is triangle-free. Since in G the average degree of every set of size u is up(1 + o(1)), the same also holds for G \ D. Since G \ D is triangle-free, by Shearer’s lemma [14], an independent set of size (1 + o(1)) log(np)/p can be found. By eliminating at most half of the set (one vertex for each edge in D), we obtain an independent set in the original graph. It follows that for every set of size u, there exists an independent set of size at least log(np)/((2 + o(1))p), being therefore at most a factor 4 + o(1) off from the size obtained by Corollary 5. We will also need the following observation. Lemma 8. Let G ∈ G(n, p), for 10 log n/n ≤ p ≤ 1, and set s0 = 10 log n/p. Then, a.a.s. the following holds: (i) every set S ⊆ V (G) with s0 ≤ |S| ≤ n contains an independent set of size at least 1/(9p); (ii) for every i ∈ N and every set S ⊆ V (G) with 2 −i s0 ≤ |S| < 2 −i+1s0, S contains an independent set of size at least i/(9p2 i ). Before we move to the proof of the lemma, let us note that the lower bound on p is not used in the proof of part (i), which becomes a trivial statement if p < 10 log n/n. For part (ii), we could easily relax this bound to p ≥ 1/nk (for any constant k > 0) by changing some of the constants in the statement. Furthermore, part (i) is trivially true for p ≥ 1/9, and part (ii) is only non-trivial for all i satisfying 9p2 i < i. Proof. For part (i), let us fix a set S with |S| = s satisfying s0 ≤ s ≤ n. Denote by ES the set of edges induced by S. We have E|ES| = ￾ s 2
p ∼ s 2p/2. By Chernoff’s bound, with probability at least 1−exp(−E|ES|/4), we have |ES| ≤ s 2p. By taking a union bound over all ￾ n s
≤ exp(s log n) subsets of size s, with probability at most exp(s(log n − sp/9)) there exists a set of size s not satisfying the condition. Since, by assumption, s ≥ s0 = 10 log n/p, this probability is at most exp(−s log n/9), and so summing over all s ≥ s0, the claim holds a.a.s. for all s in the desired range. We may therefore assume that (deterministically) every subset of size s ≥ s0 satisfies |ES| ≤ s 2p. Then, for