Almost all graphs with 2.522n edges are not 3-colorable

Dimitris Achlioptas ^{∗}

                 optas@cs.toronto.edu

Michael Molloy ^{†}

                                             molloy@cs.toronto.edu

Department of Computer Science University of Toronto Toronto, Ontario M5S 3G4, Canada.

Abstract

We prove that for c ≥ 2.522 a random graph with n vertices and m = cn edges is not 3-colorable with probability 1 − o(1). Similar bounds for non-k-colorability are given for k > 3.

1991 Mathematics Subject Classification: Primary 05C80; Secondary 05C15.

1 Introduction

Let N(n, m, A) denote the number of graphs with vertices {1, …, n}, m = m(n) edges and some property A. The term “almost all” in the title has the meaning introduced by Erdős and Rényi [5]:

lim_{n→∞} \frac{N(n, m, A)}{\binom{\binom{n}{2}}{m}} = 1 .  (1)

Equivalently, one can consider a random graph G = G(V, E) where |V | = n and E is a uniformly random m-subset of all \binom{n}{2} possible edges on V, i.e. the G(n, m) model of random graphs. If n is an index running over probability spaces, we will say that a sequence of events E_{n} occurs with high probability (w.h.p.) if lim_{n→∞} Pr[E_{n}] = 1. In particular, we will say that “G(n, m(n)) has property A w.h.p.” if m(n) is such that (1) holds for A.

In their seminal paper introducing random graphs [5], Erdős and Rényi pointed out that a number of interesting properties exhibit a sharp threshold behavior on G(n, m): for each such property A, there exists a critical number of edges m_{A}(n) such that for m around m(n) the probability of G(n, m) having A changes rapidly from near 0 to near 1. Such properties include having a multicyclic component, having a perfect matching, connectivity, Hamiltonicity and others.

∗Researh supported in part by an NSERC PGS Scholarship. Current address: Microsoft Research, One Microsoft Way, Redmond WA 98052, U.S.A. Email: optas@microsoft.com

†Researh supported in part by an NSERC grant.

A central property in this context is the k-colorability of G(n, cn) where k is a fixed integer. For k = 2, this is very well-understood as bipartiteness is equivalent to containing no odd cycles. In particular, the probability of non-2-colorability is bounded away from 0 for any c > 0 and keeps increasing gradually with c, reaching 1 − o(1) during the emergence of the giant component at c = 1/2. For k > 2, though, our understanding of k-colorability is not nearly as good; moreover, the situation is conjectured to be quite different. In particular, see [5, 3], Erdős asked: for each k > 2, is there a constant c_{k} such that for any ϵ > 0,

G(n, (c_{k} − ϵ)n) is w.h.p. k-colorable and G(n, (c_{k} + ϵ)n) is w.h.p. not k-colorable ? (2)

Recently, Friedgut [6] made great progress in our understanding of threshold phenomena in random graphs by establishing necessary and sufficient conditions for a property to have a sharp threshold. Using the main theorem of [6], Friedgut and the first author [1] showed that for k > 2, there exists a function t_{k}(n) such that (2) holds upon replacing c_{k} with t_{k}(n), i.e. that indeed k-colorability has a sharp threshold. While it is widely believed that lim_{n→∞} t_{k}(n) exists, confirming this conjecture and determining the limit c_{k}, even for k = 3, seems very challenging.

