A note on the non-colorability threshold of a random graph

Alexis C. Kaporis, Lefteris M. Kirousis, and Yannis C. Stamatiou University of Patras Department of Computer Engineering and Informatics Rio 265 00, Patras, Greece. e-mail: {kaporis,kirousis,stamatiu}@ceid.upatras.gr Third author also: Computer Technology Institute 61 Riga Feraiou Str., GR 262 21, Patras, Greece.

Submitted: April 6, 2000; Accepted: May 23, 2000

Abstract

In this paper we consider the problem of establishing a value r_{0} such that almost all random graphs with n vertices and rn edges, r > r_{0}, are asymptotically not 3-colorable. In our approach we combine the concept of rigid legal colorings introduced by Achlioptas and Molloy with the occupancy problem for random allocations of balls into bins. Using the sharp estimates obtained by Kamath et al. of the probability that no bin is empty after the random placement of the balls and exploiting the relationship between the placement of balls and the rigid legal colorings, we improve the value r_{0} = 2.522 previously obtained by Achlioptas and Molloy to r_{0} = 2.495.

1 Introduction

In this paper, we consider the problem of computing the smallest value r_{0} such that almost all graphs with rn edges, r > r_{0}, are not 3-colorable. We say that a graph G(V, E) is 3-colorable if the set V of its vertices can be partitioned into 3 nonempty cells V_{1}, V_{2}, and V_{3} such that no two vertices of the same partition are adjacent. This partition is called a 3-coloring of G and the vertices of the set V_{j}, j = 1, 2, 3 are said to have color j.

Like many other combinatorial problems on random structures (e.g. formulas, graphs etc.), there appears that the property of a graph being 3-colorable exhibits a threshold behavior. That is, it is believed, and supported by experimental evidence, that there exists a critical constant r_{c} such that a randomly generated graph with n vertices and (r_{c} − ϵ)n edges is 3-colorable with high probability while the opposite is true for a randomly generated graph with (r_{c} + ϵ)n edges. While the question of existence of this critical value is still open (as it is also for the unsatisfiability threshold for random formulas), there have been established rigorously upper and lower bounds for this value. The best lower bound is currently 1.923 and has been obtained by Achlioptas and Molloy in [1] while the best upper bound is 2.522 by the same authors (see [2]).

In order to introduce our method, we will briefly discuss the first moment method that makes use of Markov’s inequality and gives as an upper bound to the non-colorability threshold the value 2.7. Let P = (V_{1}, V_{2}, V_{3}) be an arbitrary but fixed partition of the vertex set V of a graph G(V, E) and let C_{P} denote the event that P is a 3-coloring of the graph G. The number of edges that are allowed to exist in a graph with this 3-coloring is

∑_{i<j} |V_{i}||V_{j}|, i, j ∈ {1, 2, 3}.

When considering a random graph formed by selecting uniformly at random m = rn edges with repetitions allowed, the probability to select an edge that does not invalidate P is

\frac{∑_{i<j} |V_{i}||V_{j}|}{\binom{n}{2}}.

Therefore,

Pr[P is a 3-coloring of G] = Pr[C_{P}] = (\frac{∑_{i<j} |V_{i}||V_{j}|}{\binom{n}{2}} )^{rn} .

If the random variable #P counts the number of 3-colorings of a random graph G, then the following Markov inequality holds:

