Nikolaos Fountoulakis

Colin Mcdiarmid

Upper bounds on the non-3-colourability threshold of random graphs

Keywords: sparse random graphs, 3-colourability, thresholds

We present a full analysis of the expected number of 'rigid' 3-colourings of a sparse random graph. This shows that, if the average degree is at least 4.99, then as n → ∞ the expected number of such colourings tends to 0 and so the probability that the graph is 3-colourable tends to 0. (This result is tight, in that with average degree 4.989 the expected number tends to ∞.) This bound appears independently in Kaporis et al. [14]. We then give a minor improvement, which shows in particular that the probability that the graph is 3-colourable tends to 0 if the average degree is at least 4.989.

Introduction

We are concerned with the 3-colourability of sparse random graphs. We consider the G n,m model (also known as the uniform model), where m = ⌈θn/2⌉. This consists of all graphs with vertex set V n = {1, 2, . . . , n} which have m edges, where each of these graphs occurs with probability ( n 2 )

m -1
. Note that the expected degree of a vertex is θ + o [START_REF] Achlioptas | A sharp threshold for k-colourability[END_REF] as n → ∞. We say that a graph property holds asymptotically almost surely (aas) if the probability that the random graph of order n has this property tends to 1 as n → ∞.

The threshold for non-2-colourability (that is, for the existence of an odd circuit) is well understood, and is not sharp, see for example the recent survey of Molloy [START_REF] Molloy | Thresholds for colourability and satisfiability in random graphs and boolean formulae[END_REF]. For k > 2 our understanding of k-colourability is less complete. Let χ(G) denote the chromatic number of a graph G. Erdős in [START_REF] Erdös | On the evolution of random graphs[END_REF][START_REF] Alon | The Probabilistic Method[END_REF] asked whether for each k ≥ 3 there exists a constant θ k such that for any ε > 0, χ(G n,m ) ≤ k aas when m ≤ (θ k /2 -ε)n, and χ(G n,m ) > k aas when m ≥ (θ k /2 + ε)n. Note that θ k would specify a critical average degree for the random graph. In the case of 3-colourability, the experiments in [START_REF] Hogg | The hardest constrained problems: a double phase transition[END_REF] suggest that θ 3 ≃ 4. [START_REF] Bunday | Basic Optimisation Methods[END_REF].

Recently Achlioptas and Friedgut [START_REF] Achlioptas | A sharp threshold for k-colourability[END_REF] gave a partial answer to the above question. They showed that for each fixed k ≥ 3, there exists a function d k (n) such that for any ε > 0, χ(G n,m ) ≤ k aas when m = m(n) ≤ d k (n) 2 -ε n, and χ(G n,m ) > k aas when m ≥ d k (n) 2 + ε n. It is widely believed that lim n→∞ d k (n) exists, but confirming this conjecture and determining the limit θ k seems challenging. Let Then θ - k ≤ θ + k and the two are equal if and only if the answer to the question of Erdős is positive. Let us return to the case k = 3. There are many results concerning lower bounds on θ - 3 ; in other words showing that for a certain value of θ, we have χ(G n,m ) ≤ 3 aas if m = m(n) ≤ θn/2, and so θ - 3 ≥ θ (see [START_REF] Molloy | Thresholds for colourability and satisfiability in random graphs and boolean formulae[END_REF] for a survey on this topic).

There are fewer results concerning upper bounds on θ + 3 , which is our interest here. These upper bounds are based on the following idea. For each graph G on V n let C (G) denote the set of all proper 3-colourings of G using colours 1, 2, 3 ; and let C ′ (G) ⊆ C (G) satisfy C ′ (G) = / 0 whenever C (G) = / 0. We call such a family of colourings adequate. Let us denote |C ′ (G)| by C ′ (G): we shall adopt such notation throughout the paper. By Markov's inequality,

P(χ(G n,m ) ≤ 3) ≤ E[C ′ (G n,m )]. (1)
Of course equality holds here if C ′ (G) ≤ 1 always. The aim is to find a small adequate family which is simple enough to handle, and then to use [START_REF] Achlioptas | A sharp threshold for k-colourability[END_REF] to yield an upper bound on θ + 3 .

When we consider all possible 3-colourings, that is we take C ′ (G) = C (G) for each G, we find that

E[C ′ (G n,m )] → 0 as n → ∞ if θ = 5
.41, and so θ + 3 ≤ 5.41. This basic first moment result was improved by Dunne and Zito in [START_REF] Dunne | An improved upper bound on the non-3-colourability threshold[END_REF] to θ + 3 ≤ 5.2057 by considering a certain adequate family; and then further improved by Achlioptas and Molloy [START_REF] Achlioptas | Almost all graphs with 2.522n edges are not 3-colorable[END_REF] to θ + 3 ≤ 5.044 by considering a smaller adequate family, namely the 'rigid' 3-colourings. The idea of considering such colourings came from the success of the method of 'locally maximum' satisfying truth assignments in [START_REF] Kirousis | Approximating the unsatisfiability threshold of random formulas[END_REF] for investigating the unsatisfiability threshold for random 3-SAT problems, see the survey [START_REF] Molloy | Thresholds for colourability and satisfiability in random graphs and boolean formulae[END_REF]. Definition 1 A proper 3-colouring with stable sets S 1 , S 2 , S 3 is called rigid if each vertex in S 2 ∪ S 3 is adjacent to some vertex in S 1 , and each vertex in S 3 is adjacent to some vertex in S 2 .

The above bound from [START_REF] Achlioptas | Almost all graphs with 2.522n edges are not 3-colorable[END_REF] was obtained independently by the authors in [START_REF] Fountoulakis | On the upper bound of the non-3-colourability threshold of random graphs[END_REF]. [In much earlier work [START_REF] Molloy | The chromatic number of sparse random graphs[END_REF], Molloy and Reed took a different approach to improving the basic bound θ + 3 ≤ 5.41: they showed that a random graph of average degree at least 5.142 is aas not 3-colourable by proving that the 3-core of such a random graph is aas not 3-colourable. We do not follow that approach here.] In recent work, Kaporis et al. [START_REF] Kaporis | A note on the non-colourability threshold of a random graph[END_REF] give a tighter estimate of the expected number of rigid 3-colourings, and obtain θ + 3 ≤ 4.99. We obtained this result independently and concurrently (see [START_REF] Fountoulakis | On the upper bound of the non-3-colourability threshold of random graphs[END_REF]), and present here a more complete analysis of the expected number of rigid 3-colourings, which shows in particular that the last bound cannot be improved, in the sense that with average degree 4.989 the expected number of rigid 3-colourings tends to ∞. Theorem 1.1 There exist positive real numbers θ 0 < θ 1 such that:

Now

1. The function µ(θ) is continuous on [θ 0 , θ 1 ], and for every θ ∈ [θ 0 , θ 1 ] E [R (G n,m )] = 2 µ(θ)n+O(log n) , ( 2
)
where m = ⌈θn/2⌉. Moreover, µ(θ 0 ) > 0 and µ(θ 1 ) < 0.

We have

4.9893 < θ 0 < θ 1 < 4.9895. (3)
In the above theorem as well as in what follows, the symbol log always refers to binary logarithm. In order to prove this result, one half of the battle is to show [START_REF] Achlioptas | Almost all graphs with 2.522n edges are not 3-colorable[END_REF], and the other half is to show [START_REF] Alon | The Probabilistic Method[END_REF]. The main step in proving (3) is to show that for θ = 4.9895, we have µ(θ) < 0. This involves considerable computation: we are more explicit about this side of matters than has been the custom in previous papers in this area.

From the previous theorem and the Markov inequality (1) we obtain Therefore, θ + 3 ≤ 4.9895. Working from the foundation provided by Theorem 1.1, we may try to improve the bound on θ + 3 in different ways. One way involves an adequate subfamily of the rigid 3-colourings, the "Ψ-gadget-free" rigid 3-colourings -see the brief discussion in Section 7. A second way involves considering the number of non-trivial tree components, and using the observation that any non-trivial tree has at least two rigid 3-colourings: this approach is described in Section 6 below, and yields the following theorem. Similar results can be deduced for the G n,p model. In this model, again V n = {1, 2, . . . , n} is the set of vertices, but now each of the n 2 possible edges appears independently with probability p. We find that if θ = 4.98887 and p = θ/n, then there exists a δ > 0 such that P[χ(G n,p ) ≤ 3] ≤ 2 -δn , for n sufficiently large.

The main steps in the proof of Theorem 1.1 are as follows. We first give an exact formula for