Perhaps the main tool in attacking the question of k-colorability for small values of k > 2 has been the elementary fact that if a graph has no subgraph with minimum degree at least k, then it is k-colorable. In particular, first Łuczak [11] proved that w.h.p. G(n, cn) remains 3-colorable after the emergence of the giant component by showing that for c ≤ 0.50005, w.h.p. G(n, cn) has no subgraph of minimum degree 3. Shortly afterwards, Chvátal [4] improved this greatly by showing that G(n, cn) w.h.p. has no subgraph with minimum degree 3 for c ≤ 1.44 and Reed and the second author [13] improved the bound even further to c ≤ 1.67. Finally, Pittel, Spencer and Wormald [16], proved that, in fact, for all k > 2 there exists γ_{k} such that for c < γ_{k}, G(n, cn) w.h.p. has no subgraph with minimum degree at least k, while for c > γ_{k} it has such a subgraph w.h.p. Moreover, they determined γ_{k} exactly for all k, in particular yielding c_{3} ≥ γ_{3} = 1.675... Following that, and in aswering a question of Bollobás [3], the second author [14] proved c_{k} > γ_{k} for all k ≥ 4 and conjectured c_{3} ≠ γ_{3} as well. This conjecture was verified recently by the authors [2] after analyzing the performance of a greedy “list-coloring” heuristic on G(n, cn). That argument yielded c_{3} > 1.923, which is the best known lower bound for c_{3}.

In this paper, after briefly reviewing the known upper bounds for c_{k}, we show how a technique of Kirousis et al. [8], developed for random k-SAT, can be used to yield an improved upper bound for c_{k} for small values of k. For example, we obtain

Theorem 1

c_{3} < 2.522 .

2 The first moment method

Grimmett and McDiarmid [7] gave the first lower bound on the chromatic number of random graphs by determining α_{k} such that G(n, m = α_{k}n^{2}) w.h.p. has no independent set of size n/k, and thus χ(G) > k (here k → ∞). Moreover, they conjectured that the lower bound derived by this argument is tight, and as evidence for this they showed that the expected number of k-colorings of G(n, αn^{2}) tends to infinity for α < α_{k}. Devroye (see [4]) later observed that when k is fixed, letting the expected number of k-colorings go to 0 as n → ∞ yields much better lower bounds for the chromatic number than letting the number of (suitably large) independent sets go to 0 as n → ∞.

Our proof can be viewed as a refinement of Devroye’s argument which we will reproduce below to introduce some ideas and notation. Before doing so, let us recall that in the G(n, m) model the edge set is a random m-subset of the set of all \binom{n}{2} possible edges. Equivalently, we can say that the edges of the graph are selected from the set of all possible edges one-by-one, uniformly, independently and without replacement. For the calculations in this paper it will be convenient to consider a slight modification of the G(n, m) model in that the selection is done with replacement, i.e. multiple edges are allowed. We will denote this model by G^{r}(n, m). Intuitively, it is clear that for any monotone increasing property A and any value of m, the probability of A holding in G(n, m) is no smaller than it is in G^{r}(n, m) since “additional occurrences of an edge do not help”. Formally, this is Theorem 5 in [9] and, for our purposes, it will imply that if for a given m(n), G^{r}(n, m(n)) is w.h.p. non-k-colorable then so is G(n, m(n))^{∗}.

We will distinguish between a proper k-coloring of a graph and one in which some adjacent vertices might have the same color by referring to them as a “k-coloring” and a “k-partition”, respectively. In fact, it will be helpful to think of a k-coloring of a graph G(V, E) as a k-partition of V such that every e ∈ E has its endpoints in distinct blocks of the partition, so that each block is an independent set.

Let P = V_{1}, …, V_{k} be an arbitrary (ordered) k-partition of V and let C_{P} denote the event that P is a k-coloring of G. For C_{P} to hold, every edge of the random graph has to connect vertices from two different blocks. Introducing

T (P) = ∑_{i<j} |V_{i}| · |V_{j}| ,  (3)

the total number of pairs of vertices belonging to different blocks, we have

Pr[C_{P}] = (\frac{T (P)}{\binom{n}{2}})^{m} .  (4)

∗In fact, it turns out that since the expected number of multiple edges in G^{r}(n, cn) is O(1) the converse holds as well, i.e. if G(n, cn) is w.h.p. non-k-colorable then so is G^{r}(n, cn). Thus, by switching to the G^{r}(n, m)

