Non-concentration of the chromatic number of a random graph
Annika Heckel

 Local determination of the Hubble constant and the deceleration parameter
    Valerio Marra
    December 30, 2023
=========================================================================


We show that the chromatic number of G_n, 1/2 is not concentrated on fewer than n^1/4-ϵ consecutive values. This addresses a longstanding question raised by Erdős and several other authors.




§ INTRODUCTION

Random graph theory was initiated in the late 1950s and early 1960s in the pioneering works of Erdős and Rényi <cit.>. For the binomial random graph G_n,p, include each possible edge between n labelled vertices independently with probability p. For the closely related uniform random graph G_n,m, choose a set of exactly m edges uniformly at random from all edge sets of size m. Both of these models have been studied extensively since their introduction sixty years ago, and we refer to the standard texts <cit.> and <cit.> for the rich history of this subject and many impressive results.

The chromatic number of a graph G, denoted by χ(G),
is a central concept both in graph theory in general and in random graphs in particular. It is defined as the minimum number of colours needed for a vertex colouring of G where no two adjacent vertices are coloured the same. The study of the chromatic number of random graphs goes back to the foundational papers by Erdős and Rényi <cit.> and includes some of the most 
celebrated results in random graph theory. 

The case of dense random graphs where p=1/2 has received particular attention. Grimmett and McDiarmid <cit.> first found the order of magnitude of χ(G_n, 1/2) in 1975,
and in a breakthrough paper in 1987, Bollobás <cit.> used martingale concentration arguments to 
establish the asymptotic value.
With high probability[As usual, we say that a sequence (E_n)_n ∈ of events holds with high probability (whp) if (E_n) → 1 as n →∞.],

    χ(G_n, 1/2) ∼n/2 log_2 n.
 

Several improvements to these bounds were made by McDiarmid <cit.>, Panagiotou and Steger <cit.> and Fountoulakis, Kang and McDiarmid <cit.>. In 2016 <cit.>, the author used the second moment method, combined with martingale concentration arguments, to obtain the following result.

With high probability,  

    χ(G_n, 1/2) = n/2 log_2 n-2 log_2 log_2 n - 2+o(n/log^2 n).



While these bounds give an explicit interval of length o ( n/log^2 n) which contains χ(G_n, 1/2) whp, much narrower concentration is known to hold. A remarkable result of Shamir and Spencer <cit.> states that for any sequence p=p(n), χ(G_n,p) is whp contained in a (non-explicit) sequence of intervals of length about √(n). For p = 1/2, Alon improved this slightly to about √(n)/log n (this is 7.9, Exercise 3 in <cit.>, see also <cit.>).

For sparse random graphs, much more is known: Shamir and Spencer <cit.> also showed that for p<n^-5/6 -ε, χ(G_n,p) is whp concentrated on only five consecutive values; Łuczak <cit.> improved this to two consecutive values and finally Alon and Krivelevich <cit.> showed that two point concentration holds for p<n^-1/2-ε. In a landmark contribution, Achlioptas and Naor <cit.> found two explicit such values for p=d/n where d is constant, and Coja-Oghlan, Panagiotou and Steger <cit.> extended this to three explicit values for p<n^-3/4 - ϵ.

However, while there is a wealth of results asserting sharp concentration of the chromatic number of G_n,p, until now there have been no non-trivial cases where χ(G_n,p) is known not to be extremely narrowly concentrated. (Though Alon and Krivelevich <cit.> note that it is trivial that χ(G_n,p) is not concentrated on fewer than Θ(√(n)) values for p=1-1/(10n).) 

In his appendix to the standard text on the probabilistic method <cit.>, Erdős asked the following question (see also <cit.>): How accurately can χ(G_n, 1/2) be estimated? 
Can it be shown not to be concentrated on a series of intervals of constant length? Variants of this question are discussed in <cit.>, <cit.>, <cit.> and <cit.>. 
In 2004,  Bollobás <cit.> asked for any non-trivial examples of non-concentration of the chromatic number of random graphs, specifically suggesting the dense random graph G_n,m with m= ⌊ n^2/4 ⌋ (which corresponds to p=1/2) as a candidate.  
He mentions discussing the question frequently with Erdős in the late 1980s, and notes that “even the weakest results claiming lack of concentration would be of interest.”

In this paper, we show that χ(G_n, 1/2) is not whp concentrated on fewer than n^1/4 - ε consecutive values. As a corollary, the same is true for the random graph G_n,m with m= ⌊ n^2/4 ⌋; more details are given in Section <ref>.

 For any constant c< 1/4, there is no sequence of intervals of length n^c which contain χ(G_n, 1/2) with high probability. 

  
 
 The proof of Theorem <ref> is based on the close relationship between the chromatic number and the number of maximum independent sets in G_n, 1/2. 
 For a graph G, we denote by α(G) the independence number of G, that is, the size of the largest independent vertex set. The independence number of G_n, 1/2 is very well studied: let

    α_0 = α_0(n)= 2 log_2 n - 2 log_2 log_2 n +2 log_2 ( e/2 )+1    and    a=a(n)=⌊α_0 ⌋,

then it follows from the work of Matula <cit.> and Bollobás and Erdős <cit.> that whp α(G_n, 1/2) = ⌊α_0+o(1)⌋, pinning down α(G_n, 1/2) to at most two consecutive values. In fact, for most n, whp α(G_n, 1/2) = a. 