E[R(G * n,m )],
where G * n,m is a slight variation of the G n,m model; see Lemma 2.1 below. We show that we can discard the 'tails' of the sum that appears there, and give good approximations to the remaining 'central' terms. These terms involve probabilities p(k, α, n, θ), which are investigated in Section 3. The probabilities can be written as a sum, where the summands involve binomial coefficients and certain 'balls-and-bins' probabilities. Again we show that we can discard the tails in the sums, and give good approximations to the remaining central terms, now involving Stirling numbers of the second kind. We use known asymptotic expressions for these Stirling numbers, thus expressing the summands as terms like 2 h(x,θ)n . This yields an approximation for E[R(G * n,m )] as 2 µ(θ)n+O(log n) (see ( 22) below) and we then obtain [START_REF] Achlioptas | Almost all graphs with 2.522n edges are not 3-colorable[END_REF]. This part of the proof is completed in Section 4.

The remaining work to prove Theorem 1.1 is largely numerical, and is described in Section 5. The main task is to show that for θ = 4.9895, we have µ(θ) < 0. We show that, for this specific θ, h(x, θ) is concave over its domain D. We find numerically a first approximation for a point which gives the maximum value of h inside this area. We define a very fine grid in a box around this point, and find a grid point x where the maximum value of h on the grid is attained. Then, we determine an upper bound for h on the surface of the box (by computing values of h and its partial derivatives on a fine grid and using concavity). We find that this bound is less than the value of h at x, and so we deduce that the box contains the maximum of h over D. Further computations handle the region inside the box.

After completing the proof of Theorem 1.1 as described above, in Section 6 we prove Theorem 1.3, and then we make some brief concluding remarks in Section 7. Some details from earlier proofs are given in the Appendices.

Starting the proofs

For the sake of simplicity, we carry out the probability calculations in the G * n,m model. In this model, we form the random graph by choosing at random m times, each time independently, uniformly and with replacement, an edge out of the n 2 possible 2-subsets of V n = {1, . . . , n}. We ignore any repetitions of an edge, so the random graph may have less than m edges. Our results transfer easily to the G n,m model -see Lemma 4.3 below. Every probability, unless otherwise stated, is meant to be taken over the G * n,m model.

Let D = {(k, α) : 0 ≤ k ≤ 1, 0 ≤ α ≤ k},
and for each positive integer n let

D (n) = D ∩ 1 n Z 2 .
For each

(k, α) ∈ D we define φ(k, α) = k(1 -α) -(k -α) 2 .
Let C (n) be the set of all 3-colourings of V n , i.e. the set of all possible mappings from V n into {1, 2, 3}, or equivalently the set of all partitions of V n into three sets S 1 , S 2 and S 3 (some of them possibly empty).

Also, for each positive integer n and each (k, α) ∈ D (n) , let C (k, α, n) denote the set of all partitions of V n into three sets S 1 , S 2 , S 3 , where

|S 1 | = αn and |S 1 | + |S 2 | = kn. Let p(k, α, n, m) = P[S is rigid| S is proper], (4)
where S ∈ C (k, α, n). Note that the above quantity depends only on the sizes of the independent sets induced by S. Recall that R(G) denotes the number of rigid 3-colourings of G.

Lemma 2.1 For all positive integers n and m with 0

< m ≤ n 2 , E[R(G * n,m )] = (1 - 1 n ) -m ∑ (k,α)∈D (n) n kn kn αn (2φ(k, α)) m p(k, α, n, m).
Proof. By the linearity of the expected value, we have

E[R(G * n,m )] = ∑ S∈C (n) P[S is rigid] = ∑ S∈C (n) P[S is rigid|S is proper] • P[S is proper]. ( 5
)
Let us take a fixed colouring S with stable sets S 1 , S 2 , S 3 , where Hence, e(S) n 2 = (αβ + βγ + γα) = φ(k, α).

s 1 = |S 1 | = αn, s 2 = |S 2 | =
Thus,

P[S is proper] = e(S) n 2 m = (2φ(k, α)) m 1 - 1 n -m
. Now notice that the family C (k, α, n) consists of exactly n kn • kn αn colourings. So, rephrasing the sum in (5) in terms of k and α we obtain the following:

E[R(G * n,m )] = ∑ S∈C (n) P[S is rigid] = 1 - 1 n -m ∑ (k,α)∈D (n) n kn kn αn (2φ(k, α)) m p(k, α, n, m).
✷ The above lemma is our starting point. We next check that in Lemma 2.1 we may ignore the extreme values of α and k. We will split the sum there into two pieces. Let

D 1 = {(k, α) : α ≥ 0.2, k ≤ 0.8, k -α ≥ 0.2} (6)
(which corresponds to α, β, γ ≥ 0.2); and let D

(n) 1 = D 1 ∩ 1 n Z 2 .
Moreover, doing some elementary calculations, we obtain the following:

Lemma 2.2 The function φ(k, α) is continuous and concave on D, for each (k, α) ∈ D we have 0 ≤ φ(k, α) ≤ 1/3, and sup (k,α)∈D\D 1 φ(k, α) = 0.32, min (k,α)∈D 1 φ(k, α) = 0.28. Let S 1 = (1 - 1 n ) -m ∑ (k,α)∈D (n) 1 n kn kn αn (2φ(k, α)) m p(k, α, n, m), ( 7
)
and let

S 2 = (1 - 1 n ) -m ∑ (k,α)∈D (n) \D (n) 1 n kn kn αn (2φ(k, α)) m p(k, α, n, m), so that by Lemma 2.1 E[R(G * n,m )] = S 1 + S 2 . (8)
We will see that the second 'error' term here is negligible for the relevant values of m; and then we may focus on the first term.

S 2 ≤ 2 -δn . Proof. By Lemma 2.2, we have σ = sup (k,α)∈D\D 1 φ(k, α) = 0.32.
Thus, we have

S 2 ≤ ∑ (k,α)∈D (n) \D (n) 1 n kn kn αn n n -1 2φ(k, α) m ≤ 3 n n n -1 2σ θn 2 = n n -1 θn/2 3 (2σ) θ 2 n = O 3 (2σ) θ/2 n . But 3 (0.64) 4.98
2 < 1, and the lemma follows. ✷ The following standard lemma on approximating binomial coefficients may be proved using Stirling's formula:

Lemma 2.4 Let 0 < δ < 1/2. Then uniformly over δn ≤ r ≤ (1 -δ)n we have n r = Θ(n -1/2 ) n r r n n -r n-r = Θ(n -1/2 ) 2 H(r/n) , where H(x) = -x log x -(1 -x) log(1 -x) for 0 ≤ x ≤ 1 (when x = 0 or x = 1, then H(x) = 0) is the entropy function. For m = ⌈θn/2⌉, we set p(k, α, n, θ) = p(k, α, n, m) (9)
(the use of the same letter p should not cause confusion). Directly from the definition [START_REF] Dubois | A general upper bound for the satisfiability threshold of random r-sat formulae[END_REF] and the last lemma, we have:

Lemma 2.5 Uniformly over θ in any interval [a, b] with a > 0, S 1 = Θ(n -1 ) ∑ (k,α)∈D (n) 1 2 H(k)+kH(α/k) (2φ(α, k)) θ/2 n p(k, α, n, θ).
In the next section we consider the term p(k, α, n, θ).

3 Calculations for p(k, α, n, θ)

In this section, we derive an asymptotic formula for p(k, α, n, θ), which was defined in [START_REF] Erdös | On the evolution of random graphs[END_REF] to be equal to For positive integers t ≥ r, we let p(t, r) denote the probability that, when we throw t balls uniformly at random into r bins, each bin ends up non-empty.

P[S is rigid|S is proper], where S ∈ C (k, α, n), m = ⌈θn/2⌉
Consider (k, α) ∈ D (n) . Let L (n) = L (n) (k, α, θ) = λ : n(1-α) m ≤ λ ≤ 1 -n(1-k) m ∩ ( 1 m Z). Then p(k, α, n, θ) = ∑ λ∈L (n) b(λm; m, p) p(λm, n(1 -α)) p((1 -λ)m, n(1 -k)), ( 10
)
where

p = 1 -((1 -k)(k -α))/φ(k, α) (11)
and b(λm; m, p) is the probability that a random variable distributed according to the binomial distribution Bi(m, p) is equal to λm. To see this, observe first that, conditioning on S being a proper 3-colouring, the random variable that determines the number of edges between S 1 and S 2 ∪ S 3 is binomially distributed, namely it is Bi(m, p), where p is defined in [START_REF] Fountoulakis | On the upper bound of the non-3-colourability threshold of random graphs[END_REF]. Once we have specified the number of edges between S 1 and S 2 ∪ S 3 (and, therefore, the number of edges between S 2 and S 3 as well), the probability that S is rigid is exactly the probability that each vertex in S 2 ∪ S 3 is adjacent to some vertex in S 1 and each vertex in S 3 is adjacent to some vertex in S 2 . Note that for each edge, say, between S 1 and S 2 ∪ S 3 , each vertex in S 2 ∪ S 3 has the same probability to be the endvertex of it. The same holds for the edges between S 2 and S 3 . Thus, we can think of this as a random throwing of balls into bins; each ball corresponding to an edge and each bin corresponding to a vertex. Note that we have two independent such random experiments. This observation yields (10).

Discarding the tails