model we are not giving anything away with respect to bounding c_{k}.

Now, using the fact ∑_{i} |V_{i}| = n and the Cauchy-Schwartz inequality, respectively, we bound

T (P) = \frac{n^{2}}{2} − \frac{1}{2} ∑_{i} |V_{i}|^{2}

≤ \frac{n^{2}}{2} − \frac{1}{2} · \frac{n^{2}}{k}
= \frac{k − 1}{2k}n^{2} .

Thus, (4) yields

Pr[C_{P}] ≤ (\frac{k − 1}{k})^{m} (\frac{n}{n − 1})^{m} .  (5)

Since the number of k-partitions of V is k^{n}, (5) implies that the expected number of k-colorings of G, for m = cn, is of order

[k (\frac{k − 1}{k})^{c}]^{n} .

Hence, if c > \frac{ln k}{ln k−ln(k−1)} the expected number of k-colorings of G^{r}(n, cn) tends to 0 as n → ∞ implying that G^{r}(n, cn) is w.h.p. non-k-colorable. For k = 3, this argument yields c_{3} < 2.71 and in general c_{k} < k ln k.

It is worth noting that this simple argument is asymptotically tight: the upper bound on χ(G(n, m)) given by Łuczak [10] implies that for any ϵ > 0 and all k ≥ k_{0}(ϵ), c_{k} > (1−ϵ)k ln k. On the other hand, the following two observations can be used to show that for k > 2 this argument is not exact: (a) if a k-colorable graph has s_{i} vertices of degree i then it has at least ∏_{i=0}^{k−1}(k − i)^{s_{i}} distinct k-colorings and (b) with extremely high probability, for every fixed i, G(n, cn) has Ω(n) vertices of degree i. If X is the number of k-colorings of G(n, cn), using (a),(b), one can show that there are values of c such that for some a > b > 1: (i) E[X] ≈ b^{n} and (ii) w.h.p. if X > 0 then X > a^{n}. Hence, for such c, Pr[X > 0] ≤ (a/b)^{n} + o(1) = o(1), while E[X] is exponentially large. Thus, it is not the case that G(n, cn) is w.h.p. k-colorable for exactly those values of c for which its expected number of k-colorings is large.

Indeed, Reed and the second author [13] proved that this “naive” first moment argument is quite a bit off the mark for k = 3. To that end, they first extended the argument to uniformly random pseudographs on a given degree sequence (for a definition see also [15]). In particular, they proved that such a pseudograph with ρn edges is w.h.p. non-k-colorable if ρ > \frac{ln k}{ln k−ln(k−1)}. Then, in order to improve over the naive bound, they considered the random pseudograph resulting by repeatedly (20 times) removing all vertices of degree less than 3 from G(n, m = cn). They proved that this pseudograph (i) is uniformly random with respect to its degree sequence and (ii) if c ≥ c_{0} = 2.571..., then w.h.p. it has at least ρn edges where ρ > \frac{ln 3}{ln 3−ln 2}. Hence, w.h.p. G(n, m = c_{0}n) contains a non-3-colorable subgraph, implying c_{3} < 2.572.

Inspired by the work of Kirousis et al. [8], we will take a less direct but more fruitful approach towards accounting for the wastefulness of the first moment method. Instead of focusing on the low degree vertices explicitly, we will prove the following: if P is a k-coloring of G ∈ G(n, cn) and we randomly pick a vertex v, then with probability ϕ = ϕ(k, c) > 0 we can assign a different color to v and still have a k-coloring of G. This suggests that when k-colorings exist, they tend to appear in large “clusters” of similar colorings. The approach of Kirousis et al. [8], when translated to coloring, suggests that instead of counting all the k-colorings of a random graph (as the first moment does) we should only count a few “representative” ones. Following this idea we will consider as representatives those k-colorings satisfying a certain “local maximality” condition and determine their expected number in G^{r}(n, cn). Letting that expectation go to 0 as n → ∞ will yield c_{3} < 2.522.