In the following, we will call a set of vertices of size a an a-set. Let X_a denote the number of independent a-sets in G_n, 1/2, then the distribution of X_a is known to be approximately Poisson with mean μ=𝔼[X_a] (for details see Section <ref>). We will see in Section <ref> that

    μ = n  a(1/2)^a  2=n^x   where    o(1) ⩽ x(n)⩽ 1+o(1).

 In particular, X_a is not whp contained in any sequence of intervals of length shorter than √(μ)=n^x/2. 
 
 


Note that χ(G_n, 1/2) is closely linked to α(G_n, 1/2). The lower bound in Theorem <ref> comes from the simple relationship χ(G) ≥ n / α(G) which holds for any graph G on n vertices, and Theorem <ref> implies that the average colour class size in an optimal colouring of G_n, 1/2 is 

    α_0-1-2/log 2+o(1) ≈α_0 - 3.89.

It is plausible that an optimal colouring of G_n, 1/2 contains all or almost all independent a-sets. This is because, amongst all possible choices of colour class sizes for a fixed number of colours k ≈n/2 log_2 n, the expected number of colourings is maximised if all or almost all a-sets are included. This intuition indicates χ(G_n, 1/2) should vary at least 
as much as X_a (up to a logarithmic factor). We show that this is indeed the case for some values n where x=x(n) is close to 1/2.




§ PROOF OF THEOREM <REF>



 §.§ Outline

Suppose that [s_n, t_n] is a sequence of intervals so that whp, χ(G_n, 1/2) ∈ [s_n, t_n]. In light of Theorem <ref>, we may assume that

    s_n = f(n)+o(n/log^2 n)    where    f(n)=n/2 log_2 n-2 log_2 log_2 n - 2.

(It is clear that s_n ≤ f(n) + o(n/log^2 n), but if (<ref>) does not hold, we may replace s_n with some larger s_n' = f(n)+o(n/log^2 n), which can only shorten the interval lengths.) Let

    l_n=t_n - s_n

denote the interval length, and fix c ∈(0, 1/4). We will show that there is some n^* ≥ 1 such that

    l_n^*≥( n^*) ^c,

which suffices to prove Theorem <ref>.

We start in Section <ref> with the Poisson approximation of the distribution of X_a and some technical lemmas. In Section <ref>, we fix ϵ>0 and pick some n with x=x(n) < 1/2-ϵ, so that μ=[X_a]≤ n^1/2 -ϵ. It will follow by a first moment argument that whp all independent a-sets in G_n, 1/2 are disjoint.

The proof now relies on comparing the chromatic numbers of G_n, 1/2 and G_n', 1/2, where n' is slightly larger than n. Specifically, let r=⌊√(μ)⌋=⌊ n^x/2⌋ be roughly the standard deviation of X_a, let n'=n+ a r, and let X_a' be the number of independent a-sets in G_n', 1/2. In Section <ref>, we will see that we can condition G_n, 1/2 and G_n', 1/2 on some typical values for X_a and X_a' which differ by exactly r, and on all independent a-sets being disjoint, so that the chromatic numbers of the conditional random graphs are still in the typical intervals [s_n, t_n] and [s_n', t_n'] with significant probability.

In Section <ref>, we construct a coupling of essentially these two conditional random graph distributions so that the conditional G_n, 1/2 is an induced subgraph of the conditional G_n', 1/2 and their difference can be partitioned into exactly r disjoint independent a-sets. Since the chromatic numbers of these two random graphs then differ by at most r and both lie in the intervals [s_n, t_n] and [s_n', t_n'] with positive probability, this implies s_n'≤ t_n+r or equivalently

    l_n≥ s_n'-s_n-r.

We then use the estimate s_n=f(n)+o ( n/log^ 2n) given in (<ref>). In (<ref>), we will see that

    f(n')-f(n) ≥ r+ Θ( r/log n).

If the error term o(n/log^2 n) in (<ref>) did not exist, this would immediately imply l_n ≥Θ( r/log n). To beat the error term, we repeat the argument in Section <ref>  for a sequence n_1<n_2<n_3<... of integers. Carefully checking that our assumptions remain valid throughout, we find some n^* ⩾ n such that l_n^*⩾Θ(r^*/log n^*) ⩾(n^*)^c. 







 §.§ Preliminaries
 
Recall that a=⌊α_0 ⌋, where α_0=α_0(n) is given in (<ref>), and that we denote by X_a the number of independent a-sets in G_n, 1/2, letting μ=[X_a]=n  a(1/2)^ a  2. 
A standard calculation shows that for any function h=h(n)=O(1) such that α_0-h is an integer, the expected number of independent sets of size α_0-h in G_n, 1/2 is n^h+o(1) (see 3.c in <cit.>). Therefore, as α_0-1 < a ≤α_0,

    μ = n^x    for some function    x=x(n) ∈ [o(1), 1+o(1)]

which satisfies 
    x= α_0-a+o(1)=α_0-⌊α_0 ⌋ +o(1).



Since α_0(n)→∞ and (α_0(n+1)-α_0(n)) → 0 as n →∞, the following lemma is immediate.
 
Let 0 ≤ c_1 < c_2 ≤ 1 and N>0. There is an integer n ≥ N such that

    x(n) ∈ (c_1, c_2),

where x(n) is given by (<ref>).
The Stein-Chen method (see for example 4 in <cit.>) can be used to obtain some very accurate information about the distribution of X_a. For this, if W,Z are two random variables taking values in a countable set Ω, let

    (W,Z) = sup_A ⊂Ω|(W ∈ A) - (Z ∈ A) |

denote their total variation distance. For λ>0, denote by _λ the Poisson distribution with mean λ. The following lemma is a special case of Theorem 11.9 in <cit.>.
Let Z ∼_μ, then if μ≥1, 

    (X_a,Z)  =O (μ(log n)^4/n^2+(log n)^3/n )=o(1).

We will also need a technical lemma about the Poisson distribution, a proof is given in the appendix.  
 For an integer k and A ⊂, let A-k = {a-k | a ∈A}. 
  
 Let (λ_n)_n be a sequence with 0<λ_n →∞, and suppose that (B_n)_n is a sequence of integer sets such that
 
    _λ_n(B_n ) → 0.

Then also

    _λ_n(B_n-⌊√(λ_n)⌋) → 0.





 §.§ Selection of typical values
 
Now let 0<ϵ<1/4 be fixed, and suppose that n is an integer such that

    ϵ < x =x(n) < 1/2 -ϵ,

or equivalently n^ϵ < μ < n^1/2 -ϵ (infinitely many such values n exist by Lemma <ref>). Let 

    r=  ⌊ n^x/2⌋ and   n'=n+ra.

For the rest of subsections <ref> and <ref>, whenever we write a, α_0, μ and x, this refers to a(n), α_0(n), μ(n) and x(n), respectively. Let  a'=a(n'), α_0'=α_0(n') and μ'=μ(n') (where μ' is defined with respect to a').