We next check that we may discard the extreme values of λ in (10). This is a technical exercise for which we need one preliminary lemma.

Lemma 3.1 For positive integers t > r t 2(t -r) p(t -1, r) ≤ p(t, r) ≤ t t -r p(t -1, r).
Proof. Let W (t, r) be the set of all arrangements of t balls into r bins leaving no empty bins and let w(t, r) be its cardinality. What we want to prove will follow from the following inequality:

rt 2(t -r) w(t -1, r) ≤ w(t, r) ≤ rt t -r w(t -1, r). ( 12
)
To prove [START_REF] Giotis | Corrigendum to "A note on the non-colourability threshold of a random graph[END_REF], consider ordered pairs of balls and bins, i.e. if T is the set of balls and R the set of bins, take the Cartesian product of them P = T × R. Each such pair (b, B), where b ∈ T and B ∈ R, corresponds to the fact that the ball b is in bin B. For each such pair arrange the remaining t -1 balls into the r bins leaving no empty bins. Thus, we form the set W = {(p, w) : p ∈ P, w ∈ W (t -1, r)}. Note that we have a surjective mapping from the set W onto the set W (t, r). Clearly, W is of cardinality rtw(t -1, r). The mapping induces a natural partition on this set and each of the parts, which is the set of pairs that are mapped to a specific arrangement of t balls into r bins without leaving any empty bins, is of cardinality equal to the number of balls which are not the only ball in their bin, which is at least tr and at most 2(tr). Thus, [START_REF] Giotis | Corrigendum to "A note on the non-colourability threshold of a random graph[END_REF] has been established. Therefore,

t 2(t -r) w(t -1, r) r t-1 ≤ w(t, r) r t ≤ t t -r w(t -1, r) r t-1 ,
and the lemma follows. ✷

For (k, α) ∈ D 1 , let L 1 = L 1 (k, α, θ) = λ : 2(1 -α) θ (1 + 0.24) ≤ λ ≤ 1 - 2(1 -k) θ (1 + 0.065) , (13)
and let

L (n) 1 = L (n) 1 (k, α, θ) = L 1 ∩ ( 1 m Z).
(The extra terms 0.24 and 0.065 here are to exclude extreme values which, as we shall see shortly, are negligible, but which would cause awkwardness later.) It is convenient to restrict θ to a range [θ l , θ u ], as we need to obtain approximations uniformly over θ. We let θ l = 4.98 θ u = 4.99. ( 14)

Lemma 3.2 Uniformly over θ ∈ [θ l , θ u ] and (k, α) ∈ D (n) 1 , p(k, α, n, θ) = Θ(1) ∑ λ∈L (n) 1 b(λm; m, p) p(λm, n(1 -α)) p((1 -λ)m, n(1 -k)).
(Recall that p is defined in [START_REF] Fountoulakis | On the upper bound of the non-3-colourability threshold of random graphs[END_REF].)

Proof. Within the proof, let f (λ) be the general term in the sum in equation (10). We will compare the term f (λ), for some λ which will be specified later, with the adjacent term f (λ -1/m). Note that f (λ) = b(λm; m, p)p(t, r)p(mt, r ′ ), where r = n(1 -α) and r ′ = n(1k), and t = λm. We consider the "lower" tail first. Assume that t = n(1 -α) + ⌊ηn(1 -α)⌋, for some η > 0. By Lemma 3.1 we have

p(t -1, r)p(m -t + 1, r ′ ) ≤ 2 t -r t m -t + 1 m -t + 1 -r ′ p(t, r)p(m -t, r ′ ). Also b(t -1; m, p) = λm m(1 -λ) + 1 1 -p p b(t; m, p). ( 15
)
Thus, we obtain

f λ - 1 m ≤ 2 t -r t m -t + 1 m -t + 1 -r ′ λm m(1 -λ) + 1 1 -p p f (λ).
Using the fact that (k, α) ∈ D 1 , straightforward verification shows that for η = 0.25 and for n sufficiently large the factor on the right hand side is less than 1/2 (in fact it is less than 0.45), for any θ ∈ [θ l , θ u ]. (This is the case because the factor is increasing with respect to η; see [10] for the details.) Therefore, the sum of the terms for t from n(1 -α) up to n(1 -α) + ⌊0.25(1 -α)n⌋ -1 can be bounded as follows:

n(1-α)+⌊0.25(1-α)n⌋-1 ∑ t=n(1-α) f t m ≤ f n(1 -α) + ⌊0.25(1 -α)n⌋ m ,
by the geometric sum formula.

Following the same treatment, we can bound the other tail of the sum. Here, assume that m [START_REF] Kirousis | Approximating the unsatisfiability threshold of random formulas[END_REF], we obtain

-t = n(1 -k) + ⌊η(1 -k)n⌋. Thus, t = m -n(1 -k) -⌊η(1 -k)n⌋. From Lemma 3.1 and
f (λ) ≤ t t -r 2(m -t + 1 -r ′ ) m -t + 1 (1 -λ)m + 1 λm p 1 -p f λ - 1 m .
Using the fact that (k, α) ∈ D 1 , one can see that for η = 0.07 and for n sufficiently large the factor on the right hand side is less than 1/2 (in fact it is less than 0.49), for any θ ∈ [θ l , θ u ]. As in the previous case, this expression is increasing with respect to η. Therefore, the sum of the terms for t from mn(1k) -⌊0.07(1k)n⌋ + 1 up to to mn(1k) can be bounded as follows:

m-n(1-k) ∑ t=m-n(1-k)-⌊0.07(1-k)n⌋+1 f t m ≤ f m -n(1 -k) -⌊0.07(1 -k)n⌋ m ,
by the geometric sum formula. Now, the lemma follows from the above observations along with the fact that each term is non-negative, which means that removing a few terms from the sum gives a lower bound on it. ✷

Introducing Stirling numbers of the second kind

For positive integers t ≥ r the Stirling number of the second kind S(t, r) is defined to be 1/r! times the number of surjective functions from a set of cardinality t to a set of cardinality r. Thus

p(t, r) = r!S(t, r) r t .
Hence, we may rewrite Lemma 3.2 as follows:

Lemma 3.3 Uniformly over θ ∈ [θ l , θ u ] and (k, α) ∈ D (n)
1 , we have:

p(k, α, n, θ) = = Θ(1) ∑ λ∈L (n) 1 ⌈θn/2⌉ λ⌈θn/2⌉ (1 -k)(k -α) φ(k, α) ⌈ θn 2 ⌉(1-λ) 1 - (1 -k)(k -α) φ(k, α) λ⌈ θn 2 ⌉ × (n(1 -α))!S(λ⌈θn/2⌉, n(1 -α)) (n(1 -α)) λ⌈ θn 2 ⌉ (n(1 -k))!S((1 -λ)⌈θn/2⌉, n(1 -k)) (n(1 -k)) ⌈ θn 2 ⌉(1-λ)
.

Asymptotics for Stirling numbers of the second kind

An essential part of our probability calculations involves asymptotic expressions for the Stirling numbers of the second kind. We need some preliminary definitions and results, see for example [START_REF] Temme | Asymptotic estimates for Stirling numbers[END_REF].

For 0 < u ≤ 1 let E u (x) = 1 -e -x -ux.
For 0 < u < 1 let x 0 (u) be the unique positive root of E u (x) = 0. (See Figure 1.) Note that E 1 (x) has the unique root x = 0: we let x 0 (1) = 0. Then x 0 (u) is a continuous function on (0, 1], and

x 0 (u) + 1 -1/u > 0 y=1-exp(-x)
for each 0 < u < 1. For 0 < u < 1 let f (u) = 1 -u x 0 (u) + 1 -1/u 1/2
, and let f (1) = 0. Then f is a continuous function on (0, 1], and 0 ≤ f (u) ≤ 1 (see [START_REF] Dubois | A general upper bound for the satisfiability threshold of random r-sat formulae[END_REF]). In Appendix A, we give a positive lower bound on f (u).

It is shown in [START_REF] Temme | Asymptotic estimates for Stirling numbers[END_REF] that, for positive integers t > r, S(t, r) = (e x 0 -1) r (x 0 (u)

) -t e -(t-r) (t -r) (t-r) t r f (u)(1 + ε(t, r)), ( 16
)
where u = r/t and max 0<r<t |ε(t, r)| → 0 as t → ∞.

The estimate

Recall that D 1 and L 1 are defined in ( 6) and ( 13) above. Let

D = D(θ) = {(k, α, λ) : (k, α) ∈ D 1 , λ ∈ L 1 (k, α, θ)}, (17)
and let

