ON-LINE LIST COLOURING OF RANDOM GRAPHS.pdf_大学文库

ON-LINE LIST COLOURING OF RANDOM GRAPHS ALAN FRIEZE.DIETER MITSCHE.XAVIER PEREZ-GIMENEZ.AND PAWEL PRALAT ABSTRACT.In this paper,the on-line list colouring of binomial random graphs(n,p)is studied. We show that the on-line choice number of(n,p)is asymptotically almost surely asymptotic to the chromatic number of 9(n,p),provided that the average degree d=p(n-1)tends to infinity faster than (log logn)/3(logn)2n2/3.For sparser graphs,we are slightly less successful;we show that if d >(logn)2+for some e>0,then the on-line choice number is larger than the chromatic number by at most a multiplicative factor of C,where C[2,4],depending on the range of d. Also,for d=O(1),the on-line choice number is by at most a multiplicative constant factor larger than the chromatic number. 1.INTRODUCTION The combinatorial game we study in the paper is played by two players,named Mr.Paint and Mrs.Correct,and is played on a finite,undirected graph in which each vertex has assigned a non-negative number representing the number of erasers at the particular vertex.We assume for simplicity that this number is initially the same for each vertex.In each round,first Mr.Paint selects a subset of the vertices and paints them all the same colour;he cannot use this colour in subsequent rounds.Mrs.Correct then has to erase the colour from some of the vertices in order to prevent adjacent vertices having the same colour.Whenever the colour at a vertex is erased, the number of erasers at that vertex decreases by 1,but naturally,Mrs.Correct cannot erase the colour if she has no erasers left at that vertex.Vertices whose colours have not been erased can be considered as being permanently coloured and can be removed from the game.The game has two possible endings:(i)all vertices have been permanently coloured,in which case Mrs.Correct wins, or(ii)at some point of the game,Mr.Paint presents two adjacent vertices u and v and neither u nor v has any eraser left,in which case Mr.Paint wins.If,regardless of which sets she gets presented, there is a strategy for Mrs.Correct to win the game having initially k-1 erasers at each vertex, we say that the graph is k-paintable.The smallest k for which the graph is k-paintable is called the paintability number of G,and denoted by xp(G).Note that this parameter is indeed well defined:for any graph on n vertices,n-1 erasers at each vertex always guarantee Mrs.Correct to win,as she can always choose one vertex from a set presented to her and erase colours on the remaining ones.This problem is also known as the on-line list colouring and the corresponding graph parameter is also called the on-line choice number of Gsee,for example,[16]and below for the relation to the (off-line)list colouring. Let us recall a classic model of random graphs that we study in this paper.The binomial random graph (n,p)is defined as the probability space (S,F,Pr),where n is the set of all graphs with vertex set {1,2,...,n),F is the family of all subsets of D,and for every Ge, Pr(G)=plE(G)I(1-p)(3)-IE(G)I This space may be viewed as the set of outcomes of (2)independent coin flips,one for each pair (u,v)of vertices,where the probability of success (that is,adding edge uv)is p.Note that p=p(n) may (and usually does)tend to zero as n tends to infinity. The first author is supported in part by NSF Grant CCF0502793. The fourth author is supported in part by NSERC