3 A refinement of the first moment method

Recall that for a k-partition P = V_{1}, V_{2}, …, V_{k} of V, C_{P} denotes the event that P is a k-coloring of G. Let us say that a vertex v ∈ V_{i} is unmovable in P if for every j > i the partition resulting by moving v to V_{j} is not a k-coloring of G. We will say that P is a rigid k-coloring of G if C_{P} holds and every vertex is unmovable in P. We will denote this event by R_{P}. Note now that if we consider the k-partitions of V as strings of length n over {1, …, k} then, clearly, the lexicographically last k-coloring of G (if any k-coloring exists) is rigid by definition. Hence, G has a rigid k-coloring iff it is k-colorable, implying that the probability that G^{r}(n, cn) is k-colorable is bounded by the expected number of rigid k-colorings of G^{r}(n, cn). With this in mind, we take m = cn and seek c = c(k) for which this last expectation tends to 0 as n → ∞.

Remark: Note that requiring k-colorings to be rigid, immediately eliminates all the redundant counting caused by vertices of degree k −1 or less; only the k-colorings which assign every such vertex the greatest possible color get counted.

3.1 Probability Calculations

For every k-partition P = V_{1}, V_{2}, …, V_{k} of V we let

α_{i} = α_{i}(P) = \frac{|V_{i}|}{n} .

Also, recalling (3), we let

τ = τ(P) = \frac{T (P)}{n^{2}} .  (6)

It is well-known that for any c > 0, the largest independent set of G(n, cn) w.h.p. contains only a constant fraction of all vertices. Thus, the probability that G(n, cn) has a k-coloring where only one color class contains Ω(n) vertices is o(1). Hence, in the following we only consider partitions P in which at least two blocks have Ω(n) vertices (and bound the expected number of rigid k-colorings among such partitions).

We will first bound Pr[R_{P}]. For this, using (5), it suffices to bound Pr[R_{P} | C_{P}].

For a given k-coloring P, any i, any vertex v ∈ V_{i}, and any j > i we let E(v, j) denote the event “v cannot be moved to V_{j}”. Thus,

Pr[R_{P} | C_{P}] = Pr [ ⋂_{{i<j \atop v∈V_{i}}} E(v, j)| C_{P} ] .  (7)

Letting E(v, j) = {{v, w} : w ∈ V_{j}}, we see that E(v, j) occurs iff at least one member of E(v, j) is an edge of G. Note that since we have conditioned on C_{P}, only two-element sets {v, w} enumerated by T (P) can appear in the graph. Thus, since the edges of G were chosen uniformly, independently and with replacement,

Pr[E(v, j) | C_{P}] = 1 − (1 − \frac{|V_{j}|}{T (P)})^{m}  (8)
= 1 − e^{−α_{j}c/τ} + O(n^{−1}) ,  (9)

where the passage from (8) to (9) relies on the fact that P has more than one blocks with Ω(n) vertices and, thus, T (P) = Ω(n^{2}). (This is our only use of the fact that there are more than one blocks with Ω(n) vertices.)

To bound Pr[R_{P} | C_{P}] using (7),(9) we first observe that the sets E(v, j) induce a partition of the set of two-element sets {v, w} enumerated by T (P), since each {v, w} where v ∈ V_{i}, w ∈ V_{j} and i < j belongs to exactly one such set, namely E(v, j). Since the total number of edges is fixed and each event E(v, j) “consumes” at least one edge of E, it is intuitively clear that the events E(v, j) should be negatively correlated. To prove this assertion, we view the formation of E (conditional on C_{P}) as an allocation scheme with m distinguishable balls, T (P) boxes, and a partition of the set of boxes into disjoint subsets E(v, j), (v ∈ V_{i}, i < j). Thus, the occurrence of E(v, j) simply means that the total occupancy of boxes from E(v, j) is at least one. Now, the negative correlation of the events E(v, j) follows from a classical result of McDiarmid [12]. As a result we get