D (n) = D (n) (θ) = D ∩ ( 1 n Z 2 ) × ( 1 m Z) = {(k, α, λ) : (k, α) ∈ D (n) 1 , λ ∈ L (n) 1 (k, α, θ)}. For θ ∈ [θ l , θ u ] and (k, α, λ) ∈ D, let P(k, α, λ, θ) = (1 -k) -θ 2 2 θ 2 H(λ) 1 -k 1 -α λθ 2 (e x 1 -1) (1-α) (e x 2 -1) (1-k) (x 1 ) -λθ 2 (x 2 ) -θ 2 (1-λ) × e -θ 2 λθ 2 θλ 2 θ(1 -λ) 2 θ(1-λ) 2 (1 -k)(k -α) φ(k, α) θ 2 (1-λ) 1 - (1 -k)(k -α) φ(k, α) λθ 2
,

where x 1 = x 0 2(1-α) θλ and x 2 = x 0 2(1-k)
θ(1-λ) . We shall prove the following lemma:

Lemma 3.4 Uniformly over θ ∈ [θ l , θ u ] and (k, α) ∈ D 1 , we have: p(k, α, n, θ) = Θ(n -1/2 ) ∑ λ∈L (n) 1 {P(k, α, λ, θ)} n .
Proof. In what follows, the "error" term ⌈θn/2⌉ -θn/2 yields a Θ(1) factor for each term of the sum in Lemma 3.3, since (k, α) ∈ D

(n)

1 . We use Lemma 2.4 to give asymptotic expressions for the binomial coefficients. Note that since (k, α) ∈ D 1 the assumptions of Lemma 2.4 are satisfied. This is also true for the coefficient that involves θ, since θ is assumed to be in a closed and bounded interval not containing 0. Thus, using ( 16) and Stirling's approximation for the factorials, Lemma 3.3 implies the following:

p(k, α, n, θ) = Θ(n -1/2 ) ∑ λ∈L (n) 1 P ′ (k, α, λ, θ) n ,
where, for θ ∈ [θ l , θ u ] and (k, α, λ) ∈ D,

P ′ (k, α, λ, θ) = = n (2-α-k) (1 -α) (1-α) (1 -k) (1-k) e -(2-α-k) n θ 2 (1 -k) θ 2 2 θ 2 H(λ) 1 -k 1 -α λθ 2 × n ( θλ 2 +α-1) t(1 -α, λθ/2) n ( θ 2 -θλ 2 -1+k) t(1 -k, (1 -λ)θ/2) × f 2(1 -α) θλ f 2(1 -k) θ(1 -λ) (1 -p) θ 2 (1-λ) p λθ 2 = (1 -α) (1-α) (1 -k) (1-k) e -(2-α-k) (1 -k) θ 2 2 θ 2 H(λ) 1 -k 1 -α λθ 2 f 2(1 -α) θλ f 2(1 -k) θ(1 -λ) × t(1 -α, λθ/2) t(1 -k, (1 -λ)θ/2) (1 -p) θ 2 (1-λ) p λθ 2 ,
where t(x, y) = (e x 0 -1) y (x 0 ) -x e -(x-y) (xy) (x-y) x y y x xy (x-y)

, where x 0 = x 0 (x/y) and where p is defined in [START_REF] Fountoulakis | On the upper bound of the non-3-colourability threshold of random graphs[END_REF]. Doing some calculations, we obtain:

P ′ (k, α, λ, θ) = = (1 -k) -θ 2 2 θ 2 H(λ) 1 -k 1 -α λθ 2 (e x 1 -1) (1-α) (e x 2 -1) (1-k) (x 1 ) -λθ 2 (x 2 ) -θ 2 (1-λ) e -θ 2 × f 2(1 -α) θλ f 2(1 -k) θ(1 -λ) λθ 2 θλ 2 θ(1 -λ) 2 θ(1-λ) 2 (1 -p) θ 2 (1-λ) p λθ 2 = P(k, α, λ, θ) f 2(1 -α) θλ f 2(1 -k) θ(1 -λ) ,
where

x 1 = x 0 2(1-α) θλ and x 2 = x 0 2(1-k)
θ(1-λ) . For the elementary but tedious calculations see Appendix B.

Also, note that by (27) in Appendix A, the monotonicity of the lower bound for f (u), where u = 2(1-α)

θλ or u = 2(1-k) θ(1-λ)
, and the fact that (k, α) ∈ D 1 , it follows that in both cases the function f is at least

1 -2 5θ x 0 2 5θ
, and so the two factors including f in the expression above yield a Θ(1) term. This concludes the proof of the lemma. ✷ 4 Proof of Theorem 1.1 and Corollary 1.2

Recall that θ l , θ u were introduced in ( 14) and D was defined in [START_REF] Molloy | The chromatic number of sparse random graphs[END_REF]. For θ ∈ [θ l , θ u ] and (k, α, λ) ∈ D, let

h(k, α, λ, θ) = H(k) + kH α k + θ 2 - θ 2 log(e) + θ 2 log θ 2 + θ 2 -λ log λ -(1 -λ) log(1 -λ) + (1 -λ) log(1 -k) +(1 -λ) log(k -α) + λ log α + λ log(1 -α) +(1 -k) log(e x 2 -1) - θ 2 (1 -λ) log(x 2 ) - θ(1 -λ) 2 log(1 -k) + θ(1 -λ) 2 log(1 -λ) +(1 -α) log(e x 1 -1) - λθ 2 log(x 1 ) - λθ 2 log(1 -α) + λθ 2 log λ, (18)
where

x 1 = x 0 2(1-α) θλ and x 2 = x 0 2(1-k)
θ(1-λ) . (Recall that the function x 0 (u) was defined at the start of Subsection 3.3 ) We will prove the following:

Lemma 4.1 Uniformly over θ ∈ [θ l , θ u ], S 1 = Θ(n -3/2 ) ∑ (k,α,λ)∈D (n) 2 h(k,α,λ,θ)n .
Proof. Lemmas 2.5 and 3.4 imply that uniformly over θ ∈ [θ l , θ u ]:

S 1 = Θ(n -3/2 ) ∑ (k,α,λ)∈D (n) 2 H(k) 2 kH( α k ) (2φ(k, α)) θ 2 P(k, α, λ, θ) n = Θ(n -3/2 ) ∑ (k,α,λ)∈D (n) 2 h(k,α,λ,θ) n , since for (k, α, λ) ∈ D, 2 H(k) 2 kH( α k ) (2φ(k, α)) θ 2 P(k, α, λ, θ) = = 2 H(k) 2 kH( α k ) (2φ(k, α)) θ 2 2 θ 2 H(λ) (1 -k) -θ 2 1 -k 1 -α λθ 2 (e x 1 -1) (1-α) (e x 2 -1) (1-k) × (x 1 ) -λθ 2 (x 2 ) -θ 2 (1-λ) e -θ 2 λθ 2 θλ 2 θ(1 -λ) 2 θ(1-λ) 2 (1 -p) θ 2 (1-λ) p λθ 2 = 2 H(k) 2 kH( α k ) 2 θ 2 2 θ 2 H(λ) ((1 -k)(k -α)) θ 2 (1-λ) (α(1 -α)) λθ 2 (1 -k) -θ(1-λ) 2 (1 -α) -λθ 2 × (e x 1 -1) (1-α) (e x 2 -1) (1-k) (x 1 ) -λθ 2 (x 2 ) -θ 2 (1-λ) e -θ 2 λθ 2 θλ 2 θ(1 -λ) 2 θ(1-λ) 2 = 2 h(k,α,λ,θ) ,
where p is defined in [START_REF] Fountoulakis | On the upper bound of the non-3-colourability threshold of random graphs[END_REF]. Hence, the lemma has been established. ✷ By the last lemma,

S 1 = c(n, θ) max (k,α,λ)∈D (n) 2 h(k,α,λ,θ) n = c(n, θ) 2 µ(θ,n)n , (19)
where c(n, θ) = Ω(n -3/2 ), c(n, θ) = O(n 3/2 ) and

µ(θ, n) = max (k,α,λ)∈D (n) {h(k, α, λ, θ)}.
Let D (∞) = lim inf D (n) and note that it is the set of rationals contained in D and, therefore, it is dense inside it. Then, we have

lim n→∞ µ(θ, n) = µ(θ) = sup (k,α,λ)∈D (∞) h(k, α, λ, θ) = max (k,α,λ)∈D h(k, α, λ, θ),
since for each fixed θ the function h(k, α, λ, θ) is continuous on D, which is a compact subset of R 3 . In fact, we can say a little more than this. We know that h(k, α, λ, θ) attains its maximum at an internal point of D, say x * . Note that this is a stationary point and one can also see that h is differentiable on D and its derivatives are continuous. The latter implies that for any ε > 0 there exists an open ball U containing x * where ∇h < ε. For n sufficiently large, there is a point

x n ∈ D (n) ∩U with x n -x * 2 ≤ 2 1 2n 2 + 1 m 2 ≤ 1 2 + 4 θ 2 l n -2 ,
and then

µ(θ, n) ≥ µ(θ) -ε 1 2 + 4 θ 2 l 1/2 n -1 ,
by the Mean Value Theorem. Hence,