Note that 

    α_0'=α_0+O(r a/n)=α_0+o(1).

In particular, as α_0-a=x+o(1) is bounded away from 0 and 1 by (<ref>) and (<ref>), if n is large enough we have

    a'=⌊α_0'⌋ =⌊α_0⌋=a.


As μ=n^x, r=O(n^x/2), a=O(log n) and x< 1/2, if n is large enough,

    μ'=n'  a( 1/2)^a  2=μ ∏_i=0^a-1n'-i/n-i =μ(1+O(ra/n))^a=μ(1+ O( r a^2/n)) = μ+o(1).

In particular, an easy (and well-known) calculation shows that

    (_μ, _μ') =o(1).

Recall that X_a' denotes the number of independent a-sets in G_n', 1/2, then together with Lemma <ref>, it follows that X_a and X_a' have essentially the same distribution.
 (X_a, _μ)=o(1) and (X_a', _μ)=o(1).

We would like to compare the chromatic numbers of G_n, 1/2 and G_n', 1/2, each conditioned on having “typical” numbers of independent a-sets which differ by exactly r, and conditioned on the event that all independent a-sets are disjoint (which holds whp). The content of the following lemma is that we can pick two such typical values for X_a and X_a' so that, after conditioning, the chromatic numbers of G_n, 1/2 and G_n', 1/2 still lie in their typical intervals with significant probability.
 
Let G ∼ G_n, 1/2 and G' ∼ G_n', 1/2. 
Let E and E' be the events that all independent a-sets in G  and G' are disjoint, respectively. Then, if n is large enough, there is an integer A=A(n) ∈ [1/2n^x, 2n^x]   
such that

    ( χ(G) ∈ [s_n, t_n]   |   {X_a = A}∩E) > 3/4   and 
       ( χ(G') ∈ [s_n', t_n']   |   {X_a'=A+r}∩E') > 3/4 .



Let 

    F   ={χ(G) ∈ [s_n, t_n]}∩E
    F'    ={χ(G') ∈ [s_n', t_n']}∩E'.

Then (since ( A  |  B ∩ C) ≥ ( A ∩ B  |  C) for any events A, B, C and probability distribution ), it suffices to show that there is a value A such that 

    (F  |   X_a = A )    > 3/4   and 
    ( F'   |   X_a'=A+r)    > 3/4 .

As μ=n^x with x< 1/2 - ϵ and μ'=μ+o(1), an easy first moment calculation (for the number of pairs of independent a-sets which share between 1 and a-1 vertices — this is similar to the proof of Theorem 4.5.1 in <cit.>) shows that the events E and E' both hold whp, and so the events F and F' also hold whp. 

Let A be the set of values A for which (<ref>) holds, and let A' be the set of values A for which (<ref>) holds. Then as

    o(1) =  (F^c )    ≥∑_A ∉ A( (F^c   |   X_a = A ) (X_a = A) ) ≥1/4   (X_a ∉A)    and 
    
    o(1) =  ((F')^c )    ≥∑_A ∉ A'( ((F')^c   |   X'_a = A+r ) (X'_a = A+r) )  ≥1/4   (X_a' ∉A'+r),

whp X_a ∈A and X_a' ∈A' +r.

Therefore, by Lemma <ref>, _μ(A)=1-o(1) and _μ(A'+r)=1-o(1). From Lemma <ref> (applied to B_n = ( A '+r)^c, noting that B_n - r =  A'^c), it follows that also _μ(A')=1-o(1), and so

    _μ(A∩A')=1-o(1).

Since μ> n^ϵ→∞,  by Chebyshev's inequality _μ( [1/2μ, 2μ] ∩_0)= 1-o(1). In particular, A∩A' ∩ [1/2μ, 2μ] is non-empty, so there is at least one A ∈ [1/2μ, 2μ] which fulfils  (<ref>) and (<ref>).




 §.§ Coupling the conditional distributions
 
Given an event P, denote by G_n,p|_ P the distribution of the random graph G_n,p conditional on P. The key ingredient of the proof is a construction of a coupling of essentially the two conditional distributions 

    G_n,1/2|_{X_a=A}∩E   and    G_n', 1/2|_{X_a'=A+r}∩E'

from Lemma <ref>, so that the conditional G_n, 1/2 is an induced subgraph of the conditional G_n', 1/2 and their difference can be partitioned into r independent a-sets.

For this, let V'=[n'], fix some arbitrary disjoint a-sets 

    S_1, …, S_A+r⊂ V',

as shown in Figure <ref>, and let 

    V=V'∖⋃_i=1^r S_i.

Include every edge between vertices in V' independently with probability 1/2, and consider the following events.


    𝒟_1 :     The a-sets S_1, …, S_r are independent.
    𝒟 _2 :     The a-sets S_r+1, …, S_r+A are independent.
    𝒰_1 :     There are no independent a-sets with at least one vertex in V' ∖ V, other than the a-sets
        S_1, …, S_r (which may or may not be independent).
    𝒰_2 :     There are no independent a-sets completely contained in V, other than the a-sets
        S_r+1, …, S_r+A (which may or may not be independent).

Note that U_1 and U_2 are up-sets, and D_1 and D_2 are principal down-sets (that is, D_1 and D_2 are events defined by forbidding a specific fixed edge set). Now condition on the event 

    D_1 ∩ D_2 ∩ U_1 ∩ U_2

that exactly the A+r disjoint a-sets S_1, …, S_A+r are independent and no others. Call the resulting random graph H', and let H=H'[V] be the induced subgraph of H' on the vertex set V. By construction, H is a graph on n vertices with exactly A disjoint independent a-sets, H' is a graph on n' vertices with exactly A+r disjoint independent a-sets, and V' ∖ V can be partitioned into r disjoint independent a-sets.





It is not hard to see that, up to a random vertex permutation, H' has exactly the required distribution.
  Let Ĥ' be the random graph obtained from H' by a uniform random permutation of the vertex labels in V'. Then
 Ĥ' ∼ G_n', 1/2|_{X_a'=A+r}∩E'. 


Consider the random graph G_n', 1/2 conditioned on {X_a'=A+r}∩E'. The set of all possible graphs on n' vertices with exactly A+r disjoint independent a-sets is the disjoint union of all such graphs where exactly A+r fixed disjoint independent a-sets are specified. In the conditional G_n', 1/2, every such fixed collection of A+r disjoint independent a-sets is equally likely (by symmetry).

Starting with the fixed collection S= {S_1, …, S_A+r} of a-sets, if π is a uniform random permutation of V', then the image π( S) is uniformly distributed amongst all collections of A+r disjoint a-sets. Therefore, if we start by conditioning G_n', 1/2 on having exactly the independent a-sets in S — which is the distribution of H' — and then apply the random vertex permutation π, we recover the distribution G_n', 1/2|_{X_a'=A+r}∩E'.

Unfortunately, we cannot argue in the same way for H. If we obtain Ĥ from H by randomly permuting the vertex labels in V, then Ĥ does not have exactly the conditional distribution G_n, 1/2 |_{X_a=A}∩ E. This is because the distribution of H is also conditional on the event U_1 that there are no other independent a-sets with at least one vertex in V' ∖ V.

However, as the expected number of such independent a-sets is small, the distributions are similar and we can bound probabilities in H by the corresponding probabilities in G_n, 1/2|_{X_a=A}. This can be deduced in several ways; the elegant formulation in Claim <ref> below was given by Oliver Riordan. 
 
 Let B be an event for the set of graphs with vertex set V which is invariant under the permutation of vertex labels. Then 
 
    (H ∈ B) ≤ (1+o(1)) ( G_n, 1/2|_{X_a=A}∩E∈ B ) .



By the same argument as in Claim <ref>, if we condition only on D_2 ∩U_2 and randomly permute the vertex labels of V, then the resulting random graph on V has exactly the distribution G_n, 1/2|_{X_a=A}∩E. Therefore, as B is invariant under the permutation of vertex labels,

    ( G_n, 1/2|_{X_a=A}∩E∈ B ) = (B| D_2 ∩ U_2).

The event D_1 is independent from B, D_2 and U_2 (as they depend on disjoint sets of edges), and so

    ( G_n, 1/2|_{X_a=A}∩E∈ B ) = (B|D_1 ∩ D_2 ∩ U_2).

Now note that

    ( H ∈ B)    = (B| D_1 ∩ D_2 ∩ U_1 ∩ U_2) = (B∩ U_1 | D_1 ∩ D_2 ∩ U_2)/( U_1 | D_1 ∩ D_2 ∩ U_2)≤(B| D_1 ∩ D_2 ∩ U_2)/( U_1 | D_1 ∩ D_2 ∩ U_2).

So to prove the claim, it suffices to show that ( U_1 | D_1 ∩ D_2 ∩ U_2) = 1-o(1). Note that D_1 and D_2 are principal down-sets, so after conditioning on D_1 ∩ D_2, we still have a product probability space (for all the remaining edges which are not involved in  D_1 ∩ D_2). As U_1 and U_2 are up-sets, by applying Harris' lemma to the aforementioned product space,

    ( U_1 | D_1 ∩ D_2 ∩ U_2) ≥( U_1 | D_1 ∩ D_2).

So it suffices to show that ( U_1^c | D_1 ∩ D_2)=o(1). Note that U_1^c is the event that there is at least one independent a-set, other than  S_1, …, S_r, with at least one vertex in V' ∖ V. Let Y denote the number of such sets. In Lemma <ref> below, we will show by a straightforward but slightly involved calculation that

    [Y | D_1 ∩ D_2]=o(1).

This implies ( U_1^c | D_1 ∩ D_2)=o(1) as required.

For the proof of Claim <ref> it remains to verify (<ref>).

 Let Y be as in the proof of Claim <ref>, then  [Y | D_1 ∩ D_2]=o(1).


We use the following notation below. For two functions f, g: →, we write f= O^*(g) if there are constants C and n_0 such that |f(n)| ≤ (log n)^C g(n) for all n≥ n_0. We write f = Θ^*(g) if f = O^*(g) and g= O^*(f).

Consider a potential a-set T counted in Y. Then T can be written as the disjoint union 

    T= ⋃_j=1^M T_j ∪ T_rest

where M ≥ 1, T_j ⊂ S_i_j for some i_j ∈{1, …, A+r}, and T_rest⊂ V. We can assume i_1 < … < i_M and i_1 ∈ [r] (as T has at least one vertex in V' ∖ V=⋃_i=1^r S_i) and that the sets T_j are non-empty for all 1≤ j ≤ M. As T cannot be identical to any of the sets S_1, …, S_A+r, letting t_j=|T_j|, we have for all 1≤ j ≤ M,

    1 ≤ t_j ≤ a-1.

Let T be the set of all pairs (M, t), where 1≤ M ≤ a is an integer and t=(t_1, …, t_M) is a sequence of integers with 1≤ t_j≤ a-1 for all j, and ∑t_j≤ a. Starting with some (M, t) ∈ T, an a-set T corresponding to (M, t) is defined by choosing i_1∈ [r], {i_2, …, i_M }⊂ [A+r], T_j⊂ S_t_j for all 1 ≤ j ≤ M and T_rest⊂ V. So the number of a-sets T corresponding to (M, t) is at most

    rA+r  M-1(∏_j=1^M a  t_j)n  a- ∑_j=1^M t_j≤r/A+rn  a∏_j=1^M  (A+r)a  t_ja!/(a-t_j)!(n-a)^t_j,

using A+r  M-1≤ (A+r)^M-1 and bounding

    n  a-∑_j t_j/n  a = a!(n-a)!/(a-∑_j t_j)!(n-a+∑_j t_j)!≤∏_j=1^M a!/(a-t_j)!(n-a)^t_j.

Condition on D_1 ∩ D_2, that is, on the event that none of the (A+r)a  2 edges within the a-sets S_1, …, S_A+r are present. Then conditional on D_1 ∩ D_2, a given a-set T is independent with probability exactly 2^-a  2+∑_jt_j  2. Therefore, with (<ref>),

    [Y | D_1 ∩ D_2 ]    ≤r/A+rn  a2^-a  2∑_(M, t)∈ T∏_j=1^M (A+r)a  t_ja! 2^t_j  2/(a-t_j)!(n-a)^t_j =  r μ/A+r∑_(M, t)∈ T∏_j=1^M σ_t_j,

where

    σ_t =   (A+r)a  ta! 2^t  2/(a-t)!(n-a)^t .

Note that, as n  a-12^-a-1  2=Θ(n/log n) n  a2^-a  2=Θ(n/log nμ), μ=n^x and by Lemma <ref>, A=O(n^x),

    σ_1    = Θ(n^x a^2/n)= Θ^*(n^x-1),
    σ_a-1   =O (n^x a ) a!2^a-1  2/(n-a)^a-1 = O^*( n^x /n  a-12^-a-1  2)=O^* (n^x-1/μ) =O^*(n^-1)=o(n^x-1).

Considering the ratio  σ_t+1/σ_t =(a-t)^22^t/(t+1)(n-a) (which is O^*(n^-1) for t=O(1), then increases and reaches Θ^* ( n) for t=a-O(1)), it is not hard to see that for all 1 ≤ t ≤ a-1,

    σ_t ≤max(σ_1, σ_a-1) =σ_1=O^*(n^x-1).

So from (<ref>), as 1 ≤ t_j ≤ a-1, μ=n^x, r=O(n^x/2), A=Θ(n^x) and x<1/2,

    [Y | D_1 ∩ D_2 ] ≤r μ/A+r∑_(M, t)∈ Tσ_1^M ≤r μ/A+r∑_M ≥ 1(a^M σ_1^M )=O^* (r μσ_1/A+r) = O^* (n^3/2x-1)=o(1).







As  the chromatic number of a graph is invariant under the permutation of vertex labels, it follows from Claim <ref> and Lemma <ref> that

    ( χ(H') ∈ [s_n', t_n'] )>3/4.

From Claim <ref> (applied to the event B={χ(H) ∉ [a_n, b_n]}) and Lemma <ref>, it follows that

    ( χ(H) ∈ [s_n, t_n] ) > (1+o(1)) ·3/4>1/2

if n is large enough. But as V' ∖ V is the union of the independent a-sets S_1, …, S_r, we also have

    χ(H') ≤χ(H)+r.

So with probability at least 1/4,

    s_n'≤χ(H') ≤χ(H)+r ≤ t_n+r .

The left-hand side and the right-hand side are simply functions of n, not random variables, so it follows that, deterministically,

    s_n'≤  t_n+r

and therefore

    l_n=t_n-s_n ≥ s_n'-s_n-r.




 §.§ Finishing the proof
 

Let us summarise our progress so far in the following lemma. Recall the definitions of s_n and l_n given at the beginning of Section <ref>, and of the functions a(n), μ(n) and x(n) in Section <ref>.

For every fixed ϵ∈ (0,1/4), if n is large enough (i.e. if n≥ N_ϵ for some N_ϵ>0) and

    n^ϵ≤μ(n) ≤ n^1/2 - ϵ   or equivalently   ϵ≤ x(n) ≤1/2 - ϵ,

then, 
letting r=r(n)=⌊ n^x(n)/2⌋ and n'=n+a(n)r,

    l_n  ≥ s_n'-s_n-r.
 
Recall from  (<ref>) that s_n=f(n)+o( n/log^2 n). With n and n' as in Lemma <ref>, by a straightforward calculation which can be found in the appendix, if n is large enough,

    f(n')-f(n) = r(n)+ (1-x(n)+o(1))r(n)/a(n)  >  r(n)+ r(n)/2a(n).


If we had equality in the estimate s_n ≈ f(n), without the additive error term o( n/log^2 n), then together with Lemma <ref>, this would imply l_n ≥Θ( r(n)/log n). To tackle the error term, we will apply Lemma <ref> to a sequence of values (n_i)_i≥ 1.

To this end, let c ∈(0, 1/4) be a constant, and let 

    ϵ=1/4(1/4-c) < 1/16.

By Lemma <ref>, there is an arbitrarily large integer n_1 such that

    2ϵ < 1/2-4 ϵ< x(n_1) < 1/2 -3ϵ.

Note that by (<ref>), α_0(n_1)=a(n_1)+x(n_1)+o(1)< a(n_1)+1/2-3 ϵ+o(1). Let M be the largest integer such that for all n_1 ≤ n ≤ M,

    α_0(n) < a(n_1)+1/2 - 2ϵ.

For n_1 large enough, it follows from the definition (<ref>) of α_0 that

    M-n_1 =Θ (n_1).

Furthermore, if n_1 is large enough, then for all n_1 ≤ n ≤ M,

    α_0(n_1)    ≤α_0(n) ≤α_0(M), 
    
     a(n)   = ⌊α_0(n)+o(1) ⌋ = a(n_1)   by (<ref>), 
    ϵ < 2ϵ+o(1)<x(n_1) ≤ x(n)    ≤1/2 - 2ϵ+o(1) < 1/2 -ϵ   by (<ref>), (<ref>) and (<ref>); and so
    
     n^ϵ   < μ(n) < n^1/2 -ϵ.

Let a=a(n_1). We inductively define a sequence of integers: for i ≥ 1, let x_i=x(n_i), r_i= ⌊ n^x_i/2⌋ and

    n_i+1= n_i + r_i a.

Let i_max be the largest index so that n_i_max≤ M. Note that if n_1 is large enough, by (<ref>),

    n_i_max-n_1 = Θ (n_1).

Now by the properties stated in (<ref>), if n_1 is large enough, we may apply Lemma <ref> to every pair (n_i, n_i+1) where 1 ≤ i < i_max. Let s_i=s_n_i, t_i= t_n_i and l_i=l_n_i, then

    l_i≥ s_i+1-s_i-r_i  for all 1≤ i < i_max.

Therefore,

    ∑_i=1^-1l_i ≥ s_-s_1 -∑_i=1^-1 r_i.

By (<ref>), if n_1 is large enough, for all 1 ≤ i <,

    f(n_i+1)-f(n_i) > r_i+  r_i/2a,

and so by (<ref>) and (<ref>), and as n_i_max=Θ(n_1) by (<ref>),

    s_-s_1=f(n_)-f(n_1)+o(n_1/log^2 n_1)> ∑_i=1^-1(r_i+ r_i/2a) +o(n_1/log^2 n_1).

Together with (<ref>), this gives

    ∑_i=1^-1 l_i >  ∑_i=1^-1r_i/2a +o(n_1/log^2 n_1).

Note that by (<ref>) and (<ref>),

    ∑_i=1^-1r_i/a = n_-n_1/a^2=Θ(n_1/a^2)=Θ(n_1/log^2 n),

and so, if n is large enough,

    ∑_i=1^-1 l_i >  ∑_i=1^-1r_i/2a +o(n_1/log^2 n)  ≥∑_i=1^-1r_i/3a.

In particular, there is some index 1≤ i^* < such that, letting n^*=n_i^*,

    l_n^* > r_i^*/3a.

(In fact, there are either many indices i with l_n_i > r_i/10a, say, or some i where l_i is very long.)
By (<ref>), r_i^*=⌊(n^*)^x(n^*)/2⌋≥⌊(n^*)^x(n_1)/2⌋. So by (<ref>) and (<ref>), if n_1 is large enough,

    l_n^* > (n^* )^1/4 - 4 ϵ=(n^*)^c,

so we have found an integer n^* with l_n^*>(n^* )^c as required. 




§ REMARKS AND OPEN QUESTIONS
 


  
  * As a corollary of Theorem <ref>, the same conclusion holds for the random graph G_n,m with m= ⌊ n^2/4 ⌋, which was pointed out by Alex Scott. This is because we can couple the random graphs G_n,m and G_n, 1/2 so that whp their chromatic numbers differ by at most ω(n)log n for any function ω(n) →∞. 
  For this, start with G_n,m and independently sample E ∼(n  2, 1/2). Now either add E-m edges to or remove m-E from G_n,m uniformly at random, so that the total number of edges is E. The new graph has the distribution G_n,1/2, and it is not hard to show that whp this changes the chromatic number by at most ω(n)log n. (Note that in both G_n,m and G_n, 1/2, an optimal colouring consists of O ( n/log n) colour classes of size O (log n). If we add |E-m|≤  n √(ω(n)) random edges, then whp at most ω(n) log n of these to “spoil” a given optimal colouring, which can be “fixed” by adding at most ω(n) log n new colours.)  

  * Of course X_a is not whp contained in any sequence of intervals of length less than n^1/2 - ϵ for any fixed ϵ>0, because there are infinitely many values n where x(n) > 1-ϵ. We conjecture that the same is true for χ(G_n, 1/2). This exponent would match the upper bound for the concentration of χ(G_n, p) given by Shamir and Spencer <cit.>.

In the proof of Theorem <ref>, we only consider the case x(n) <1/2 - ϵ because then whp all independent a-sets in G_n, 1/2 are disjoint. It is possible that the coupling argument could be refined to show that there is some interval [s_n, t_n] of length at least n^1/2 - ϵ. 
 
  * While Theorem <ref> was only proved for p=1/2, the same proof works for any constant p ∈ (0, 1-1/e^2]. For p>1-1/e^2, there are some additional technical difficulties because the estimate for χ(G_n,p) given in <cit.> differs from the one in Theorem <ref>, and we have not attempted this case.
 
It would be interesting to see whether the argument could be generalised to other ranges p=p(n). As Alon and Krivelevich <cit.> proved two point concentration for p< n^-1/2-ϵ, this would be particularly interesting for p close to n^-1/2.
 

  * It should be noted that the proof of Theorem <ref> required a fairly good estimate for χ(G_n, 1/2). The error bound in Theorem <ref> is of size o (n/log^2 n), which is used in (<ref>), and the proof would not have worked with an error bound of size O(  n/log^2 n). Therefore, to extend the result to other ranges of p, we might first need similarly accurate bounds for χ(G_n,p).
 
 
 
  * Theorem <ref> only implies that for any constant c< 1/4, there are some values n where l_n > n^c. It could still be the case that χ(G_n, 1/2) is very narrowly concentrated on a subsequence of the integers. Can we find a lower bound for l_n which holds for all large enough n?
 
 
  * Ultimately, it would 
 be very nice to establish the correct exponent for the concentration of χ(G_n, 1/2), and it seems likely that this exponent varies with n. In other words, can we find a function ρ(n) such that for any fixed ϵ>0, χ(G_n,p) is whp contained in some sequence of intervals of length n^ρ(n)+ϵ, but for any sequence of intervals I_n of length at most n^ρ(n)-ϵ, if n is large enough, 
  
    ( χ(G_n, 1/2) ∈ I_n ) < 1/2?





§ ACKNOWLEDGEMENTS

The work in this paper was completed during the Oberwolfach workshop “Combinatorics, Probability and Computing”, and I am grateful to the MFO institute for their hospitality. I would like to thank Oliver Riordan for many discussions and suggestions which simplified 
the coupling argument considerably, as well as David Conlon, Eoin Long, Konstantinos Panagiotou and Lutz Warnke for several helpful discussions and remarks on earlier versions of this paper. I would also like to thank the anonymous referees for their detailed comments and suggestions which greatly improved the presentation of the paper.
 plainnat
 
 
 
 26


urlstyle

[Achlioptas and Naor(2005)]achlioptas2005two
D. Achlioptas and A. Naor.
The two possible values of the chromatic number of a random graph.
Annals of Mathematics, 162:0 1335–1351, 2005.

[Alon and Krivelevich(1997)]alon1997concentration
N. Alon and M. Krivelevich.
The concentration of the chromatic number of random graphs.
Combinatorica, 170 (3):0 303–313, 1997.

[Alon and Spencer(1992)]alonspencerfirstedition
N. Alon and J. Spencer.
The Probabilistic Method (With an Open Problems Appendix by
  Paul Erdős).
Wiley, New York, first edition, 1992.

[Alon and Spencer(2015)]alonspencer
N. Alon and J. Spencer.
The Probabilistic Method.
Wiley, 4th edition, 2015.

[Bollobás(1988)]bollobas1988chromatic
B. Bollobás.
The chromatic number of random graphs.
Combinatorica, 80 (1):0 49–55, 1988.

[Bollobás(2001)]bollobas:randomgraphs
B. Bollobás.
Random Graphs.
Cambridge University Press, second edition, 2001.

[Bollobás(2004)]bollobas:concentrationfixed
B. Bollobás.
How sharp is the concentration of the chromatic number?
Combinatorics, Probability and Computing, 130
  (01):0 115–117, 2004.

[Bollobás and Erdős(1976)]erdoscliques
B. Bollobás and P. Erdős.
Cliques in random graphs.
In Mathematical Proceedings of the Cambridge Philosophical
  Society, volume 80, pages 419–427. Cambridge University Press, 1976.

[Chung and Graham(1998)]chung1998erdos
F. Chung and R. Graham.
Erdős on Graphs: his legacy of unsolved problems.
AK Peters/CRC Press, 1998.

[Coja-Oghlan et al.(2008)Coja-Oghlan, Panagiotou, and
  Steger]coja2008chromatic
A. Coja-Oghlan, K. Panagiotou, and A. Steger.
On the chromatic number of random graphs.
Journal of Combinatorial Theory, Series B, 980
  (5):0 980–993, 2008.

[Erdős and Rényi(1959)]erdos1959random
P. Erdős and A. Rényi.
On random graphs, I.
Publicationes Mathematicae Debrecen, 6:0 290–297,
  1959.

[Erdős and Rényi(1960)]erdos1960evolution
P. Erdős and A. Rényi.
On the evolution of random graphs.
Publications of the Mathematical Institute of the Hungarian
  Academy of Sciences, 5:0 17–61, 1960.

[Fountoulakis et al.(2010)Fountoulakis, Kang, and
  McDiarmid]fountoulakis2010t
N. Fountoulakis, R. Kang, and C. McDiarmid.
The t-stability number of a random graph.
The Electronic Journal of Combinatorics, 170
  (1):0 R59, 2010.

[Glebov et al.(2015)Glebov, Liebenau, and
  Szabó]glebov2015concentration
R. Glebov, A. Liebenau, and T. Szabó.
On the concentration of the domination number of the random graph.
SIAM Journal on Discrete Mathematics, 290
  (3):0 1186–1206, 2015.

[Grimmett and McDiarmid(1975)]grimmett1975colouring
G. R. Grimmett and C. McDiarmid.
On colouring random graphs.
In Mathematical Proceedings of the Cambridge Philosophical
  Society, volume 77, pages 313–324. Cambridge University Press, 1975.

[Heckel(2018)]heckel2018chromatic
A. Heckel.
The chromatic number of dense random graphs.
Random Structures & Algorithms, 530 (1):0
  140–182, 2018.

[Janson et al.(2000)Janson, Łuczak, and
  Ruciński]janson:randomgraphs
S. Janson, T. Łuczak, and A. Ruciński.
Random Graphs.
Wiley, New York, 2000.

[Kang and McDiarmid(2015)]mcdiarmidsurvey
R. Kang and C. McDiarmid.
Colouring random graphs.
In Topics in Chromatic Graph Theory, volume 156 of
  Encyclopedia of Mathematics and Its Applications, pages 199–229.
  Cambridge University Press, 2015.

[Łuczak(1991)]luczak1991note
T. Łuczak.
A note on the sharp concentration of the chromatic number of random
  graphs.
Combinatorica, 110 (3):0 295–297, 1991.

[Matula(1970)]matula1970complete
D. Matula.
On the complete subgraphs of a random graph.
In Proceedings of the 2nd Chapel Hill Conference on
  Combinatorial Mathematics and its Applications (Chapel Hill, NC, 1970),
  pages 356–369, 1970.

[Matula(1972)]matula1972employee
D. Matula.
The employee party problem.
Notices of the American Mathematical Society, 190
  (2):0 A–382, 1972.

[McDiarmid(1989)]mcdiarmid1989method
C. McDiarmid.
On the method of bounded differences.
Surveys in Combinatorics, 1410 (1):0 148–188,
  1989.

[Panagiotou and Steger(2009)]panagiotou2009note
K. Panagiotou and A. Steger.
A note on the chromatic number of a dense random graph.
Discrete Mathematics, 3090 (10):0 3420–3423,
  2009.

[Ross(2011)]ross2011fundamentals
N. Ross.
Fundamentals of Stein's method.
Probability Surveys, 8:0 210–293, 2011.

[Scott(2008)]scott2008concentration
A. Scott.
On the concentration of the chromatic number of random graphs.
Available at arxiv.org/abs/0806.0178, 2008.

[Shamir and Spencer(1987)]shamir1987sharp
E. Shamir and J. Spencer.
Sharp concentration of the chromatic number on random graphs
  G_n,p.
Combinatorica, 70 (1):0 121–129, 1987.





§ APPENDIX






  §.§.§ Proof of Lemma <ref>

To simplify notation, we write λ instead of λ_n. Let r= ⌊√(λ)⌋ and fix ϵ>0. Then it suffices to show that there is some δ=δ(ϵ)>0 such that, if n and therefore λ is large enough, for all sets B with _λ(B) <δ we have

    _λ(B- r ) <ϵ.

So let δ>0 be small enough so that 

    log(ϵ/2δ)> √(3/ϵ)+1,

and pick some 

    t ∈( √(3/ϵ)+1,  log(ϵ/2δ)).

Suppose that B is a set of integers with _λ(B) <δ. For s>0, let 

    I_s= [λ-sr, λ+s r ]∩,

and consider B_1=B∖ I_t and  B_2=B∩ I_t. Note that I_t-1⊂I_t-r, so B_1 -r ⊂ I_t^c-r ⊂ I_t-1^c. So by Chebyshev's inequality and (<ref>), if λ is large enough,

    _λ (B_1-r) ≤_λ (I_t-1^c) ≤λ/(t-1)^2r^2 < ϵ/2.

Now consider some k ∈B_2. If k-r<0, we have _λ({k-r})=0, so in particular

    _λ ({k-r}) ≤ϵ/2δ_λ({k}).

Otherwise, as k ≤λ+t r ≤λ + t√(λ), by (<ref>), 

    _λ ({k-r})/_λ ({k})  =  k!/λ^r(k-r)!≤( k/λ)^r ≤( 1+t/√(λ))^√(λ)≤ e^t< ϵ/2δ.

 Therefore, together with (<ref>),
 
    _λ (B_2-r) ≤ϵ/2δ_λ (B_2)≤ϵ/2δ_λ (B) < ϵ/2 .

 Together with (<ref>), this proves the claim.





  §.§.§ Proof of (<ref>)

First note that 

    f(n)=n/2 log_2 n - 2 log_2 log_2 n-2=n/α_0(n)-1-2/log 2
    .

Now

    α_0(n')-α_0(n) ∼ 2 log_2 n' - 2 log_2 n = 2/log 2log(1+ar/n) ∼2ar/n log 2=o(1).

Note that

    f(n')-f(n)   = n'-n/α_0(n')-1-2/log 2 +(n/α_0(n')-1-2/log 2-n/α_0(n)-1-2/log 2).

For the first term in (<ref>), since α(n')=α(n)+o(1)=a+x+o(1) by (<ref>),

    n'-n/α_0(n')-1-2/log 2=ar/a+x-1 -2/log 2+o(1)= r+ (1+2/log 2-x )r/a +o (r/a).

For the second term in (<ref>), note that by (<ref>),

    n/α_0(n')-1-2/log 2-n/α_0(n)-1-2/log 2   = n/α_0(n)-1-2/log 2+2ar/n log 2+o (ar/n)-n/α_0(n)-1-2/log 2
       ∼-2ar/log 2/α_0(n)^2∼-2r/alog 2

as α_0(n) ∼ a. Together with (<ref>) and (<ref>), this gives

    f(n')-f(n)= r+(1-x )r/a +o (r/a).