Pr[R_{P} | C_{P}] ≤ ∏_{{i<j \atop v∈V_{i}}} Pr[E(v, j)] ,  (10)

and, thus, using (7),(9) and (10) we get

Pr[R_{P} | C_{P}] ≤ ∏_{1≤i<j≤k} (1 − e^{−α_{j}c/τ} + O(n^{−1}))^{α_{i}n}

= ( ∏_{2≤j≤k} (1 − e^{−α_{j}c/τ})^{∑^{i<j} α_{i}})^{n} × O(1) .  (11)

Having bounded Pr[R_{P} | C_{P}], we bound the expected number of rigid k-colorings, E[R(G)], as follows. For k-partitions P_{1} = V_{1}^{1}, …, V_{k}^{1} and P_{2} = V_{1}^{2}, …, V_{k}^{2}, we say that P_{1} is isomorphic to P_{2} if |V_{i}^{1}| = |V_{i}^{2}|, for all i. Clearly, if P_{1}, P_{2} are isomorphic then Pr[R_{P_{1}}] = Pr[R_{P_{2}}]. Let P be any maximal set of non-isomorphic k-partitions of V. Then

E[R(G)] = ∑_{P} Pr[R_{P}]

= ∑_{P ∈P} \binom{n}{α_{1}n, …, α_{k}n} Pr[R_{P}]

≤ max_{P ∈P} [\binom{n}{α_{1}n, …, α_{k}n} Pr[R_{P}]] n^{k−1} ,  (12)

as there are at most n^{k−1} (ordered) partitions of n into k integers. Moreover, if n > 0 and all α_{i}n are integers it is well-known that

\binom{n}{α_{1}n, …, α_{k}n} < (\frac{1}{α_{1}^{α_{1}} ⋯ α_{k}^{α_{k}}} )^{n} , where 0^{0} ≡ 1.  (13)

Thus, combining (4),(6) and (11)–(13) we have

E[R(G)] ≤ (max_{P ∈P} f(P))^{n} × O(n^{k−1})  (14)

where

f(P) = \frac{(2 ∑_{i<j} α_{i}α_{j})^{c}}{α_{1}^{α_{1}} ⋯ α_{k}^{α_{k}}} ∏_{2≤j≤k} (1 − e^{−α_{j}c/τ})^{∑^{i<j} α_{i}} .  (15)

Letting Q = {q/n : q ∈ {0, …, n}}, it is clear that maximizing f over P ∈ P amounts to maximizing the right-hand side of (15) over Q^{k} subject to ∑_{i} α_{i} = 1. Naturally, we still get an upper bound on E[R(G)] if we relax each such α_{i} to an arbitrary real number in [0, 1] and maximize the extended function, g, over D = [0, 1]^{k} subject to ∑_{i} α_{i} = 1. If for some c^{∗} = c^{∗}(k) the resulting maximum of g is strictly less than 1, then (14) implies that E[R(G)] → 0 as n → ∞ and, thus, that G^{r}(n, c^{∗}n) is w.h.p. non-k-colorable.

It is straightforward to verify that g is continuous, differentiable and its gradient is bounded on D. As a result, g can be maximized numerically with arbitrarily good, guaranteed precision (we used Maple [18] and the code in [17]). For example, for k = 3 we have

g(α_{1}, α_{2}, α_{3}) = \frac{(2τ_{3})^{c} (1 − e^{−α_{2}c/τ_{3}})^{α_{1}} (1 − e^{−α_{3}c/τ_{3}})^{α_{1}+α_{2}}}{α_{1}^{α_{1}}α_{2}^{α_{2}}α_{3}^{α_{3}}}