sup θ∈[θ l ,θ u ] n(µ(θ) -µ(θ, n)) = o(1).
This fact along with [START_REF] Strang | Linear Algebra and its Applications[END_REF] imply the following:

Lemma 4.2 Uniformly over θ ∈ [θ l , θ u ], S 1 = 2 µ(θ)n+O(log n) .
Since h(k, α, λ, θ) is continuous on its domain D, and h as a function of θ is also continuous, the function µ(θ) is continuous as well. As we shall see later, for θ 0 = 4.9893, we have

µ(θ 0 ) > 0. ( 20
)
The numerical investigation in the next section shows that

µ(θ 2 ) < 0, ( 21
)
for θ 2 = 4.9895. By Lemma 2.3, there exists δ > 0 such that

S 2 = O 2 -δn , uniformly over θ ∈ [θ l , θ u ].
We set δ ′ = min{ δ, -µ(θ 2 )}. Let

θ 1 = inf{θ ≥ θ 0 : µ(θ) ≤ -δ ′ /2}.
Note that ( 20) and ( 21) imply that θ 0 < θ 1 < θ 2 . Thus, we have µ(θ 1 ) = -δ ′ /2 and µ(θ) ≥ -δ ′ /2 for each θ ∈ [θ 0 , θ 1 ]. Therefore, Lemma 4.2 implies that uniformly over θ ∈ [θ 0 , θ 1 ], we have

E[R(G * n,m )] = 2 µ(θ)n+O(log n) + S 2 = 2 µ(θ)n+O(log n) + O 2 -δ ′ n = 2 µ(θ)n+O(log n) , that is E[R(G * n,m )] = 2 µ(θ)n+O(log n) . ( 22
)
Now, to establish Theorem 1.1, i.e. to show that this result in fact is also true in the G n,m model, we have to do a little more work. We prove the following:

Lemma 4.3 Let θ l ≤ b < ∞. Uniformly over θ ∈ [θ l , b] we have E[R(G n,m )] = Θ(1) E[R(G * n,m )],
where m = ⌈θn/2⌉.

Proof. To see the one direction note that

E[R(G * n,m )] ≥ E[R(G * n,m )||E(G * n,m )| = m] P[|E(G * n,m )| = m] = E[R(G n,m )] P[|E(G * n,m )| = m].
Here, E(G) denotes the set of edges of a graph G. Recall that ln(1

-x) ≥ -x 1-x ≥ -2x, for 0 ≤ x ≤ 1/2. Hence, if 2m ≤ n 2 , P[|E(G * n,m )| = m] = m-1 ∏ i=0 1 - i n 2 ≥ exp -2 m 2 n 2 .
This expression is bounded away from 0 uniformly for θ in the closed interval

[θ l , b].
The other direction is a little more tricky. To see this note as before that

P[S ∈ R (G n,m )] = P[S is proper for G n,m ] P[S ∈ R (G n,m )|S is proper for G n,m ]. By Lemma 2.2, we have e(S) = n 2 φ(k, α) ≥ 0.28n 2 , for a colouring S ∈ C (k, α, n), where (k, α) ∈ D 1 ,
whence we obtain e(S)/m 2 ≥ η > 0, for some η (depending only on b). Thus (once 2m ≤ e(S)),

1 - m e(S) m = exp m ln 1 - m e(S)
≥ exp(-2m 2 /e(S)) ≥ e -2/η .

Hence, for such an S, we have

P[S is proper for G n,m ] = e(S)
n 2 e(S) -

1 n 2 -1 • • • e(S) -m + 1 n 2 -m + 1 ≥ e(S) n 2 1 - m e(S) m ≥ e -2/η P[S is proper for G * n,m ].
On the other hand,

P[S ∈ R (G n,m )|S is proper for G n,m ] ≥ P[S ∈ R (G * n,m )|S is proper for G * n,m ],
since adding edges to a proper 3-colouring increases the probability that this is rigid. Therefore,

P[S ∈ R (G * n,m )] ≤ e 2/η P[S ∈ R (G n,m )].
Finally, by Lemma 2.3, since θ ≥ 4.98,

E[R(G * n,m )] = (1 + o(1)) ∑ (k,α)∈D (n) 1 ∑ S∈C (k,α,n) P[S ∈ R (G * n,m )] ≤ (1 + o(1)) e 2/η ∑ (k,α)∈D (n) 1 ∑ S∈C (k,α,n) P[S ∈ R (G n,m )] ≤ (1 + o(1)) e 2/η E[R(G n,m )].
✷ Thus, Lemma 4.3 along with (22) and inequalities [START_REF] Temme | Asymptotic estimates for Stirling numbers[END_REF] and ( 21) conclude the proof of Theorem 1.1. Corollary 1.2 follows immediately.

Numerical Computations

Let us quickly dispose of the easy result [START_REF] Temme | Asymptotic estimates for Stirling numbers[END_REF]. As above, let θ 0 = 4.9893. Also, we set k = 0.698, α = 0.362 and λ = 0.691. We find using Maple with 10 digits precision that h(k, α, λ, θ 0 ) > 0. In fact, to one digit it equals 5 × 10 -6 . Moreover, for the same values of k, α and λ and for θ = 4.989, h(k, α, λ, θ) equals 7 × 10 -5 , to one digit, and so µ(4.989) > 0 (yielding the result stated in brackets in the abstract). These values for k, α, λ were found using the Complex method [START_REF] Bunday | Basic Optimisation Methods[END_REF]: for details of this and other computational matters see [10].

To complete the proof of Theorem 1.1, and thus of Corollary 1.2, it remains to establish [START_REF] Webster | Convexity[END_REF]. Let From an initial approximation to the maximum in D, using the Complex method [START_REF] Box | A new method of constrained optimisation and a comparison with other methods[END_REF] (see also [START_REF] Bunday | Basic Optimisation Methods[END_REF]), our attention is directed to the cube C ⊆ D, where 0.6980 ≤ k ≤ 0.6981, 0.3622 ≤ α ≤ 0.3623 and 0.6910 ≤ λ ≤ 0.6911. Divide the surface of the cube C into squares of side s = 5 × 10 -6 . For a square centred at a, by the concavity of h we obtain

h = h(k, α, λ) = h(k, α, λ, θ 2 ),
h(b) ≤ h(a) + (s/ √ 2) ∇h(a)
for each point b in the square. By checking each square, we find that h(x) ≤ -3.937721 × 10 -5 for each point x on the surface of the cube C . But there is a point y inside C with h(y) strictly greater than this bound. More specifically, we may define a cubic grid inside C each cube having side equal to 5 × 10 -6 .

The maximum value we find by searching this grid is equal to -3.937414 × 10 -5 and it is strictly greater than the upper bound on h on the surface of C . Since h is concave on D, it follows as noted above that h attains its maximum over D inside C . Now we obtain an upper bound on h inside C , using the aforementioned grid. By concavity, for each point b in the sub-cube with its centre located at a and edge of length equal to s, we have

h(b) ≤ h(a) + √ 3s 2 ∇h(a) .
By checking through each sub-cube, we find that h(x) is less than -3.9 × 10 -5 , for each x ∈ C , and thus for each x ∈ D.

6 Proof of Theorem 1.3

Let t(G) denote the number of components of the graph G that are non-trivial trees (that is, trees with at least one edge).

Lemma 6.1 For any t ≥ 0 and any positive integers n and m with

0 ≤ m ≤ n 2 , P[χ(G n,m ) ≤ 3] ≤ 2 -t E[R(G n,m )] + P[t(G n,m ) < t].
Proof. Any non-trivial tree has at least 2 rigid 3-colourings. Thus, for a graph

G, if χ(G) ≤ 3 and t(G) ≥ t, then R(G) ≥ 2 t . Hence, 1 {χ(G)≤3}∩{t(G)≥t} ≤ 2 -t R(G).
Now, we apply this result to G n,m and take expectations. We obtain:

P[(χ(G n,m ) ≤ 3) ∧ (t(G n,m ) ≥ t)] ≤ 2 -t E[R(G n,m )],
and the lemma follows. ✷

For θ > 0 let τ(θ) = ∞ ∑ t=2 θ t-1 e -tθ t t-2
t! , and m = ⌈θn/2⌉. We shall use standard methods to prove: Lemma 6.2 Let θ > 0. For any ε > 0 there exists δ 1 > 0 such that

P[t(G n,m ) ≤ τ(θ)n -εn] = O(e -δ 1 n ).
Proof. Let T be a tree on vertices 1, . . . ,t, where t is constant. Then

P[T is a component of G n,m ] = ( n-t 2 )
m-t+1

( n 2 ) m = θ n t-1 e -θt (1 + o(1)),
by standard approximations. Now we may multiply by n t t t-2 to see that the expected number of tree components with t vertices in G n,m is (1 + o( 1)) nθ t-1 e -θt t t-2 /t!. Since the number of tree components of G n,m with at least t vertices is at most n/t, it follows that (see also [START_REF] Bollobás | Random Graphs[END_REF] p.96):