arXiv:1501.07469v2 [math.CO] 12 May 2015 ON-LINE LIST COLOURING OF RANDOM GRAPHS ALAN FRIEZE, DIETER MITSCHE, XAVIER PEREZ-GIM ´ ENEZ, AND PAWE L PRA LAT ´ Abstract. In this paper, the on-line list colouring of binomial random graphs G (n, p) is studied. We show that the on-line choice number of G (n, p) is asymptotically almost surely asymptotic to the chromatic number of G (n, p), provided that the average degree d = p(n − 1) tends to infinity faster than (log log n) 1/3 (log n) 2n 2/3 . For sparser graphs, we are slightly less successful; we show that if d ≥ (log n) 2+ε for some ε > 0, then the on-line choice number is larger than the chromatic number by at most a multiplicative factor of C, where C ∈ [2, 4], depending on the range of d. Also, for d = O(1), the on-line choice number is by at most a multiplicative constant factor larger than the chromatic number. 1. Introduction The combinatorial game we study in the paper is played by two players, named Mr. Paint and Mrs. Correct, and is played on a finite, undirected graph in which each vertex has assigned a non-negative number representing the number of erasers at the particular vertex. We assume for simplicity that this number is initially the same for each vertex. In each round, first Mr. Paint selects a subset of the vertices and paints them all the same colour; he cannot use this colour in subsequent rounds. Mrs. Correct then has to erase the colour from some of the vertices in order to prevent adjacent vertices having the same colour. Whenever the colour at a vertex is erased, the number of erasers at that vertex decreases by 1, but naturally, Mrs. Correct cannot erase the colour if she has no erasers left at that vertex. Vertices whose colours have not been erased can be considered as being permanently coloured and can be removed from the game. The game has two possible endings: (i) all vertices have been permanently coloured, in which case Mrs. Correct wins, or (ii) at some point of the game, Mr. Paint presents two adjacent vertices u and v and neither u nor v has any eraser left, in which case Mr. Paint wins. If, regardless of which sets she gets presented, there is a strategy for Mrs. Correct to win the game having initially k − 1 erasers at each vertex, we say that the graph is k-paintable. The smallest k for which the graph is k-paintable is called the paintability number of G, and denoted by χP (G). Note that this parameter is indeed well defined: for any graph on n vertices, n − 1 erasers at each vertex always guarantee Mrs. Correct to win, as she can always choose one vertex from a set presented to her and erase colours on the remaining ones. This problem is also known as the on-line list colouring and the corresponding graph parameter is also called the on-line choice number of G—see, for example, [16] and below for the relation to the (off-line) list colouring. Let us recall a classic model of random graphs that we study in this paper. The binomial random graph G (n, p) is defined as the probability space (Ω, F,Pr), where Ω is the set of all graphs with vertex set {1, 2, . . . , n}, F is the family of all subsets of Ω, and for every G ∈ Ω, Pr(G) = p |E(G)| (1 − p) ( n 2 )−|E(G)| . This space may be viewed as the set of outcomes of n 2 independent coin flips, one for each pair (u, v) of vertices, where the probability of success (that is, adding edge uv) is p. Note that p = p(n) may (and usually does) tend to zero as n tends to infinity. The first author is supported in part by NSF Grant CCF0502793. The fourth author is supported in part by NSERC. 1

2 ALAN FRIEZE, DIETER MITSCHE, XAVIER PEREZ-GIM ´ ENEZ, AND PAWE L PRA LAT ´ All asymptotics throughout are as n → ∞ (we emphasize that the notations o(·) and O(·) refer to functions of n, not necessarily positive, whose growth is bounded; whereas Θ(·) and Ω(·) always refer to positive functions). We say that an event in a probability space holds asymptotically almost surely (or a.a.s.) if the probability that it holds tends to 1 as n goes to infinity. We often write G (n, p) when we mean a graph drawn from the distribution G (n, p). Finally, for simplicity, we will write f(n) ∼ g(n) if f(n)/g(n) → 1 as n → ∞ (that is, when f(n) = (1 + o(1))g(n)). Now, we will briefly mention the relation to other known graph parameters. A proper colouring of a graph is a labelling of its vertices with colours such that no two adjacent vertices have the same colour. A colouring using at most k colours is called a (proper) k-colouring. The smallest number of colours needed to colour a graph G is called its chromatic number, and it is denoted by χ(G). Let Lk be an arbitrary function that assigns to each vertex of G a list of k colours. We say that G is Lk-list-colourable if there exists a proper colouring of the vertices such that every vertex is coloured with a colour from its own list. A graph is k-choosable, if for every such function Lk, G is Lk-list-colourable. The minimum k for which a graph is k-choosable is called the list chromatic number, or the choice number, and denoted by χL(G). Since the choices for Lk contain the special case where each vertex is assigned the list of colours {1, 2, . . . , k}, it is clear that a k-choosable graph has also a k-colouring, and so χ(G) ≤ χL(G). It is also known that if a graph is k-paintable, then it is also k-choosable [13], that is, χL(G) ≤ χP (G). Indeed, if there exists a function Lk so that G is not Lk-list-colourable, then Mr. Paint can easily win by fixing some permutation of all colours present in Lk and presenting at the i-th step all vertices containing the i-th colour of the permutation on their lists (unless the vertex was already removed before). Finally, it was shown in [16] that the paintability of a graph G on n vertices is at most χ(G) log n + 1. (All logarithms in this paper are natural logarithms.) Combining all inequalities we get the following: (1) χ(G) ≤ χL(G) ≤ χP (G) ≤ χ(G) log n + 1. It follows from the well-known results of Bollob´as [4], Luczak [11] (see also McDiarmid [12]) that the chromatic number of G (n, p) a.a.s. satisfies (2) χ(G (n, p)) ∼ log(1/(1 − p))n 2 log(np) , for np → ∞ and p bounded away from 1. The study of the choice number of G (n, p) was initiated in [1], where Alon proved that a.a.s., the choice number of G (n, 1/2) is o(n). Kahn then showed (see [2]) that a.a.s. the choice number of G (n, 1/2) equals (1 + o(1))χG (n,1/2). In [7], Krivelevich showed that this holds for p ≫ n −1/4 , and Krivelevich, Sudakov, Vu, and Wormald [8] improved this to p ≫ n −1/3 . On the other hand, Alon, Krivelevich, Sudakov [3] and Vu [15] showed that for any value of p satisfying 2 0 be any constant, and suppose that (log log n) 1/3 (log n) 2n −1/3 ≪ p ≤ 1 − ε