where τ_{3} = α_{1}α_{2} + α_{1}α_{3} + α_{2}α_{3}. For c^{∗} = 2.5217, g is maximized around α_{1} = 0.30746, α_{2} = 0.33527, α_{3} = 0.35727 and at that vicinity it is strictly less than 0.9999744. Thus, G^{r}(n, m = c^{∗}n) is w.h.p. non-k-colorable, implying c_{3} < 2.522.

Similarly, we get the following new bounds for c_{k} for 3 ≤ k ≤ 7. (The choice of 7 is rather arbitrary, as the numerical computations remain manageable for substantially larger k.)

k  3  4  5  6  7
First moment bound 2.710 4.819 7.213 9.828 12.714
New bound  2.522 4.587 6.948 9.539 12.316

The above table gives an idea of how our improvement over the first moment bound scales with k. Recalling that the first moment bound is asymptotically tight, we see that already for k = 7 the improvement has dropped to less than 3% from 7% for k = 3.

It seems clear that one could improve the upper bound on c_{k} somewhat further by imposing a stricter local maximality condition. For example, one could consider conditions that involve “moving” two vertices at a time. Unfortunately, the lack of “independence” between the outcomes of different moves in that setting seems to complicate matters greatly.

Acknowledgements

We would like to thank the authors of [8] for providing us with an early draft of their paper and an anonymous referee for many valuable comments.

References

[1] D. Achlioptas, E. Friedgut, A sharp threshold for k-colorability, Random Structures & Algorithms, 14 (1999), 63–70.

[2] D. Achlioptas, M. Molloy, The analysis of a list-coloring algorithm on a random graph, 38th Annual Symposium on Foundations of Computer Science, Miami, FL (1997), 204–212.

[3] N. Alon, J.H. Spencer, The Probabilistic Method, with an Appendix of open problems by P. Erdős, J. Wiley & Sons, New York, 1992.

[4] V. Chvátal, Almost all graphs with 1.44n edges are 3-colorable, Random Structures & Algorithms, 2 (1991), 11–28.

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

[6] E. Friedgut, Necessary and sufficient conditions for sharp thresholds of graph properties, and the k-SAT problem, Journal of the American Mathematical Society, 12 (1999), 1017–1054.

[7] G.R. Grimmett, C.J.H. McDiarmid, On colouring random graphs, Mathematical Proceedings of the Cambridge Philosophical Society, 77 (1975), 313–324.

[8] L. M. Kirousis, E. Kranakis, D. Krizanc, and Y. Stamatiou, Approximating the unsatisfiability threshold of random formulas, Random Structures & Algorithms, 12 (1998), 253–269.

[9] L. M. Kirousis, Y. Stamatiou, An inequality for reducible increasing properties of random words, Technical Report, Computer Technology Institute, Greece, (1997), 1–3.

[10] T. Łuczak, The chromatic number of random graphs, Combinatorica, 11 (1991), 45–54.

[11] T. Łuczak, Size and connectivity of the k-core of a random graph, Discrete Mathematics, 91 (1991), 61–68.

[12] C.J.H. McDiarmid, On a correlation inequality of Farr, Combinatorics, Probability and Computing, 1 (1992), 157–160.

[13] M. Molloy, The chromatic number of sparse random graphs, M. Math Thesis, University of Waterloo, (1992).

[14] M. Molloy, A gap between the appearances of a k-core and a (k + 1)-chromatic graph, Random Structures & Algorithms, 8 (1996), 159–160.

[15] M. Molloy, B. Reed, A critical point for random graphs with a given degree sequence, Random Structures & Algorithms, 6 (1995), 161–179.

[16] B. Pittel, J.H. Spencer, and N.C. Wormald, Sudden emergence of a giant k-core in a random graph, Journal of Combinatorial Theory Series B, 67 (1996), 111–151.

[17] W.H. Press, S. Teukolsky, W.T. Vetterling, and B.P. Flannery, Numerical recipes in C, Cambridge University Press, Cambridge, 1992.

[18] D. Redfern, The Maple Handbook: Maple V Release 3, Springer, New York,