E[t(G n,m )] = n ∞ ∑ t=2 θ t-1 e -θt t t-2 /t! (1 + o(1)) = n • τ(θ) (1 + o(1)).
The following lemma will complete the proof, since if G ′ is obtained from G by adding an edge and deleting an edge then |t(G)t(G ′ )| ≤ 2. ✷ The following lemma is a special case of Theorem 7.4 of [START_REF] Mcdiarmid | On the method of bounded differences[END_REF].

Lemma 6.3 Let f be a function on graphs such that, if G ′ is obtained from G by adding an edge and deleting an edge, then

| f (G) -f (G ′ )| ≤ c. Let µ = E[ f (G n,m )]. Then for any x ≥ 0 P[ f (G n,m ) -µ ≥ x] ≤ exp -2x 2 /mc 2 and P[ f (G n,m ) -µ ≤ -x] ≤ exp -2x 2 /mc 2 .
Proof. Given an m-tuple x of distinct edges of K n , let G(x) be the graph on {1, . . . , n} with edges those mentioned in x (ignoring the order), and let f (x) = f (G(x))/c. Then | f (x) -f (y)| ≤ 1 if x and y differ in exactly one co-ordinate, or if they differ in exactly two co-ordinates and the values there are swapped. Thus we may apply Theorem 7.4 of [START_REF] Mcdiarmid | On the method of bounded differences[END_REF], see also Example 7.3 there. ✷ Therefore, setting x = τ(θ)nεn, for some ε > 0 which will be specified later, in Lemma 6.1, and using also Lemmas 6.2, 4.2 and 4.3 along with equation ( 8) we obtain the following:

P [χ(G n,m ) ≤ 3] ≤ 2 -nτ(θ)+εn E [R(G n,m )] + O e -δ 1 n = 2 εn 2 -nτ(θ)+Θ(1) (2 nµ(θ)+O(log n) + S 2 ) + O e -δ 1 n . ( 23
)
We now fix θ = 4.98887.

From the proof of Lemma 2.3 we may see that S 2 ≤ 1, for n sufficiently large. We keep the definition of the region D unchanged. Inside D, we may perform numerical investigations similar to those in the case of the rigid 3-colourings. We consider the same sub-cube C as before, and find again that h(k, α, λ, θ) attains its maximum inside C . We can check through the same family of sub-cubes and see that the maximum value µ(θ) of h(k, α, λ, θ) over D satisfies µ(θ) > 0, but τ(θ)µ(θ) ≥ 10 -5 . Then by (23) with

ε = τ(θ)-µ(θ)

2

, we obtain:

P [χ(G n,m ) ≤ 3] ≤ 2 -(ε+o(1))n + O e -δ 1 n .
Choosing δ < min{ε, δ 1 log e}, we conclude the proof of Theorem 1.3.

Appendices

A A note on Subsection 3.3 We set u = r/t. Recall that x 0 (u) = x 0 (r,t) is the root of the following equation:

E u (x) = 1 -e -x -ux = 0, (24)
for 0 < u = u(r,t) ≤ 1. Let x 0 = x 0 (u) throughout this Appendix. Suppose that y is either r or t. We have

e -x 0 ∂x 0 ∂y - ∂u ∂y x 0 -u ∂x 0 ∂y = 0.
Therefore, ∂x 0 ∂y = (∂u/∂y)x 0 e -x 0u .

Again, using (24) we have e x 0 -1e x 0 ux 0 = 0.

So, u = e -x 0 (e x 0 -1)x -1 0 . Thus, (25) becomes ∂x 0 ∂y = (∂u/∂y)x 0 e -x 0e -x 0 (e x 0 -1)x -1

0 = e x 0 (∂u/∂y)x 2 0 1 + x 0 -e x 0 . ( 26
)
The denominator is negative, since 1 + x 0 < e x 0 . Thus, the sign of this expression depends upon the sign of ∂u/∂y. We shall use these expressions for the derivatives of x 0 (u) with respect to the variables on which it depends in Appendix C. Now, we shall give a lower bound on f (t, r) and we will study its monotonicity. In fact we shall work with

f (t, r) 2 = f (u) 2 = 1 -u x 0 -1 u + 1
, where u = r/t. We have

f (u) 2 = 1 -u x 0 -1 u + 1 u(1 -u) ux 0 -(1 -u) > u(1 -u) ux 0 = 1 -u x 0 .
Thus,

f (u) 2 > 1 -u x 0 . (27)
In what follows, we are trying to investigate the monotonicity of the latter function. The derivative of this with respect to u is

1 -u x 0 ′ = -x 0 -(1 -u) ∂x 0 ∂u x 2 0 .
We have to determine the sign of the numerator. Using (25), we obtain

-x 0 -(1 -u) ∂x 0 ∂u = -x 0 1 + (1 -u) 1 e -x 0 -u = -x 0 1 + (1 -u) 1 1 -ux 0 -u = -x 0 1 + 1 1 -u 1-u x 0 . f 2(1 -α) θλ f 2(1 -k) θ(1 -λ) (1 -k)(k -α) φ(k, α) θ 2 (1-λ) 1 - (1 -k)(k -α) φ(k, α) λθ 2 = (1 -α) (1-α) (1 -k) (1-k) e -(2-α-k) (1 -k) θ 2 2 θ 2 H(λ) 1 -k 1 -α λθ 2 f 2(1 -α) θλ f 2(1 -k) θ(1 -λ) × t(1 -α, λθ/2) t(1 -k, (1 -λ)θ/2) (1 -k)(k -α) φ(k, α) θ 2 (1-λ) 1 - (1 -k)(k -α) φ(k, α) λθ 2
, where t(x, y) = (e x 0 -1) y (x 0 ) -x e -(x-y) (xy) (x-y) x y y x xy (x-y)

, where x 0 = x 0 (x/y). Thus, for (k, α, λ) ∈ D we have

P ′ (k, α, λ) = = (1 -α) (1-α) (1 -k) (1-k) e -(2-α-k) (1 -k) θ 2 2 θ 2 H(λ) 1 -k 1 -α λθ 2 (e x 1 -1) (1-α) (x 1 ) -λθ 2 e -( θλ 2 +α-1) × θλ 2 + α -1 ( θλ 2 +α-1) λθ 2(1 -α) (1-α) λ θ 2 θλ 2 + α -1 ( θλ 2 +α-1) × (e x 2 -1) (1-k) (x 2 ) -θ 2 (1-λ) e -( θ 2 -θλ 2 -1+k) × θ 2 - θλ 2 -1 + k ( θ 2 -θλ 2 -1+k) θ(1 -λ) 2(1 -k) (1-k)   θ(1-λ) 2 θ 2 -θλ 2 -1 + k   ( θ 2 -θλ 2 -1+k) × f 2(1 -α) θλ f 2(1 -k) θ(1 -λ) (1 -k)(k -α) φ(k, α) θ 2 (1-λ) 1 - (1 -k)(k -α) φ(k, α) λθ 2 = (1 -k) -θ 2 2 θ 2 H(λ) 1 -k 1 -α λθ 2 (e x 1 -1) n(1-α) (e x 2 -1) (1-k) (x 1 ) -λθ 2 (x 2 ) -θ 2 (1-λ) e -θ 2 × λθ 2 θλ 2 θ(1 -λ) 2 θ(1-λ) 2 f 2(1 -α) θλ f 2(1 -k) θ(1 -λ) × (1 -k)(k -α) φ(k, α) θ 2 (1-λ) 1 - (1 -k)(k -α) φ(k, α) λθ 2
,

where x 1 = x 0 2(1-α) θλ
, i.e. it is the positive root of the equation

1 -e -x - 2(1 -α) θλ x = 0 (28) and x 2 = x 0 2(1-k)
θ(1-λ) , i.e. it is the positive root of the equation

1 -e -x - 2(1 -k) θ(1 -λ) x = 0. ( 29
)
C The concavity of h(k, α, λ) over D

In this Appendix, we show that the function h(k, α, λ) as it was defined in Section 5 is strictly concave over the interior of D, where D was defined in [START_REF] Molloy | The chromatic number of sparse random graphs[END_REF]. (Recall that the function h(k, α, λ, θ) was defined in ( 18), and we have fixed θ = θ 2 = 4.9895 to obtain h(k, α, λ).) This treatment improves the proof in an earlier version of this paper; and was inspired by the correction [START_REF] Giotis | Corrigendum to "A note on the non-colourability threshold of a random graph[END_REF] to [START_REF] Kaporis | A note on the non-colourability threshold of a random graph[END_REF]. We split the function h(k, α, λ)

(multiplied by ln 2 to change to natural logarithms) into four parts. Namely, for any (k, α, λ) ∈ D, we have

ln 2 h(k, α, λ) = h 1 (k, α, λ) + h 2 (k, α, λ) + h 3 (k, α, λ) + θ 2 2 h 4 (k, α, λ),
where