4 ALAN FRIEZE, DIETER MITSCHE, XAVIER PEREZ-GIM ´ ENEZ, AND PAWE L PRA LAT ´ Let G = (V, E) be any graph. A set S ⊆ V is called independent if no edge e ∈ E has both endpoints in S. Denote by α(G) the independence number of G, that is, the size of a largest independent set of G. Let k0 be defined as follows: k0 = k0(n, p) = max k ∈ N : n k (1 − p) ( k 2 ) ≥ n 4 . It is well known that k0 is well defined (for all n sufficiently large and provided that p ≤ 1 − ε for some ε > 0) and that k0 ∼ 2 logb (np) with b = 1/(1 − p). The following result was proved in [8]. Theorem 4 ([8]). Suppose n −2/5 log6/5 n ≪ p ≤ 1 − ε for some constant ε > 0. Let G ∈ G(n, p). Then Pr(α(G) 0 be any constant and let ω = ω(n) = o(log n) be any function tending to infinity as n → ∞. Suppose that ω(log log n) 1/3 (log n) 2n −1/3 ≤ p ≤ 1 − ε. Let G ∈ G(n, p). Then, a.a.s. every set S ⊆ V (G) with |S| = s ≥ s0 := n/(ω log2 n) contains an independent set of size k0 = k0(s, p) ∼ k0(n, p). Proof. Fix a set S ⊆ V (G) with |S| = s ≥ n/(ω log2 n). First, let us note that k0 = k0(s, p) ∼ 2 logb (sp) = 2 logb (np) 1 − O log log n log n ∼ k0(n, p). Moreover, since n/(ω log2 n) ≤ s ≤ n, we can easily verify that p satisfies s −2/5 log6/5 s ≪ p ≤ 1 − ε (with room to spare in the lower bound). It follows immediately from Theorem 4 that the probability of not having an independent set of size k0 in S is at most exp −Ω s 2 k 4 0 p = exp −Ω s 2p 3 log4 n = exp −Ω snp3 ω log6 n = exp −Ω sω2 log log n . On the other hand, the number of sets of size s can be bounded as follows: n s ≤ ne s s = exp (s log(ne/s)) ≤ exp (3s log log n), since log(ne/s) ≤ log(eω log2 n) = (2 + o(1)) log log n. Hence, the expected number of sets of size s for which the desired property fails is exp −Ω sω2 log log n . Summing over all s ≥ s0, the expected number of all such sets is exp −Ω s0ω 2 log log n = o(1). The claim holds by Markov’s inequality. Given a graph G and some fixed ordering of its vertices (for example, we may assume that it is the natural ordering 1, 2, . . . , n), the greedy colouring algorithm proceeds by scanning vertices of G in the given order and assigning the first available colour for the current vertex. We will use the following lemma due to [9] (see also [5]). However, since we use it in a slightly different setting, we point out a few small differences in the argument by providing a sketch of the proof. In fact, this lemma is the bottleneck for the argument that prevents us to extend Theorem 2 for sparser graphs. Lemma 6. Let ω = ω(n) := log log n. Given any constant 0 < ε < 1, let G ∈ G(n, p) with log2+ε n/n =: p0 ≤ p = o(1/ log n). Then, a.a.s. every subgraph of G of size u ≥ u0 := n/(ω log2 n) has an independent set of size at least ε(1 − ε) log(np)/(3p).

6 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| 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

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) 9p21.Therefore,2i(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.Since

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) ∈ N such that (4) 9p2 i (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

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) 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)

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)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 partitioning

