10 ALAN FRIEZE.DIETER MITSCHE.XAVIER PEREZ-GIMENEZ.AND PAWEL PRALAT 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)]for some 1 <i<M are called of type-i; and vertices from the last set of vertices J of size at most np/(w log-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 1/i 1/i 1+o(1) 9i= ∑巧 ∑7216 ilog logn 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 Anp 2 =0 =o(X(G)) Vwlog(np) logi(np) 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/(vwlog(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/(wlog(np))>log2(1)n times.Hence,it follows from Chernoff's bound that,with probability 1-o(n-1),at least np/(vwlog(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)within the first np/(vwlog(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 1/(9p)wlog2n (10) n/(wlog2n)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+1=9s02+1=901ogn+1≤ 00logn /(9p2) where for the last step we used that i<M<logn/log 2.This time,the probability that v is permanently coloured is at least 1+o(1) (11) 100logn100(log n)(log log n) 7 wlog(np)logn np where we used that w=log logn and np/(log(np))>log2+e/2n.Finally,if group-2 is chosen and v belongs to this group,the probability that v is permanently coloured is at least (12) 1 =wlog2n np/(w log2n) np10 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