h 1 (k, α, λ) = -(1 -k) ln(1 -k) -(k -α) ln(k -α) -α ln α + θ 2 2 - θ 2 2 log(e) + θ 2 2 log θ 2 2 ln 2, h 2 (k, α, λ) = (1 -k) ln(e x 2 -1) - θ 2 2 (1 -λ) ln x 2 - θ 2 (1 -λ) 2 ln(1 -k) + θ 2 (1 -λ) 2 ln(1 -λ), h 3 (k, α, λ) = (1 -α) ln(e x 1 -1) - λθ 2 2 ln x 1 - λθ 2 2 ln(1 -α) + λθ 2 2 ln λ, h 4 (k, α, λ) = -λ ln λ -(1 -λ) ln(1 -λ) + (1 -λ) ln(1 -k) + (1 -λ) ln(k -α) + λ ln α + λ ln(1 -α),
and x 1 , x 2 are defined in (28) and (29), respectively. For i = 1, . . . , 4, we set h i = h i (k, α, λ). We prove that each of these functions is concave over the interior of D, with h 4 being strictly concave there. To prove that a suitably differentiable function is concave (strictly concave, respectively) over an open domain, we have to prove that its Hessian matrix (i.e. the matrix of the second partial derivatives) is negative semidefinite (definite, respectively) over this domain (see for example [START_REF] Webster | Convexity[END_REF], Theorem 5.5.5 p. 230). By, for example, Theorem 6E in [START_REF] Strang | Linear Algebra and its Applications[END_REF] (p.339), to check negative semidefiniteness (definiteness, respectively) of a real symmetric matrix it is necessary and sufficient to show that the principal minors have alternating signs (and are non-zero in the case of definiteness), the first one being non-positive. Thus, we may deal with h 1 , . . . , h 4 as follows (for further details of the calculations see [10]).

1. Observe that h 1 does not depend on λ. It can be easily checked that it is concave over D. The elements of the Hessian matrix with respect to k and α are the following:

∂ 2 h 1 ∂k 2 = - 1 (1 -k) - 1 (k -α) < - 1 (k -α) , ∂ 2 h 1 ∂k∂α = 1 k -α , ∂ 2 h 1 ∂α 2 = - 1 α - 1 k -α < - 1 (k -α)
.

Thus ∂ 2 h 1 ∂k 2 < 0 and ∂ 2 h 1 ∂k 2 ∂ 2 h 1 ∂α 2 -∂ 2 h 1 ∂k∂α 2
> 0, and so is concave over D.

2. Next we consider the function h 2 , which does not depend on α. After doing some algebraic manipulations and using ( 29) and (26), we obtain:

∂ 2 h 2 ∂k 2 = θ 2 2 1 -λ (1 -k) 2 x 2 1 + x 2 -e x 2 .
Similarly,

∂ 2 h 2 ∂λ 2 = θ 2 2(1 -λ) x 2 1 + x 2 -e x 2 ,
and

∂ 2 h 2 ∂k∂λ = - θ 2 2 1 1 -k x 2 1 + x 2 -e x 2 .
Clearly we have ∂ 2 h 2 ∂k 2 < 0 and it is easily checked from the above that

∂ 2 h 2 ∂k 2 ∂ 2 h 2 ∂λ 2 -∂ 2 h 2 ∂k∂λ 2
is identically 0 over D; and so h 2 is concave there.

3. The function h 3 has precisely the same form as h 2 , where 1 -λ has been replaced by λ. Thus, we deduce that h 3 is also concave over the interior of D.

    =    -1-λ (1-k) 2 -1-λ (k-α) 2 1-λ (k-α) 2 1 1-k -1 k-α 1-λ (k-α) 2 -1-λ (k-α) 2 -λ α 2 -λ (1-α) 2 1 k-α + 1 α -1 1-α 1 1-k -1 k-α 1 k-α + 1 α -1 1-α -1 λ -1 1-λ    .
To show strict concavity, it suffices to show that the principal minors are non-zero and have alternating signs with the first one being negative. It is easy to see that the first two principal minors are as required, since ∂ 2 h 4 ∂k 2 and ∂ 2 h 4 ∂α 2 are strictly less than -1-λ (k-α) 2 . The third principal minor, which is the determinant ∆ of the matrix, satisfies

∆ = -(1 -λ)α 2 (1 -α) 2 + 4λα(1 -α)(k -α)(1 -k) -2λ 2 (k -α)(1 -k) λα 2 (1 -α) 2 (k -α) 2 (1 -k) 2 ,
and this can verified e.g. by using Maple (or see [10] for the details). The denominator is always strictly positive, so it is sufficient to show that the numerator in negative for any (k, α, λ) ∈ D.

Let us fix α, λ < 1 and express the numerator as a quadratic function of k, for α ≤ k ≤ 1. We obtain -k 2 η + k(α + 1)η -((1 -λ)α 2 (1 -α) 2 + αη), where η = (4α(1 -α) -2λ)λ. If η = 0, then obviously this expression is negative. On the other hand, for k = α or k = 1, the above expression is equal to -(1 -λ)α 2 (1 -α) 2 < 0. So, to show that this quadratic function is negative it is sufficient to prove that at its stationary point k = (α + 1)/2 this is negative. But the value of the function at this point is

-(1 -λ)α 2 (1 -α) 2 + λα(1 -α) 3 - λ 2 (1 -α) 2 2 = -(1 -α) 2 α 2 2 + 1 2 (α -λ) 2 < 0,
and this concludes the proof of the strict concavity of h 4 over D.

  n) = sup{θ > 0 : χ(G n,⌈θn/2⌉ ) ≤ k aas },and θ + k = lim sup n→∞ d k (n) = inf{θ > 0 : χ(G n,⌈θn/2⌉ ) > k aas }.

  , let us introduce our central theorem. Let m = ⌈θn/2⌉. For a graph G, let R (G) denote the set of rigid 3-colourings of G, and let R(G) denote the cardinality of this set. For θ in an interval [θ l , θ u ], and for x in a domain D = D(θ) ⊆ [0, 1] 3 , we shall introduce a function h(x, θ) (defined in (18) below), and let µ(θ) = sup x∈D h(x, θ).

Corollary 1 . 2

 12 Let θ = 4.9895 and m = ⌈θn/2⌉. Then there exists δ > 0 such that P [χ(G n,m ) ≤ 3] ≤ 2 -δn , for n sufficiently large.

Theorem 1 . 3

 13 Let θ = 4.98887 and m = ⌈θn/2⌉. Then there exists δ > 0 such that P [χ(G n,m ) ≤ 3] ≤ 2 -δn , for n sufficiently large.

βn and s 3 =

 3 |S 3 | = γn, and where k = α + β. Set e(S) = s 1 s 2 + s 1 s 3 + s 2 s 3 .

Lemma 2 . 3

 23 Let 4.98 ≤ a ≤ b. Then there exist δ > 0 and n 0 ∈ N such that for θ ∈ [a, b], n ≥ n 0 and m = ⌈θn/2⌉ we have:

  and we are working in the G * n,m model. See Lemma 3.2 below.

Fig. 1 :

 1 Fig. 1: The function x 0 (u)

  where as above θ 2 = 4.9895. Then h is continuous over D, and we shall see in Appendix C that it is strictly concave over the interior of D. Thus, if C ⊆ D and y ∈ C o (the interior of C ) are such that h(y) > h(x) for every x in the boundary of C , then h has a unique maximum point x * over D and x * ∈ C o . Using concavity, we can estimate numerically where the maximum of h is located, and give an upper bound on h over this domain, as follows.

  4. We show that h 4 is strictly concave over the interior of D. Its Hessian matrix is:

	   	∂ 2 h 4 ∂k 2 ∂ 2 h 4 ∂k∂α ∂ 2 h 4 ∂k∂λ	∂ 2 h 4 ∂k∂α ∂ 2 h 4 ∂α 2 ∂ 2 h 4 ∂α∂λ	∂ 2 h 4 ∂k∂λ ∂ 2 h 4 ∂α∂λ ∂ 2 h 4 ∂λ 2

* Research supported by EPSRC Studentship, Award No.: 00801424, and "Alexander S. Onassis" Public Benefit Foundation Cont. No.: W-112/2000. 1365-8050

Concluding remarks

We considered the adequate family consisting of the rigid 3-colourings of a graph, and investigated carefully the expected number of such colourings in the random graph G n,m . We thus obtained an upper bound on the non-3-colourability threshold θ + 3 , which appears independently in [START_REF] Kaporis | A note on the non-colourability threshold of a random graph[END_REF]. We then improved this upper bound slightly, by taking into account the number of non-trivial tree components.

Let us sketch now some related ideas that also will improve the upper bound slightly. When we considered the number of non-trivial tree components in Section 6, in the proof of Lemma 6.1 we used the fact that R(T ) ≥ 2 for any non-trivial tree T . We can be more precise; for example R(T ) ≥ 3 unless T is a star. By computing the value of R(T ) for each 'small' non-trivial tree (say those having at most 5 vertices), and then following the general approach in Section 6, it is possible to obtain a slight improvement on Theorem 1.3 (see [10] for further details).