ON-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) 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

10 ALAN FRIEZE, DIETER MITSCHE, XAVIER PEREZ-GIM ´ ENEZ, AND PAWE L PRA LAT ´ We classify vertices in S into types depending on the size of the set in the partition of S to which they belong: more precisely, we call vertices from independent sets of size ⌈1/(9p)⌉ to be of type-0; vertices from independent sets of size ⌈i/(9p2 i )⌉ for some 1 ≤ i ≤ M are called of type-i; and vertices from the last set of vertices J of size at most np/(ω log2 n) are called of type-(M + 1). Of course, these definitions depend on the particular time a set S is presented by Mr. Paint. In particular, if a vertex is presented several times by Mr. Paint, each time it might be of a different type. Finally, we classify vertices in S into 3 groups: vertices of type-0 form group-0, vertices of type-1 up to type-M form group-1, and vertices of type-(M + 1) form group-2. Mrs. Correct now chooses with probability 1/3 one of the three groups. If group-0 is selected, she then picks uniformly at random one independent set within the group. In case when group-2 is selected, she picks uniformly at random a single vertex inside this group. Finally, if group-1 is selected, she first picks a random type. The probability that type-i is selected is equal to qi := 1/i PM j=1 1/j ≥ 1/i Plog n/ log 2 j=1 1/j = 1 + o(1) ilog log n . Then, within the selected type, an independent set is selected uniformly at random. If the group or type chosen by Mrs. Correct has no vertices in it, she picks no vertex to colour permanently, which is clearly a suboptimal strategy. Our goal is to show that a.a.s. each vertex v appears in less than 4np √ ω log(np) = o n logb (np) = o(χ(G)) many medium sets, before its colour is accepted. If this holds, then the number of erasers needed for each vertex (due to medium sets) is negligible. Suppose that some vertex v appears in at least 4np/( √ ω log(np)) medium sets. Since one of the three groups is selected uniformly at random for each medium set, we expect v to belong to the selected group at least (4/3)np/( √ ω log(np)) ≥ log2+ε+o(1) n times. Hence, it follows from Chernoff’s bound that, with probability 1 − o(n −1 ), at least np/( √ ω log(np)) times the group to which v belongs is chosen. Call this event E. It remains to show that, conditional on E, v will be permanently coloured with probability 1 − o(n −1 ) within the first np/( √ ω log(np)) times its group is picked for some medium set. Note that if group-0 is selected and v belongs to this group, the probability that v is chosen to be permanently coloured, is at least (10) 1/(9p) n/(ω log2 n) = ω log2 n 9np . Suppose then that group-1 is chosen, v belongs to this group and is of type-i for some 1 ≤ i ≤ M. The number of independent sets in the partition containing vertices of type-i is at most 2 −i+1s0/2 i/(9p2 i ) + 1 = 9s0p i + 1 = 90 log n i + 1 ≤ 100 log n i , where for the last step we used that i ≤ M ≤ log n/ log 2. This time, the probability that v is permanently coloured is at least (11) qi i 100 log n ≥ 1 + o(1) 100(log n)(log log n) ≥ ω log(np) log n np , where we used that ω = log log n and np/(log(np)) ≥ log2+ε/2 n. Finally, if group-2 is chosen and v belongs to this group, the probability that v is permanently coloured is at least (12) 1 np/(ω log2 n) = ω log2 n np