Pr[G has a 3-coloring] = Pr[#P ≥ 1] ≤ E[#P] = ∑_{P =(V_{1},V_{2},V_{3})} Pr[C_{P}]

≤ 3^{n} ( max_{P =(V_{1},V_{2},V_{3})} \frac{∑_{i<j} |V_{i}||V_{j}|}{\binom{n}{2}} )^{rn} .  (1)

The right-hand side of Inequality(1) vanishes for values of r greater than 2.7. Thus, almost all graphs with more than 2.7n edges do not possess a 3-coloring.

Despite its simplicity, the above argument, also known as the first moment method, does not give the smallest possible value for r. For values of r < 2.7, the expectation of the number of 3-colorings diverges although it has been experimentally observed that almost all randomly generated graphs with a little less than 2.7n edges do not have a 3-coloring. The reason for this phenomenon is that for values of r less than 2.7 there are a few graphs that possess very large numbers of 3-colorings such that, although they quickly disappear when n tends to infinity, they still contribute greatly to the expectation.

A first step towards improving the upper bound derived from Markov’s inequality was taken by Dunne and Zito in [5] (see also [16]) where they adapted the method of locally maximum satisfying truth assignments that was introduced by Kirousis et al. in [10] for improving the unsatisfiability threshold of random 3-SAT formulas. From the set of legal colorings of a graph, Dunne and Zito singled out the special colorings that satisfy a maximality condition that, however, is a weaker form of maximality than the one considered in [10]. This has as an effect a smaller right-hand side in (1) that results in the improved upper bound value 2.602. In [2], Achlioptas and Molloy introduced a more restricted set of legal colorings that they call rigid legal colorings that correspond exactly to the notion of locally maximum truth assignments used in [10] for the 3-SAT problem. This resulted in a still lower right-hand side in (1) and a further improvement of the upper bound to 2.522. However, the two approaches given in [2] and [5] suffer from the disadvantage of computing a certain probability that involves the conjunction of a number of negatively correlated events using the product of the probabilities of each of the events as an upper bound. In our approach, a key step to further improving the upper bound obtained in [2] is the exact computation of the probability involving the conjunction of the events using the occupancy problem for random placements of balls into bins. We make use of the sharp estimates obtained by Kamath et al. in [8] for the probability of the event that no bin remains empty after the placement of the balls in order to compute the probability mentioned above. A similar approach for the 3-SAT problem was followed by Kaporis, Kirousis, Stamatiou, Vamvakari, and Zito in [9] (see also [16]).

In the sections to follow, we will explain the analogy of our problem with the occupancy problem and we will describe the computations that allowed us to obtain as an upper bound to the threshold of non 3-colorability the value 2.495. Throughout the paper, we will follow the definitions and notations of Achlioptas and Molloy ([2]) which we will reproduce for reasons of convenience.

2 Restricted sets of 3-colorings

Consider an arbitrary but fixed coloring P = (V_{1}, V_{2}, V_{3}). It will help to imagine P as a partition into three cells of the vertex set V of the graph G(V, E) such that no edge e ∈ E connects two vertices of the same cell. In our method, we assume that a vertex with color i, i = 1, 2, 3 can be changed to a different color j, j = 1, 2, 3 only if j > i, i.e. only when color j is “higher” than color i.

We say that a vertex u of color i is unmovable if every change to a higher indexed color j invalidates the coloring P. Thus, u of color i is unmovable if it is adjacent with at least one vertex of every cell V_{j}, such that j > i. Then P is a rigid coloring of a graph G, if P makes every vertex of G unmovable. This event will be denoted by R_{P}. From all possible 3-colorings of a random graph, only its rigid colorings are used in order to obtain a smaller expression for the right-hand side in (1). If by R^{♯} we denote the set of rigid 3-colorings of a random graph, it can be easily proved (see [10] for the analogous proof for 3-SAT) that the following Markov type inequality holds:

Pr[G has a 3-coloring] ≤ E[|R^{♯}|] = ∑_{P =(V_{1},V_{2},V_{3})} Pr[R_{P} | C_{P}]Pr[C_{P}].  (2)

As in 3-SAT, this improves the value 2.7 obtained by the simple first moment argument above. The value obtained with the rigid colorings technique is equal to 2.495. In what follows, we will be concerned with the computation of Pr[R_{P} | C_{P}].

3 Asymptotic approximations to probabilities using the occupancy problem

In this section, we will compute the asymptotic probability of the conditional event R_{P} |C_{P} following a line of reasoning similar to that in [9]. First, fix a 3-coloring P_{0}:

P_{0} = (V_{1}, V_{2}, V_{3}), such that, |V_{1}| = α_{0}n, |V_{2}| = β_{0}n, |V_{3}| = γ_{0}n,
α_{0} + β_{0} + γ_{0} = 1, α_{0}, β_{0}, γ_{0} ≥ 0.

Since we condition on the event C_{P_{0}}, in each of the rn edge selections no edge with both its endpoints into a part V_{j}, j = 1, 2, 3 is allowed to appear. The number of edges that do not violate this constraint is (α_{0}β_{0} + α_{0}γ_{0} + β_{0}γ_{0})n^{2}. Thus we obtain,

Pr[C_{P_{0}}] = [2(α_{0}β_{0} + α_{0}γ_{0} + β_{0}γ_{0})]^{rn} = [2(α_{0}β_{0} + (α_{0} + β_{0})(1 − α_{0} − β_{0}))]^{rn}.  (3)

When conditioning on the event C_{P_{0}}, the random graphs of the resulting probability space may contain edges only from within the edges that connect vertices of different partitions of P_{0}. The number of possible edges connecting parts V_{1}, V_{2} is α_{0}β_{0}n^{2}. For each of these edges, their endpoint that belongs to V_{1} is unmovable to V_{2} since their other endpoint belongs to V_{2}. Also, α_{0}γ_{0}n^{2} and β_{0}γ_{0}n^{2} are the numbers of possible edges between vertices of partitions V_{1}, V_{3} and V_{2}, V_{3} respectively. Let E_{ij}, i < j denote the event that an edge between vertices of the parts V_{i}, V_{j} is chosen. Thus, in each edge selection of the rn exactly one of the three possible events E_{12}, E_{13}, E_{23} must be realized. The corresponding probabilities are:

Pr[E_{12}] = \frac{α_{0}β_{0}}{α_{0}β_{0} + α_{0}γ_{0} + β_{0}γ_{0}} , Pr[E_{13}] = \frac{α_{0}γ_{0}}{α_{0}β_{0} + α_{0}γ_{0} + β_{0}γ_{0}} ,
Pr[E_{23}] = \frac{β_{0}γ_{0}}{α_{0}β_{0} + α_{0}γ_{0} + β_{0}γ_{0}} ,

with α_{0} + β_{0} + γ_{0} = 1 and α_{0}, β_{0}, γ_{0} ≥ 0. Let λ_{1}, λ_{2}, λ_{3} be random variables counting the number of selected edges (repetitions counted) joining vertices from the pairs of partitions (V_{1}, V_{2}), (V_{1}, V_{3}) and (V_{2}, V_{3}) respectively. It is clear that the joint distribution of the r.v.’s λ_{1}, λ_{2}, λ_{3} is the multinomial distribution (see [6]). In the remaining of the paper we will consider z as 1 − x − y end γ as (1 − α − β). Also, for notational convenience, we will denote by ”(xrn, yrn, (1 − x − y)rn) the event [λ_{1} = xrn, λ_{2} = yrn, λ_{3} = (1 − x − y)rn]. Similarly, by V (αn, βn, γn) we will denote the partitioning of the n nodes in: [|V_{1}| = αn, |V_{2}| = βn, |V_{3}| = (1 − α − β)n]. If we denote by F ≍ G the fact that ln F ∼ ln G, the following holds:

Pr[λ(xrn, yrn, (1 − x − y)rn) | V (αn, βn, (1 − α − β)n)] =

\binom{rn}{xrn, yrn, (1 − x − y)rn}Pr[E_{12}]^{xrn} · Pr[E_{13}]^{yrn} · Pr[E_{23}]^{(1−x−y)rn} ≍

[(\frac{αβ}{x} )^{x} (\frac{α(1 − α − β)}{y})^{y} (\frac{β(1 − α − β)}{1 − x − y})^{1−x−y} \frac{1}{αβ + (α + β)(1 − α − β)}]^{rn} ,

with α + β + γ = 1, α, β, γ ≥ 0 and x + y + z = 1, x, y, z ≥ 0.

We are now ready to make the connection with the problem of placing uniformly at random a number of balls into a number of bins (for a thorough treatment of such problems, see [11]). After the rn edge selections, the λ_{1} = xrn edges that happen to be between vertices of V_{1} and V_{2} must be sufficiently many in order to block every possible change of color of vertices from V_{1} to V_{2}. Each time we select an edge from the αβn^{2} possible edges between V_{1} and V_{2}, a vertex of V_{1} is blocked. We may, thus, say that the selection of an edge of this kind chooses uniformly and with replacement a single vertex of V_{1} to make it unmovable to V_{2}. But there are αn vertices colored V_{1} that must be blocked. In order to compute the probability that all such vertices are blocked, we can view these xrn selections of edges as distinct balls and the set of αn vertices as bins. Therefore, the above process of choosing edges connecting one vertex from V_{1} with another vertex of V_{2} thus blocking vertices in V_{1}, may be viewed as throwing randomly and uniformly xrn balls into αn cells. Consequently, the probability that all vertices in V_{1} are blocked from changing color to V_{2} is equal to the probability that no cell remains empty after the random placement of the xrn balls. Exactly the same line of reasoning can be applied for edges between vertices in V_{1}, V_{3} and V_{2}, V_{3}.

The following theorem will be our main tool in establishing sharp estimates of the occupancy probabilities mentioned above, i.e. the probabilities that no bin remains empty after the random placement of the balls.

Theorem 1 (Kamath, Motwani, Palem, and Spirakis, 1995) Let Z denote the number of empty bins after the placement, uniformly and independently, of l balls into k bins. Let also c = l/k. If by H(l, k, z) we denote the probability that Z = z and if, in addition, |z − E[Z]| = Ω(k) then,

H(l, k, z) ≍ e^{−k[∫_{0}^{1−z/k} ln((u_{z}−t)/(1−t))dt−c ln u_{z}]},

where u_{z} is the solution of the equation,

z = k(1 − u(1 − e^{−c/u})).  (4)

In our case, we will set z = 0. Also, in all three cases of color changes considered above the precondition |z − E[Z]| = Ω(k) holds. For example, in the case of change of color of vertices from V_{1} to V_{2}, we have l = xrn and k = αn. Then for z = 0

|z − E[Z]| = |0 − k(1 − \frac{1}{k})^{l}| ∼ αne^{−xr/α} = Ω(k).

Let u_{0} denote the solution of Equation (4) for z = 0. Assuming k ≠ 0, Equation (4) for z = 0 is equivalent to the equation u_{0}(1 − e^{−c/u_{0}}) = 1. Thus, if by V_{i} ↛ V_{j} we denote the event that all vertices in V_{i} are unmovable to V_{j}, the following are deduced from the above remarks:

Pr[V_{1} ↛ V_{2}|λ_{1} = xrn, |V_{1}| = αn] ≍ e^{−α[∫_{0}^{1} ln((u_{12}−t)/(1−t))dt−c_{12} ln u_{12}]},
Pr[V_{1} ↛ V_{3}|λ_{2} = yrn, |V_{1}| = αn] ≍ e^{−α[∫_{0}^{1} ln((u_{13}−t)/(1−t))dt−c_{13} ln u_{13}]},
Pr[V_{2} ↛ V_{3}|λ_{3} = (1 − x − y)rn, |V_{2}| = βn] ≍ e^{−β[∫_{0}^{1} ln((u_{23}−t)/(1−t))dt−c_{23} ln u_{23}]}.

It can be easily verified that,

u_{12} = 1/[1 − e^{−c_{12}}ϕ_{2}(c_{12}e^{−c_{12}})] = 1/[1 + LambertW(−c_{12}e^{−c_{12}})/c_{12}],
u_{13} = 1/[1 − e^{−c_{13}}ϕ_{2}(c_{13}e^{−c_{13}})] = 1/[1 + LambertW(−c_{13}e^{−c_{13}})/c_{13}],
u_{23} = 1/[1 − e^{−c_{23}}ϕ_{2}(c_{23}e^{−c_{23}})] = 1/[1 + LambertW(−c_{23}e^{−c_{23}})/c_{23}],
c_{12} = \frac{xr}{α} ≥ 1, c_{13} = \frac{yr}{α} ≥ 1, c_{23} = \frac{(1−x−y)r}{β} ≥ 1,

(5)

where ϕ_{2}(t) is defined as the smallest root of ϕ_{2}(t) = e^{tϕ_{2}(t)} and can be expressed through the Lambert W function (see [3] for information on the Lambert W function and its properties).

Let D = {(α, β, x, y)| (α, β, x, y) ⊆ [0, 1]^{4}} such that each quadruple (α, β, x, y) ∈ D satisfy the conditions:

α + β ≤ 1, α, β ≥ 0,
x + y ≤ 1, x, y ≥ 0,
x ≥ \frac{α}{r}, y ≥ \frac{α}{r}, 1 − x − y ≥ \frac{β}{r} .

By (α_{0}, β_{0}, x, y) ∈ D we denote the fact that the first two variables are fixed, while x, y are chosen arbitrarily from D.

Theorem 2 The probability of the conditional event R_{P_{0}}|C_{P_{0}} is the following:

∑_{(α_{0}, β_{0}, x, y) ∈ D} Pr[λ(xrn, yrn, (1 − x − y)rn) | V (α_{0}n, β_{0}n, (1 − α_{0} − β_{0})n)]

·Pr[V_{1} ↛ V_{2}, V_{1} ↛ V_{3}, V_{2} ↛ V_{3} | λ(xrn, yrn, (1 − x − y)rn) ∧V (α_{0}n, β_{0}n, (1 − α_{0} − β_{0})n)]

≍ ∑_{(α_{0}, β_{0}, x, y) ∈ D} [(\frac{α_{0}β_{0}}{x} )^{x} (\frac{α_{0}(1 − α_{0} − β_{0})}{y})^{y} (\frac{β_{0}(1 − α_{0} − β_{0})}{1 − x − y})^{1−x−y}]^{rn}

· [\frac{1}{α_{0}β_{0} + (α_{0} + β_{0})(1 − α_{0} − β_{0})}]^{rn}

· [e^{−α_{0}[(∫_{0}^{1} ln((u_{12}−t)/(1−t))dt−c_{12} ln u_{12})+(∫_{0}^{1} ln((u_{13}−t)/(1−t))dt−c_{13} ln u_{13})]}]^{n}

· [e^{−β_{0}(∫_{0}^{1} ln((u_{23}−t)/(1−t))dt−c_{23} ln u_{23})}]^{n}

= ∑_{(α_{0}, β_{0}, x, y) ∈ D} F(x, y, (1 − x − y) | α_{0}, β_{0}, 1 − α_{0} − β_{0}).  (6)

Taking the expectation of the number of rigid colorings |R^{♯}| and using (3), (5), and (6) we get

E[|R^{♯}|] ≍ ∑_{(α, β, x, y) ∈ D} [2(αβ + (α + β)(1 − α − β)]^{rn}
·F(x, y, 1 − x − y| α, β, 1 − α − β).  (7)

We will now consider an arbitrary term of the double sum that appears in (7) and examine for which values of r it converges to 0. If we find a condition on r that forces such a term to converge to 0, then the whole sum will converge to 0 since it contains polynomially many terms all of which vanish exponentially fast.

An arbitrary term of the double sum in (7) can be bounded from above by the following expression raised to n:

E = (\frac{1}{α^{α}β^{β}(1 − α − β)^{(1−α−β)}} )

· (2 (\frac{αβ}{x} )^{x} (\frac{α(1 − α − β)}{y})^{y} (\frac{β(1 − α − β)}{1 − x − y})^{1−x−y})^{r}

· [e^{−α_{0}[(∫_{0}^{1} ln((u_{12}−t)/(1−t))dt−c_{12} ln u_{12})+(∫_{0}^{1} ln((u_{13}−t)/(1−t))dt−c_{13} ln u_{13})]}]

· [e^{−β_{0}(∫_{0}^{1} ln((u_{23}−t)/(1−t))dt−c_{23} ln u_{23})}] .  (8)

The expression E above is a function of five variables, namely α, β, x, y, and r. Any particular value of r for which E = E(α, β, x, y, r) is strictly less than 1 for all α, β, x, y ∈ D is a value of r for which the n-th power of E(α, β, x, y, r) has limit 0, and hence the probability that the graph has a 3-coloring vanishes asymptotically.

We will show that r = 2.495 is such a value. It makes the calculations easier to consider the natural logarithm of E(α, β, x, y, r) (all the factors of E(α, β, x, y, r) are positive) and show that ln E(α, β, x, y, r) is strictly less than 0 for r = 2.495 and ∀(α, β, x, y) ∈ D.

First observe that, u_{12} is a function of c_{12} which in turn depends only on α and x since r = 2.495. Thus, u_{12} = f_{1}(α, x), c_{12} = f′_{1}(α, x). Similarly, u_{13} = f_{2}(α, y), c_{13} = f′_{2}(α, y), u_{23} = f_{3}(β, 1 − x − y), c_{23} = f′_{3}(β, 1 − x − y). After some easy calculations, we obtain

ln E = −α ln α − β ln β − (1 − α − β) ln(1 − α − β) + r ln 2

+r ln [\frac{α}{(α(1 − x − y))^{(1−x−y)}} ] + r ln [\frac{β}{(βy)^{y}} ] + r ln [\frac{(1 − α − β)}{((1 − α − β)x)^{x}} ]

−α [∫_{0}^{1} ln(\frac{f_{1}(α, x) − t}{1 − t})dt − f′_{1}(α, x) ln f_{1}(α, x)]

−α [∫_{0}^{1} ln(\frac{f_{2}(α, y) − t}{1 − t})dt − f′_{2}(α, y) ln f_{2}(α, y)]

−β [∫_{0}^{1} ln(\frac{f_{3}(β, 1 − x − y) − t}{1 − t})dt − f′_{3}(β, 1 − x − y) ln f_{3}(β, 1 − x − y)] .

We now claim:

Claim 1 For any value of r, the expression ln E as function of (α, β, x, y) ∈ D is convex.

The proof of Claim 1 is given in an appendix.

Given now that ln E is convex, as a function of (α, β, x, y) ∈ D we will compute its maximum value for r = 2.495 and (α, β, x, y) ∈ D. For that purpose we used a Maple (see [12] for information on Maple) implementation of the downhill simplex function optimization method (see [13] for a good description of the method and a C implementation) to the maximize the expression. This implementation, that is based on the exposition and the code given in [13], is freely distributed by F.J. Wright in his Web page [15].

For r = 2.494695 and guided by Maple’s plotting facilities, we chose as a starting set of values for the downhill simplex algorithm the values (α, β, x, y) = (0.3, 0.33, 0.3, 0.3). We set the accuracy parameter equal to 10^{−50} and set the scale of the problem equal to 10^{−50}. Finally, we set the number of decimal digits parameter of Maple equal to 100. We run the algorithm and it returned as the maximum value of ln E the value −0.00000998 with more decimal digits to follow. Notice that since our function is convex, the downhill simplex method does not get trapped at a local maximum.

Additionally, we computed all the partial derivatives of ln E at the point where downhill simplex claims that it has located the maximum and they were found to be in the order of 10^{−48} and they can safely be regarded as equal to 0. Therefore, this provides attitional support that at this point the function attains its maximum.

As a final check, we generated 30000 random points close to the point at which downhill simplex finds the maximum of ln E and we confirmed that the value of ln E is not above the value returned by the method.

The above discussion shows that -0.00000998 is indeed a global maximum. and, therefore, that 2.495 is an upper bound to the non-colorability threshold.

4 Discussion

In this paper we showed how to reduce the upper bound for the non 3-colorability threshold from 2.522 (see [2]) to 2.495 using a method that was used in [9] in order to reduce the upper bound for the unsatisfiability threshold.

More specifically, we considered the set of 3-colorings of a random graph and singled out the rigid 3-colorings, i.e. those colorings such that the change of color of any vertex gives an illegal coloring. This idea stems from the analogous local maxima technique for the satisfying truth assignments of a random formula (see [10]). Then, as a key step, we used sharp probability estimates for the probability that no bin remains empty after the random placement of a number of balls into a number of bins in order to compute the probability of a color assignment being a rigid 3-coloring. This analogy, that also resulted in an improvement of the upper bound for the unsatisfiability threshold in [9], alleviates the problem of overestimating the probability of the conjunction of certain negatively correlated events that appears in the computations. The above approach resulted in an improvement of the simple first moment argument based on Markov’s inequality that, in turn, gave the improved upper bound 2.495 for the non-colorability threshold. Fountoulakis and McDiarmid recently claimed [7] to have independently found the same value as a threshold.

Acknowledgment. We would like to thank Kostas Mpekas for his help on numerical function maximization.

References

[1] D. Achlioptas and M. Molloy, “The analysis of a list-coloring algorithms on a random graph,” in Proc. 38th Annual Symposium on Foundations of Computer Science,

pp 204–212, 1997.

[2] D. Achlioptas and M. Molloy, “Almost all graphs with 2.522n edges are not 3colorable,” Electronic Journal of Combinatorics, 6 (1), 1999.

[3] R.M. Corless, G.H. Gonnet, D.E.G. Hare, D.J. Jeffrey, and D.E. Knuth, “On the Lambert W function,” manuscript, Computer Science Department, University of Waterloo.

[4] O. Dubois and Y. Boufkhad, “A general upper bound for the satisfiability threshold of random r-SAT,” J. of Algorithms 24, pp 395–420, 1997.

[5] P.E. Dunne and M. Zito, “An improved upper bound on the non 3-colourability threshold,” Information Processing Letters, 65, pp 17–23, 1998.

[6] W. Feller, An Introduction to Probability Theory and its Applications, Vol. 1, 3rd Edition, 1968.

[7] N. Fountoulakis and C. McDiarmid, personal communication.

[8] A. Kamath, R. Motwani, K. Palem, and P. Spirakis, “Tail bounds for the occupancy and the satisfiability threshold conjecture,” Random Structures and Algorithms 7, pp 59–80, 1995. Also in: Proc. 35th FOCS, IEEE, pp 592–603, 1994.

[9] A.C. Kaporis, L.M. Kirousis, Y.C. Stamatiou, M. Vamvakari, and M. Zito “The unsatisfiability threshold revisited,” submitted.

[10] L.M. Kirousis, E. Kranakis, D. Krizanc, and Y.C. Stamatiou, “Approximating the unsatisfiability threshold of random formulas,” Random Structures and Algorithms 12, pp 253–269, 1998.

[11] V.F. Kolchin, Random Mappings, Translation series in Mathematics and Engineering, Optimization Software Inc., New York, 1986.

[12] M.B. Monagan, K.O. Geddes, K.M. Heal, G. Labahn, and S.M. Vorkoetter, Programming Guide, Maple V Release 5, Springer–Verlag, 1998.

[13] W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery, Numerical Recipes in C: The Art of Scientific Computing, 2nd edition, Cambridge University Press, 1993.

[14] A.E. Taylor, W.R Mann, Advanced Calculus, 3rd edition, John Wiley & Sons, 1983.

[15] F.J. Wright: http://centaur.maths.qmw.ac.uk/Computer_Algebra/. A Maple

(version V release 5) implementation of Downhill Simplex based on code given in [13].

[16] M. Zito, Randomised Techniques in Combinatorial Algorithmics, PhD Thesis, Department of Computer Science, University of Warwick, November 1999.

5 Appendix

Proof of the Claim 1. Recall that:

ln E = −α ln α − β ln β − (1 − α − β) ln(1 − α − β) + r ln 2

+r ln [\frac{α}{(α(1 − x − y))^{(1−x−y)}} ] + r ln [\frac{β}{(βy)^{y}} ] + r ln [\frac{(1 − α − β)}{((1 − α − β)x)^{x}} ]

−α [∫_{0}^{1} ln(\frac{f_{1}(α, x) − t}{1 − t})dt − f′_{1}(α, x) ln f_{1}(α, x)]

−α [∫_{0}^{1} ln(\frac{f_{2}(α, y) − t}{1 − t})dt − f′_{2}(α, y) ln f_{2}(α, y)]

−β [∫_{0}^{1} ln(\frac{f_{3}(β, 1 − x − y) − t}{1 − t})dt − f′_{3}(β, 1 − x − y) ln f_{3}(β, 1 − x − y)] ,

where (α, β, x, y) ∈ D.

A. −α ln α, as a function of α, β, x, y, is convex. Indeed, the quadratic form of its Hessian (see e.g. [14]) computed at an arbitrary vector (α′, β′, x′, y′) ∈ R^{4} is −\frac{1}{α}(a′)^{2} ≤ 0. So the Hessian is negative semi-definite, so −α ln α is convex, as a function of α, β, x, y. For the same reason −β ln β is convex. Also, if u is a new variable −(1 − u) ln(1 − u) is convex, as it is the reflection of −u ln u with respect to the axis u = 1/2. So, convex also is −(1 − α − β) ln(1 − α − β) as it is obtained from −(1 − u) ln(1 − u) by a linear substitution for u. So convex also is −α ln α − β ln β − (1 − α − β) ln(1 − α − β).

B. r ln \frac{β}{(βy)^{y}}, as a function of α, β, x, y, is convex. Indeed, the quadratic form of its Hessian computed at an arbitrary vector (α′, β′, x′, y′) ∈ R^{4} is

−r [(β′)^{2} \frac{1 − y}{β^{2}} + 2β′y′ \frac{1}{β} + (y′)^{2} \frac{1}{y} ]  (9)

Now, because 0 ≤ y ≤ 1 the above expression is at most,

−r [(β′)^{2} \frac{1 − y}{β^{2}} + 2β′y′ \frac{1}{β} + (y′)^{2}] ≤ −r [(β′)^{2} \frac{1 − y}{β^{2}} + 2β′y′ \frac{1}{β} \sqrt{1 − y} + (y′)^{2}]
≤ −r [\sqrt{1 − y} \frac{β′}{β} + y′]^{2} ≤ 0.

So, the Hessian is negative semi-definite, so r ln \frac{β}{(βy)^{y}} is convex. Similarly, convex is r ln \frac{α}{(a(1−x−y))^{1−x−y}} and r ln \frac{1−α−β}{((1−α−β)x)^{x}}. (Once more, we use here the fact that we can reflect a convex function, with u among its variables, with respect to a hyperplane u = 1/2 and that we can substitute for u a linear expression of other variables without destroying the convexity.)

C.

−α [∫_{0}^{1} ln(\frac{f_{1}(α, x) − t}{1 − t})dt − f′_{1}(α, x) ln(f_{1}(α, x))] = −α [∫_{0}^{1} ln(\frac{u_{12} − t}{1 − t})dt − c_{12} ln u_{12}] ,

(10)

where c_{12} = \frac{rx}{α} and u_{12} = 1/[1 + LambertW(−c_{12}e^{−c_{12}})/c_{12}] is convex as a function of α, β, x, y. Indeed,

∫_{0}^{1} ln(\frac{u_{12} − t}{1 − t})dt = u_{12} ln(u_{12}) − u_{12} ln(u_{12} − 1) + ln(u_{12} − 1).

By equation (4) we have: u_{12}(1 − exp(−c_{12}/u_{12})) = 1, and we obtain:

∫_{0}^{1} ln(\frac{u_{12} − t}{1 − t})dt = c_{12} + ln(u_{12}) − \frac{c_{12}}{u_{12}} .  (11)

From Equations (10, 11) we obtain:

−α [∫_{0}^{1} ln(\frac{u_{12} − t}{1 − t})dt − c_{12} ln u_{12}] = −α [c_{12} + ln(u_{12}) − \frac{c_{12}}{u_{12}} − c_{12} ln u_{12}]

= −xr − α ln(xr) + α ln α + α ln \frac{c_{12}}{u_{12}} + α\frac{c_{12}}{u_{12}}
+xr ln(xr) − xr ln α − xr ln \frac{c_{12}}{u_{12}} .  (12)

The quadratic form of the Hessian of (12) computed at an arbitrary vector (α′, β′, x′, y′) ∈ R^{4} is equal to:

\frac{xre^{−c_{12}/u_{12}}}{e^{−c_{12}/u_{12}} − α/xr} [\frac{α′}{α} − \frac{x′}{x} ]^{2} ≤ 0.  (13)

The last expression is nonpositive, because by Equation (4) we have:

\frac{xr}{α} = \frac{c_{12}/u_{12} e^{c_{12}/u_{12}}}{e^{c_{12}/u_{12}} − 1} ⇔ e^{−c_{12}/u_{12}} − \frac{α}{xr} = \frac{1 + c_{12}/u_{12} − e^{c_{12}/u_{12}}}{c_{12}/u_{12} e^{c_{12}/u_{12}}}

and because 1 + \frac{c_{12}}{u_{12}} ≤ e^{c_{12}/u_{12}}. The computation of the above quadratic form in (13) is somewhat complicated, and depends on computing the partial derivatives of u_{12}, which is implicitly given as the solution of the equation u_{12} = 1/[1+LambertW(−c_{12}e^{−c_{12}})/c_{12}] We omit the tedious algebraic manipulations. (Boufkhad and Dubois [4] give the details of the computation of a very similar quadratic form.) Similarly we show the convexity of:

−α [∫_{0}^{1} ln(\frac{f_{2}(α, y) − t}{1 − t})dt − f′_{2}(α, y) ln f_{2}(α, y)]

and

−β [∫_{0}^{1} ln(\frac{f_{3}(β, 1 − x − y) − t}{1 − t})dt − f′_{3}(β, 1 − x − y) ln f_{3}(β, 1 − x − y)]

This completes the proof of the convexity of ln E as a function of (α, β, x, y) ∈ D.