We may also consider an adequate subfamily of the rigid 3-colourings of a graph G, namely the leftmost 3-colourings. These are the proper 3-colourings S 1 , S 2 , S 3 where |S 3 | is minimal and, subject to this, |S 2 | is minimal. Note that any such 3-colouring must be rigid and, further, this family is adequate. Unfortunately it seems to be hard to study leftmost 3-colourings, but we can work with related families such as those defined in terms of "Ψ-gadgets".

Given a 3-colouring S 1 , S 2 , S 3 of a graph G, a Ψ 12 -gadget is a component of the subgraph induced on S 1 ∪ S 2 , which is a star with centre in S 1 and at least 2 leaves (which must belong to S 2 ). We may define Ψ 13 -and Ψ 23 -gadgets similarly. Call a rigid 3-colouring Ψ-gadget free if there are no Ψ 12 or Ψ 13 or Ψ 23 gadgets. Note that these 3-colourings form an adequate family, since each leftmost 3-colouring is Ψ-gadget free. By analysing such families of 3-colourings we may reduce the upper bound on θ + 3 slightly -see [START_REF] Fountoulakis | On the upper bound of the non-3-colourability threshold of random graphs[END_REF] and [10].

Since x 0 = 0, the expression on the right hand side is 0 if and only if

is strictly less than zero for u < 1, and its only root in (0, 1] is u = 1. This follows from the monotonicity of 1e -2(1-u) u -2(1u) with respect to u. Note, also, that for u = (1e -2 )/2, we have x 0 = 2. Since u < 1/2, the monotonicity of x 0 with respect to u implies that x 0 (1/2) < 2. This observation along with the above result yield x 0 > 2(1u)/u, which implies that 1

Hence, the derivative of (1u)/x 0 with respect to u is positive, and, therefore, this is a strictly increasing function with respect to u. Thus, for u ≤ 1, this is an increasing function. We will use this fact to obtain a lower bound for f (t, r) for specific t, r.

B Some calculations from Subsection 3.4 In this Appendix we present the elementary but tedious calculations for the function P ′ (k, α, λ) on D, as it was defined in Subsection 3.4:


Vince Grolmusz
email: grolmusz@cs.elte.hu

A Note on Set Systems with no Union of Cardinality 0 Modulo m

Keywords: Set systems, composite modulus, polynomials over rings

proved that for any hypergraph F = {F 1 , F 2 , . . . , F d(q-1)+1 }, where q is a prime-power, and d denotes the maximum degree of the hypergraph, there exists an F 0 ⊂ F , such that | F∈F 0 F| ≡ 0 (mod q). The main tool of the proof was a one-to-one correspondence between hypergraphs and polynomials. We give a direct, alternative proof to this correspondence, and also review its implications for set-systems following from the result of Barrington, Beigel and Rudich (Comput. Complexity, 4 (1994), 367-382) for certain mod 6 polynomials.

Introduction

Alon, Kleitman, Lipton, Meshulam, Rabin and Spencer [START_REF] Alon | Set systems with no union of cardinality 0 modulo m[END_REF] gave the following definition: Definition 1 ([1]) For integers d, m ≥ 1, let f d (m) denote the smallest t such that for any hypergraph F = {F 1 , F 2 , . . . , F t } with maximum degree d there exists a non-empty F 0 ⊂ F , such that | F∈F 0 F| ≡ 0 (mod m) Baker and Schmidt [START_REF] Baker | Diophantine problems in variables restricted to the values 0 and 1[END_REF] defined the following quantity:

Definition 2 For integers d, m ≥ 1, let g d (m) denote the smallest t such that for any polynomial h ∈ Z[x 1 , x 2 , . . . , x t ] of degree d, satisfying h(0) = 0, there exists an 0 = ε ∈ {0, 1} n , such that h(ε) ≡ 0 (mod m).
The following theorem was proven in [START_REF] Alon | Set systems with no union of cardinality 0 modulo m[END_REF]:

Theorem 3 ([1]) f d (m) = g d (m)
In the next section we give a natural one-to-one correspondence between polynomials and hypergraphs, proving Theorem 3.

For p prime, and α positive integer it is known ([1], [START_REF] Baker | Diophantine problems in variables restricted to the values 0 and 1[END_REF], [START_REF] Tardos | A lower bound on the MOD 6 degree of the OR function[END_REF]) that g d (p α ) = d(p α -1) + 1, so we obtain ) For F = {F 1 , F 2 , . . . , F d(q-1)+1 }, where q is a prime-power, and d denotes the maximum degree of the hypergraph, there exists an

/ 0 = F 0 ⊂ F , such that | F∈F 0 F| ≡ 0 (mod q).
This corollary is a generalization of the undergraduate exercise that from arbitrary m integers, one can choose a non-empty subset, which adds up to 0 modulo m (the d = 1 case).

In 1991, Barrington, Beigel and Rudich [START_REF] Barrington | Representing Boolean functions as polynomials modulo composite numbers[END_REF] gave an explicit construction for polynomials modulo

m = p α 1 1 p α 2 2 . . . p α r r , showing that g d (m) = Ω(d r ).
Since the proof of Theorem 3 (both the original and ours in the next section) gives explicit constructions for hypergraphs from polynomials, the following corollary holds:

Corollary 5 Let m = p α 1 1 p α 2 2 . . . p α r r .
Then there exists an explicitly constructible hypergraph F of maximum degree d, such that |F | = Ω(d r ) and for each /

0 = F 0 ⊂ F it is satisfied that | F∈F 0 F| ≡ 0 (mod m).
The authors of [START_REF] Alon | Set systems with no union of cardinality 0 modulo m[END_REF] gave a doubly-exponential upper bound on f d (m), which was based on a Ramseytheoretic bound of [START_REF] Baker | Diophantine problems in variables restricted to the values 0 and 1[END_REF]. More recently, Tardos and Barrington [START_REF] Tardos | A lower bound on the MOD 6 degree of the OR function[END_REF] showed that

f d (m) = exp(O(d r-1 )).

Correspondence between polynomials and hypergraphs

We give here a short and direct proof for Theorem 3. Let Q denote the set of rationals. It is well known that the set of functions { f : {0, 1} t → Q} forms a 2 t -dimensional vector space over the rationals. One useful basis of this vector space is the set of OR-functions { i∈I x i : I ⊂ {1, 2, . . . ,t}}, where

i∈I x i = 1 -∏ i∈I (1 -x i ).
It is easy to see that any integer-valued function on the hypercube can be written as the integer-coefficient linear combination of these OR-functions. Moreover, if the function is a degree-d polynomial, then it is enough to use OR functions with |I| ≤ d. If we consider modulo m polynomials, then the coefficients can be restricted to the set {0, 1, 2, . . . , m -1}. It will be convenient to view modulo m polynomials as the sum of several OR functions with coefficient 1; instead of multiplying an OR function with a coefficient a we will add it up exactly a times.

Consequently, our degree-d modulo m polynomial has the following form:

h = S 1 + S 2 + • • • + S ℓ , (1)
where S i is an OR-function of degree at most d. Now we are ready to define the one-to-one correspondence between degree-d modulo m polynomials without non-trivial zeroes on the hypercube and hypergraphs, without non-empty subhypergraphs of modulo-m union-size 0. Let h be a degree-d polynomial written in form [START_REF] Alon | Set systems with no union of cardinality 0 modulo m[END_REF], and define hypergraph F = {F 1 , F 2 , . . . , F t }, where F i = {S j : x i appears as a variable in S j }. Clearly, the degree of this hypergraph is at most the degree of h that is, d.

On the other hand, for a hypergraph F = {F 1 , F 2 , . . . , F t } on the ground-set {v 1 , v 2 , . . . , v ℓ }, let us define

h(x 1 , x 2 , . . . , x t ) = S 1 + S 2 + • • • + S ℓ , where S j = i:v j ∈F i x i .
Obviously, the degree of h is at most the degree of F . Now we state that F has a non-empty subhypergraph with union-size 0 modulo m if and only if there exists a 0 = x : h(x) ≡ 0 (mod m). The proof is as follows: For x = (x 1 , x 2 , . . . , x n ) ∈ {0, 1} n let us denote I(x) = {i : x i = 1}. Then S j (x) = 1 if S j ∈ i∈I(x) F i , and S j (x) = 0 otherwise. Thus h(x) = | i∈I(x) F i | holds for all x ∈ {0, 1} n . In particular, evaluations of h and union-sizes of subhypergraphs in F become divisible by m simultaneously. ✷

1365-8050 c 2003

 2003 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France Corollary 4 ([1]

Acknowledgment.

The author is grateful for the anonymous referee for his/her suggestions clarifying the correspondence between polynomials and hypergraphs. The author also acknowledges the partial support of research grants EU FP5 IST FET No. IST-2001-32012, OTKA T030059.