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-GIMENEZ,AND PAWEL PRALAT All asymptotics throughout are as n-oo (we emphasize that the notations o()and O()refer to functions of n,not necessarily positive,whose growth is bounded;whereas e()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 (n,p)when we mean a graph drawn from the distribution (n,p).Finally,for simplicity, we will write f(n)~g(n)if f(n)/g(n)1 as noo (that is,when f(n)=(1+0(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 x(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 L-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 xL(G).Since the choices for Lk contain the special case where each vertex is assigned the list of colours f1,2,...,k,it is clear that a k-choosable graph has also a k-colouring,and so x(G)<XL(G).It is also known that if a graph is k-paintable,then it is also k-choosable [13],that is,xL(G)<XP(G).Indeed, if there exists a function Lk so that G is not L-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 x(G)logn+1.(All logarithms in this paper are natural logarithms.)Combining all inequalities we get the following: (1) X(G)≤Xz(G)≤XP(G≤x(G)logn+1. It follows from the well-known results of Bollobas [4],Luczak [11](see also McDiarmid [12])that the chromatic number of(n,p)a.a.s.satisfies (2) x(4(np)) log(1/(1-p))n 2log(np) for npoo and p bounded away from 1.The study of the choice number of (n,p)was initiated in [1],where Alon proved that a.a.s.,the choice number of (n,1/2)is o(n).Kahn then showed (see [2])that a.a.s.the choice number of(n,1/2)equals (1+o(1))(n1/2).In [7],Krivelevich showed that this holds for pn1/4,and Krivelevich,Sudakov,Vu,and Wormald 8]improved this to pn/3.On the other hand,Alon,Krivelevich,Sudakov [3]and Vu [15]showed that for any value of p satisfying 2<np n/2,the choice number is e(np/log(np)).Later,Krivelevich and Vu [10]generalized this to hypergraphs;they also improved the leading constants and showed that the choice number for C<np 0.9n (where C is a sufficiently large constant)is at most a multiplicative factor of 2+o(1)away from the chromatic number,the best known factor for p<n-1/3.Our results below (see Theorem 1,Theorem 2,and Theorem 3)show that even for the on-line case,for a wide range of p,we can asymptotically match the best known constants of the off-line case.Moreover,if np logn (for some function w=w(n)tending to infinity as noo), then we get the same multiplicative factor of 2+o(1). Our main results are the following theorems.The first one deals with dense random graphs. Theorem 1.Let e>0 be any constant,and suppose that (log log n)/3(log n)2n-1/3<p<1-e

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 < np ≤ n/2, the choice number is Θ(np/ log(np)). Later, Krivelevich and Vu [10] generalized this to hypergraphs; they also improved the leading constants and showed that the choice number for C ≤ np ≤ 0.9n (where C is a sufficiently large constant) is at most a multiplicative factor of 2 + o(1) away from the chromatic number, the best known factor for p ≤ n −1/3 . Our results below (see Theorem 1, Theorem 2, and Theorem 3) show that even for the on-line case, for a wide range of p, we can asymptotically match the best known constants of the off-line case. Moreover, if np ≥ logω n (for some function ω = ω(n) tending to infinity as n → ∞), then we get the same multiplicative factor of 2 + o(1). Our main results are the following theorems. The first one deals with dense random graphs. Theorem 1. Let ε > 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-GIMENEZ.AND PAWEL PRALAT Let G=(V,E)be any graph.A set S CV is called independent if no edge eE has both endpoints in S.Denote by a(G)the independence number of G,that is,the size of a largest independent set of G.Let ko be defined as follows: =a红，刊=max{keN ()1-pm≥m} It is well known that ko is well defined (for all n sufficiently large and provided that p <1-e for some e>0)and that ko ~2log(np)with b=1/(1-p).The following result was proved in [8]. Theorem 4((8]).Suppose n-2/510g6/5n<p<1-e for some constant >0.Let GEG(n,p). Then Pa<=即(n(》 We obtain the following immediate corollary that will be useful to deal with dense random graphs. In fact,this lemma is the bottleneck for the argument that prevents us to extend Theorem 1 for sparser graphs. Corollary 5.Let e>0 be any constant and let w=w(n)=o(logn)be any function tending to infinity as n->oo.Suppose that w(loglog n)1/3(1ogn)2n-1/3≤p≤1-e. Let GEG(n,p).Then,a.a.s.every set S C V(G)with S]=s so:=n/(w log2n)contains an independent set of size ko =ko(s,p)~ko(n,p). Proof.Fix a set SCV(G)with S]=s>n/(wlog2n).First,let us note that ko=ko(s,p)~2logb(sp)2l0go(np)(1-O log log n ko(n,p). log n Moreover,since n/(wlog2n)<s<n,we can easily verify that p satisfies s-2/5l0g6/5sp< 1-E(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 ko in S is at most em(()》 (()》-em(( smp3） exp(-(sw2loglog n)) On the other hand,the number of sets of size s can be bounded as follows: )s(s)°=xp(olo(ne/s/》≤epBs1 log og, n since log(ne/s)<log(ewlog2n)=(2+o(1))loglogn.Hence,the expected number of sets of size s for which the desired property fails is exp(-(sw2loglogn)).Summing over all s>so,the expected number of all such sets is exp(-(sow2 loglogn))=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 w=w(n):=log logn.Given any constant 0<<1,let GE G(n,p)with log2+en/n =po <p=o(1/logn).Then,a.a.s.every subgraph of G of size uuo:=n/(w log2n) has an independent set of size at least e(1-E)log(np)/(3p)

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) < k0) = exp −Ω n 2 k 4 0 p . We obtain the following immediate corollary that will be useful to deal with dense random graphs. In fact, this lemma is the bottleneck for the argument that prevents us to extend Theorem 1 for sparser graphs. Corollary 5. Let ε > 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).