Critical subgraphs of a random graph

Michael Molloy

Department of Computer Science University of Toronto Toronto, Canada

            molloy@cs.toronto.edu

Bruce Reed

Equipe Combinatoire CNRS Université Pierre et Marie Curie Paris, France

                                              reed@ecp6.jussieu.fr

Submitted: Sept 7, 1998; Accepted: Sept 6, 1999.

Abstract We prove that the threshold for a random graph to have a k-core is equal to the threshold for having a subgraph which meets a necessary condition of Gallai for being k-critical.

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

1 Introduction

In this paper, we examine the random graph G_{n,M} formed by taking n vertices and choosing M edges where each of the \binom{\binom{n}{2}}{M} possible edgesets is equally likely to be chosen. In particular, we will be concerned with the chromatic number of such a graph when M = O(n).

Equivalently, we often discuss the random graph process in which we start with the graph with n vertices and no edges, and repeatedly add an edge chosen uniformly at random from amongst all edges not currently present. Note that G_{n,M} is equivalent to the state of the random graph process after exactly M iterations.

One of the most tantalizing open problems in random graph theory (see for example [11]) is that of determining

d_{k} = sup{d| a.s.^{1}χ(G_{n,M=dn}) ≤ k},

where χ(G) is the chromatic number of G. As is the trend in the study of k-chromatic graphs, the case k = 2 is well-understood - d_{2} = 0 - while the case k ≥ 3 seems much more difficult. In fact, it was only recently shown that for k ≥ 3 the threshold for k-colourability is sharp (see [1] and [14]).

1We say that G_{n,p} almost surely (a.s.) has a property P if lim_{n→∞}{Pr(G_{n,p} has P } = 1.

If G is not k-colourable, then it must have a (k +1)-critical subgraph, i.e. a subgraph H ⊆ G such that χ(H) = k + 1, but χ(H − e) = k for any edge e ∈ E(G). The most well known necessary conditions for a graph to be (k + 1)-critical are (see [9]):

(a) it must have minimum degree at most k;

(b) it must be 2-connected.

Often a property P will a.s. occur for the first time during the random graph process at the exact step in which a weaker property P′ first occurs. For example, a.s. the first graph to have a perfect matching will be the first graph to have minimum degree one [13], and a.s. the first graph to be Hamiltonian will be the first graph to have minimum degree two [17] (see also [8]). Given the nature of these two examples, it is natural to wonder if a.s. the first graph to be (k + 1)-chromatic will be the first graph to have a subgraph with minimum degree k.

Bollobás was the first to consider this approach to the problem of determining d_{k}. He defined the k-core of a graph to be its unique maximal subgraph with minimum degree at least k, if such a subgraph exists. Until recently, all lower bounds on d_{k} have been achieved by bounding the relaxation:

c_{k} = sup{c| a.s. G_{n,M=cn} has no k-core}.

Bollobás [6] proved that a.s. the first k-core to appear is k-connected, thus showing that there would be little benefit to incorporating condition (b) in our search for d_{k}. It was here that he first asked the much repeated question of whether c_{k} = d_{k} for all k ≥ 3.

In [10], Chvátal showed that for c < c^{∗} = 1.442 …, the expected number of subgraphs of G_{n,M=cn} with minimum degree 3 is subexponentially small, while for c > c^{∗}, the expected number of such subgraphs is exponentially large. An immediate corollary is that c_{3} ≥ c^{∗}.

In [19], Molloy and Reed showed that 1.67 ≤ c_{3} ≤ 1.78, and that d_{3} ≤ 2.571. Shortly thereafter, Pittel, Spencer and Wormald [22] successfully determined

c_{k} = min_{y>0} y/2π_{k}(y)
= \frac{1}{2}k + \frac{1}{2}\sqrt{k log k} + O(log k),

with π_{k}(y) = Pr{Poisson(y) ≥ k − 1}. For example, c_{3} = 1.67 . . .. Furthermore, the appearance of a k-core has a very sharp threshold.

Molloy [20] observed that this result can be used to show d_{k} > c_{k} for k ≥ 4. More recently, Achlioptas and Molloy[2] showed that d_{3} > 1.94... > c_{3}, and so there is a significant gap between these two thresholds. Among other things, this indicates that the quest to determine d_{k} may require consideration of other properties of critical graphs.

This paper marks the first time that a nontrivial criticality condition is incorporated in the study of the chromatic number of a random graph.

Given a graph H with minimum degree at least k, we define the low graph of H, L(H), to be the subgraph induced by the vertices of degree k. In [16] Gallai characterized the set of graphs which are the low graphs of (k + 1)-critical graphs:

Theorem L is the low graph of some (k + 1)-critical graph H, k ≥ 2, iff

(a) L has maximum degree at most k;

(b) each block of L is either a clique or a chordless odd cycle.

We say that a graph is k-Gallai if it has minimum degree k and it contains no even cycles whose vertices are all of degree k and do not induce a clique. Thus a graph with minimum degree k is k-Gallai iff its low graph satisfies the conditions of this theorem, and so it implies that any (k + 1)-critical graph must be k-Gallai.

A natural question to ask, particularly in light of the now known gap between c_{k} and d_{k}, is whether c_{k} is also the threshold for the appearance of a k-Gallai subgraph. In this paper we answer this question in the affirmative:

Theorem 1.1 For k ≥ 3 and any ϵ > 0, a.s. G_{n,M=(c_{k}+ϵ)n} has a k-Gallai subgraph.

One implication of this theorem is that in order to compute d_{k}, we may need to study even further properties of k-critical graphs.

We define the edge-density of a graph to be the ratio of the number of edges to the number of vertices in the graph. Let Ω_{n,M}^{k} be the set of all simple graphs with n vertices and M edges and with minimum degree k, and define G_{n,M}^{k} to be a uniformly random member of Ω_{n,M}^{k}. It is well-known (see, for example, [19] or [22]) that every member of Ω_{n,M}^{k} is equally likely to occur as the k-core of the random graph G_{n′,M′}, for any n′, M′, and so upon exposing the number of vertices and edges of the k-core of G_{n,M′}, we can then choose the k-core from the G_{n,M}^{k} model.

Define t_{k} to be the solution to

\frac{t_{k}^{k−1}}{(k − 2)!} = e^{t_{k}} − ∑_{i=0}^{k−2} \frac{t_{k}^{i}}{i!}  (1)

and set

ℓ_{k} = \frac{∑i≥k \frac{it_{k}^{i}}{i!}}{2 ∑_{i≥k} \frac{t_{k}^{i}}{i!}} .

For example, ℓ_{3} = 1.7932..., ℓ_{4} = 2.5377..., ℓ_{5} = 3.2541....

The main step towards proving Theorem 1.1 is the following:

Theorem 1.2

(a) For ℓ < ℓ_{k}, G_{n,M=⌈ℓn⌉}^{k} is k-Gallai with probability at least 1−z^{n} for some constant z < 1.

(b) For ℓ > ℓ_{k}, the probability that G_{n,M=⌈ℓn⌉}^{k} is k-Gallai tends to a constant 0 <

p_{k}(ℓ) < 1.

It is straightforward, using the results of [22] to determine the edge-density of the k-core when it first appears. Perhaps surprisingly, it is asymptotic to precisely ℓ_{k}:

Fact 1.3 For k ≥ 3, a.s. the first k-core to appear during the random graph process has edge-density ℓ_{k} + o(1).

Theorem 1.1 will follow from Fact 1.3 and Theorem 1.2(b), along with a little more work. We will present this proof in the final section of the paper.

The crux of the proof of Theorem 1.2 lies in showing that ℓ_{k} is a threshold for G_{n,M}^{k} in the sense of the celebrated Double Jump Threshold discovered by Erdős and Rényi. In [12] they show that the component structure of G_{n,M=cn} undergoes a dramatic change at the point c = \frac{1}{2}. For c < \frac{1}{2} a.s. all components of G_{n,M=cn} are quite small, very few of them are cyclic, and none have more than one cycle. For c > \frac{1}{2}, a.s. G_{n,M=cn} has a giant component on Θ(n) vertices and containing at least Θ(n) cycles.

In [21], Molloy and Reed showed that a similar phenomenon occurs for random graphs with a given degree sequence. This work was originally developed specifically to be applied to the results in this paper, and plays an important role here. Thus, before proceeding further, it is necessary to summarize the main theorem.

Definition 1.4 An asymptotic degree sequence is a sequence of integer-valued functions D = d_{0}(n), d_{1}(n), … such that

1. d_{i}(n) = 0 for i ≥ n;

2. ∑_{i≥0} d_{i}(n) = n.

Given an asymptotic degree sequence D, we set D_{n} to be the degree sequence {c_{1}, c_{2}, …, c_{n}}, where c_{j} ≥ c_{j+1} and |{j : c_{j} = i}| = d_{i}(n) for each i ≥ 0. We say that D_{n} is an incident of D. We define Ω_{D_{n}} to be the set of all graphs with vertex set [n] with degree sequence D_{n}. A random graph on n vertices with degree sequence D is a uniformly random member of Ω_{D_{n}}.

Definition 1.5 An asymptotic degree sequence D is feasible if Ω_{D_{n}} ≠ ∅ for all n ≥ 1.

Definition 1.6 An asymptotic degree sequence D is smooth if there exist constants λ_{i} such that lim_{n→∞} d_{i}(n)/n = λ_{i}.

Definition 1.7 Given a smooth asymptotic degree sequence, D, Q(D) = ∑_{i≥1} i(i−2)λ_{i}.

Definition 1.8 An asymptotic degree sequence D is sparse if ∑_{i≥0} id_{i}(n)/n = K +o(1) for some constant K.

We omit the definition of well-behaved, but suffice it to say that if for all n, d_{i}(n) = 0 whenever i > Δ for some fixed Δ then D is well-behaved. This will be the case for any degree sequence considered in this paper (although the definition of well-behaved allows for more general situations and so the statement of this theorem is more general than is needed for this paper).

Theorem 1.9 Let D = d_{0}(n), d_{1}(n), … be a well-behaved sparse asymptotic degree sequence for which there exists ϵ > 0 such that for all n and i > n^{\frac{1}{4} −ϵ}, d_{i}(n) = 0. Let G be a graph with n vertices, d_{i}(n) of which have degree i, chosen uniformly at random from amongst all such graphs. Then:

(a) If Q(D) > 0 then there exist constants ζ_{1}, ζ_{2} > 0 dependent on D such that G a.s. has a component with at least ζ_{1}n vertices and ζ_{2}n cycles. Furthermore, if Q(D) is finite then G a.s. has exactly one component of size greater than γ log n for some constant γ dependent on D.

(b) If Q(D) < 0 and for some function 0 ≤ ω(n) ≤ n^{\frac{1}{8} −ϵ}, d_{i}(n) = 0 for all i ≥ ω(n), then for some constant R dependent on Q(D), G a.s. has no component with at least Rω(n)^{2} log n vertices, and a.s. has fewer than 2Rω(n)^{2} log n cycles. Also, a.s. no component of G has more than one cycle.

Consistent with the model G_{n,M}, we call the component refered to in Theorem 1.9(a) the giant component.

As the reader has no doubt guessed, it is a simple matter to use Theorem 1.9 to show that for ℓ < ℓ_{k}, a.s. L(G_{n,M=⌈ℓn⌉}^{k}) has a giant component, while for ℓ > ℓ_{k},

a.s. all components of L(G_{n,M=⌈ℓn⌉}^{k}) are small. In the next section we do this and

show that if L(G_{n,M=⌈ℓn⌉}^{k}) has a giant component then with subexponentially high

probability L(G_{n,M=⌈ℓn⌉}^{k}) has an even cycle whose vertices do not induce a clique, and

if all components of L(G_{n,M=⌈ℓn⌉}^{k}) are small then the probability that no such cycle

exists tends to p_{k}(ℓ), thus proving Theorem 1.2. The reader who is willing to accept these facts on faith may wish to skip Section 2. The reader whose faith is shaken because it seems counterintuitive that L(G_{n,M=⌈ℓn⌉}^{k}) a.s. has a giant component when ℓ is below

the threshold should note that when ℓ is small more vertices of G_{n,M=⌈ℓn⌉}^{k} will have degree k, and so the low graph will tend to have higher edge-density.

In the final section, we prove Fact 1.3 and complete the proof of Theorem 1.1.

Throughout this paper, all asymptotics are taken as n → ∞ and we only claim statements to hold for sufficiently large n. By A ∼ B, we mean that lim_{n→∞} A/B = 1.

2 A Gallai Threshold

In this section we will prove Theorem 1.2. As is common in the study of random graphs with restricted degree sequences, we will work with the configuration model, introduced in this form by Bollobás[5] and motivated in part by the work of Bender and Canfield[4]. This model arose in a somewhat different form in the work of Bekessy, Bekessy and Komlos[3] and Wormald[23, 24]. Given the degree sequence of a graph, we construct a random configuration with the same degree sequence by taking deg(v) copies of each vertex v, and then choosing a uniformly random pairing of the vertex-copies. Note that every configuration has an underlying multigraph with the desired degree sequence. Note further that every simple graph with that degree sequence occurs as the underlying multigraph with the same probability. As we shall see in the proof of Theorem 1.2(b), if the degree sequence has bounded maximum degree then the underlying multigraph of a random configuration is simple with probability asymptotic to e^{−μ_{1}−μ_{2}} where μ_{1}, μ_{2} are constants dependent on the degree sequence. An immediate and very useful consequence is the following:

Lemma 2.1 If a random configuration, F, on a particular degree sequence with constant maximum degree a.s. has a property P, then a random (simple) graph, G, on the same degree sequence a.s. has P. Moreover, the probability that G does not have P is at most a constant multiple of the probability that F does not have P.

We will use this lemma to allow us to work with the configuration model a number of times in this section.

Note that choosing a random configuration amounts to nothing more than selecting a uniformly random pairing of its vertices, and that we are free to choose this pairing any way we like so long as the distribution remains uniform. It is frequently useful to repeatedly take any unpaired vertex-copy we please and pair it with another randomly selected unexposed vertex-copy. In the proof of Theorem 1.9 in [21], we did this, each time being precise about the vertex-copy that we chose to pair. Essentially, we would expose the components of the underlying multigraph one at a time. If any vertices already known to be in the component had some unpaired copies, then we would choose one such copy (arbitrarily) to be the next one paired. At each step, we refer to such vertices as partially exposed, and we refer to the subgraph induced by the exposed edges of the component currently being exposed as a partial component. If there were no partially exposed vertices, then we would arbitrarily choose a vertex-copy, effectively starting a new component. We mention this here, because during the proof of Theorem 1(a) we will refer to a lemma from [21] regarding the evolution of the configuration during this exposure.

Now we begin our proof of Theorem 1.2. The first step is to show that λ_{k} is the threshold for L(G_{n,M=λn}^{k}) to a.s. have a giant component.

Lemma 2.2 For ℓ < ℓ_{k}, a.s. L(G_{n,M=⌈ℓn⌉}^{k}) has a giant component on θ(n) vertices,

while for ℓ > ℓ_{k}, a.s. all components of L(G_{n,M=⌈ℓn⌉}^{k}) have size at most O(log n).

Proof First we expose the degree sequence of G_{n,M=⌈ℓn⌉}^{k}, letting d_{i} denote the

number of vertices of degree i for each i ≥ k. Using the results of [18] one can show (see [15] or [22]) that a.s. this degree sequence has an asymptotic truncated Poisson distribution with sharp concentration. More precisely, with ν_{i} = \frac{t^{i}}{i!} e^{−t} where t is chosen so that

\frac{∑_{i≥k} iν_{i}}{∑_{i≥k} ν_{i}} = 2ℓ,

a.s. d_{i} = (ν_{i}/ ∑_{i≥kν_{i}})n + o(n), for each i ≥ k. Furthermore, for any ϵ_{1} > 0 there exists ζ_{1} < 1 such that with probability at least 1 − ζ_{1}^{n}, |d_{k} − μ_{k}n| < ϵ_{1}n.

Consider a random configuration, F, on this degree sequence. First we expose the degree sequence of L(F), the low graph of the underlying multigraph of F. Each vertexcopy is paired to a copy of a vertex of degree k with probability kd_{k}/2ℓn = α. Therefore a.s. a vertex of degree k in F has degree i in L(F) with probability approximately β_{i} = \binom{k}{i}α^{i}(1 − α)^{k−i}. In fact it is straightforward to show that for each 0 ≤ i ≤ k, the number of vertices of degree i in L(F), b_{i}, is sharply concentrated around β_{i}n in the sense that d_{i} is sharply concentrated, i.e. for any ϵ_{2} > 0 there exists ζ_{2} < 1 such that with probability at least 1 − ζ_{2}^{n}, |b_{i} − β_{i}n| < ϵ_{2}n. Therefore, if D_{n} is the degree sequence of L(F), then a.s. D_{n} is an incident of an asymptotic degree sequence D with

Q(D) = ∑_{i=1}^{k} i(i − 2)\binom{k}{i}α^{i}(1 − α)^{k−i}
= kα((k − 1)α − 1)

Solving α = 1/(k − 1) for ℓ yields ℓ = ℓ_{k}, showing that for ℓ < ℓ_{k} (ℓ > ℓ_{k}), there exist ϵ = ϵ(ℓ) > 0, ζ_{3} = ζ_{3}(ℓ) < 1 such that Q(D) > ϵ (Q(D) < −ϵ) with probability at least 1 − ζ_{3}^{n}, and apply Theorem 1.9.

And now we prove that the threshold for L(G_{n,M=⌈ℓn⌉}^{k}) to a.s. have a giant compo-

nent is the threshold for G_{n,M=⌈ℓn⌉}^{k} to a.s. not be Gallai, as described in the statement of Theorem 1.2.

Proof of Theorem 1.2(a): First we consider the case ℓ < ℓ_{k}. We will first expose the degree sequence D = D_{n} of L(G_{n,M=⌈ℓn⌉}^{k}). As shown in the preceding proof, there is some ϵ > 0, ζ_{3} < 1 such that D_{n} is an incident of an asymptotic degree sequence D, where Q(D) > ϵ, with probability at least 1 − ζ_{3}^{n}. Let E_{1} be the event that this happens. Note that, conditioning on E_{1}, L(G_{n,M=⌈ℓn⌉}^{k}) a.s. has a giant component and so, intuitively, it is not surprising that it is a.s. not k-Gallai.

Given the degree sequence of L(G_{n,M=⌈ℓn⌉}^{k}), we expose a random configuration, F, on

that degree sequence, in the manner used in [21] as described above. It is straightforward to check that every simple graph with degree sequence D is equally likely to occur as L(G_{n,M=⌈ℓn⌉}^{k}), and so we are justified in using the configuration model here. After i pairs have been exposed, we let X_{i} denote the number of unexposed copies of partially exposed vertices. If E_{1} holds, then by Lemma 9 of [21] there exists I, γ > 0, ζ_{4} < 1 such that with probability at least 1 − ζ_{4}^{n}, X_{I} ≥ γn. Let E_{2} be the event that this happens.

If E_{2} holds, consider any spanning tree T of the partial component currently being exposed. Because the maximum degree in T is at most k, it is easy to show that T has a vertex v such that, considering T to be rooted at v, v has a child v_{1} such that the subtree rooted at v_{1} has at least \frac{γn}{2k} but not more than \frac{2γn}{k} open vertex-copies. Furthermore, we can repeatedly choose a child v_{i+1} of v_{i} such that the subtree rooted at v_{i+1} has at least \frac{γn}{2k^{i}} open vertex-copies. Setting u = v_{k+1}, and letting P be the unique uv-path in T, we have that P has length k + 1, and upon deleting the edges of P from T, the components containing u and v, T_{u}, T_{v}, each have at least (γ/2k^{k+1})n open vertex-copies. Similarly, T_{u} contains a path P_{u} of length k + 1 such that the components of T_{u} − P_{u} containing the endpoints of P_{u}, T_{u}^{1}, T_{u}^{2} each have at least (γ/4k^{2k+2})n open vertex-copies.

Therefore, there exists ζ_{5} < 1 such that at least one pair of the configuration will contain a point from each of T_{u}^{1}, T_{v}, and at least one pair will contain a point from each of T_{u}^{2}, T_{v}, with probability at least 1 − ζ_{5}^{n}. The two cycles induced in T by these edges intersect in P, and so their union must contain an even cycle of length at least k + 2. Since F has maximum degree k, it contains no (k + 2)−clique, and so it cannot be k-Gallai.

Therefore, applying Lemma 2.1 the probability that L(G_{n,M=⌈ℓn⌉}^{k}) is k-Gallai is at most

Pr{L(G_{n,M=⌈ℓn⌉}^{k}) is k-Gallai | E_{1} ∧ E_{2}} + Pr{Ē_{2} | E_{1}} + Pr{Ē_{1}} < ζ^{n},

for some ζ > 0.

To prove Theorem 1.2(b), we will essentially show that the number of even cycles in L(G_{n,M=⌈ℓn⌉}^{k}) is asymptotically equivalent to a Poisson variable with mean μ. The

result then follows by setting p_{k}(ℓ) = e^{−μ}.

Proof of Theorem 1.2(b): First we expose the degree sequence of L(G_{n,M=⌈ℓn⌉}^{k}),

and then we choose L(G_{n,M=⌈ℓn⌉}^{k}) by taking a random graph on that degree sequence. Again, we work with the configuration model, taking a random configuration F on the same degree sequence.

As in Lemma 2.2, a.s. the number of vertices of degree i is λ_{i}n + o(n) for some λ_{0}, …, λ_{k} > 0 such that ∑_{i=1}^{k} i(i − 2)λ_{i} < ϵ = ϵ(ℓ), and we let E_{3} be the event that this holds.

For constant r ≥ 1, let C_{r} denote the number of cycles of length r in F. We will show that C_{1}, C_{2}, … are asymptotic to independent Poisson variables with means μ_{1}, μ_{2}, . . ..

The first step is to compute μ_{r}. Define K = ∑_{i≥1} iλ_{i}.

μ_{r} ≈ \frac{r!}{(Kn)^{r}} ∑_{a_{2}+...+a_{k}=r} ∏_{i=2}^{k} \binom{λ_{i}n}{a_{i}}(i(i − 1))^{a_{i}}

≈ \frac{r!}{K^{r}} ∑_{a_{2}+...+a_{k}=r} ∏_{i=2}^{k} \frac{(i(i − 1)λ_{i})^{a_{i}}}{a_{i}!}

= \frac{r!}{K^{r}} [x^{r}] ∏_{i=2}^{k} e^{i(i−1)λ_{i}}
= (\frac{∑_{i=2}^{k} i(i − 1)λ_{i}}{K} )^{r} .

Note that if E_{3} holds, then μ_{r} tends to zero as r grows, since ∑_{i≥1} i(i − 2)λ_{i} < 0 implies that ρ = ∑_{i=2}^{k} i(i − 1)λ_{i} < K. Note further that for any r = r(n), the expected number of cycles of length r in F is at most ρ^{r}.

The next step is to compute the second moment of C_{r}. To do this we will compute Δ_{r_{1},r_{2}}, the sum over all pairs of intersecting cycles in K_{n} of length r_{1}, r_{2} of the probability that they both appear in L(G_{n,M=⌈ℓn⌉}^{k}).

To compute Δ, we sum first over all cycles, H_{1}, of length r_{1}, and then over all intersecting cycles H_{2} of length r_{2}. Noting that H_{2} − E(H_{1}) is a collection of a paths for some a ≥ 1, we sum over the number of choices for these paths, setting l_{1}, …, l_{a} to be their lengths.

Δ_{r_{1},r_{2}} ≤ ∑_{a_{2}+...+a_{k}=r_{2}} ∏_{i=2}^{k} \binom{λ_{i}n}{a_{i}}(i(i − 1))^{a_{i}}

× ∑_{a=1}^{r_{2}} ∑_{{l_{1},...,la≥1 \atop l_{1}+...+l_{k}<r_{2}}} ∏_{j=1}^{a} ∑_{b_{2}+b_{3}+...=l_{j} −1} \binom{r_{1}}{2}k^{2}(k − 1)^{2} \frac{(l_{j} − 1)!}{(Kn)^{l_{j}}}

× ∏_{i=2}^{k} \binom{λ_{i}n}{b_{i}}(i(i − 1))^{b_{i}}

≤ ρ^{r} ∑_{a=1}^{r_{2}} \binom{r_{1}}{2}k^{2}(k − 1)^{2}n^{−1} ( ∑_{l=1}^{r_{2}−1} ρ^{l})^{a}
= O(n^{−1})

Therefore, Exp(C_{r}^{2}) is asymptotic to the expected number of pairs of non-intersecting cycles of length r in F which is easily calculated to be \frac{μ_{r}^{2}}{2} + o(1). Similarly, for r_{1} ≠ r_{2}, Exp(C_{r_{1}}C_{r_{2}}) ≈ μ_{r_{1}}μ_{r_{2}}.

Similar calculations show that the expected number of t-tuples of non-edge-disjoint cycles of lengths r_{1}, …, r_{t} is o(1) for any t ≥ 2, and so for any x_{1}, …, x_{s}, Exp(C_{r_{1}}^{x_{1}}, …, C_{r_{s}}^{x_{s}}) ≈ ∏_{i=1}^{s} \frac{μ_{r_{i}}^{x_{i}}}{x_{i}!} , and so C_{0}, C_{1}, … are asymptotically independent Poisson variables as claimed.

Note that for any δ > 0, there exists R = R(δ) such that the expected number of cycles of length at least R is less than δ and so, by Markov’s Inequality, the probability that F contains a cycle of length at least R is less than δ. Therefore, the probability that F contains no even cycle of length at least 4 is asymptotic to

p_{k}(ℓ) = e^{− ∑_{r≥2} ρ^{2r}}.

Furthermore, this event is asymptotically independent of the event that F contains no cycles of length 1 or 2, and so the probability that a random graph on the same degree sequence has no even cycle is asymptotic to p_{k}(ℓ).

Define E_{4} to be the event that G_{n,M=⌈ℓn⌉}^{k} has no 4-clique. It is straightforward to

compute that Pr(E_{4}) > 1 − n^{−1}. Therefore, again applying Lemma 2.1,

|Pr{G_{n,M=⌈ℓn⌉}^{k} is k-Gallai} − p_{k}(ℓ)| ≤ Pr(Ē_{3}) + Pr(Ē_{4})
= o(1).

3 The first k-core to appear

Here, we see that a.s. the first k-core to appear has edge density precisely ℓ_{k}.

Proof of Fact 1.3: It is implicit in [22] that a.s. the edge-density of the first k-core to appear is:

\frac{∑i≥k \frac{iτ_{k}^{i}}{i!}}{2 ∑_{i≥k} \frac{τ_{k}^{i}}{i!}} + o(1),

where τ_{k} minimizes

\frac{τ}{1 − e^{−τ} ∑_{i=0}^{k−2} \frac{τ^{i}}{i!}} .

Thus, it is our goal to show that τ_{k} = t_{k}. To solve for τ_{k}, we set f(τ) = (1 − e^{−τ} ∑_{i=0}^{k−2} \frac{τ^{i}}{i!} )/τ, yielding

f′(τ) = −\frac{1}{τ^{2}} − (−e^{−τ} (∑_{i=0}^{k−2} \frac{τ^{i−1}}{i!} ) + e^{−τ} (−\frac{1}{τ^{2}} + ∑_{i=0}^{k−4} \frac{τ^{i}}{(i + 2)i!}))

= −\frac{e^{−τ}}{τ^{2}} (e^{τ} − (1 + τ + ∑_{i=2}^{k−2} τ^{i} (\frac{1}{(i − 1)!} − \frac{1}{i(i − 2)!}) + \frac{τ^{k−1}}{(k − 2)!}))

= −\frac{e^{−τ}}{τ^{2}} (e^{τ} − ∑_{i=0}^{k−2} \frac{τ^{i}}{i!} − \frac{τ^{k−1}}{(k − 2)!}) ,

and so τ_{k} = t_{k}.

And this yields our main theorem:

Proof of Theorem 1.1: Consider any ϵ > 0 and set M = (c_{k} + ϵ)n. By the main result of [22], G_{n,M} a.s. has a k-core, and by Fact 1.3, the edge-density of the k-core is at least t_{k} + δ for some δ > 0. Let T denote this k-core.

Once we have exposed n′, the number of vertices, and M′, the number of edges in T, it is a uniformly random member of Ω_{n′,M′}^{k} as each member of Ω_{n′,M′}^{k} is the k-core of the same number of graphs with n vertices and M edges. Therefore Theorem 1.2(b) can be applied to T.

Define T_{1} ⊂ T to be the subgraph of T induced by the components of L(T) which contain even cycles. Recall that in the proof of Theorem 1.2(b) we show that the number of even cycles in a random configuration with the same degree sequence as L(T) has an asymptotically Poisson distribution. In the same manner, it is straightforward to show that (a) a.s. |T_{1}| < |T |, (b) a.s. no vertex v ∈ T of degree at least k + 1 has more than 1 neighbour in T_{1}, and finally (c) a.s. the subgraph induced by (T ∪ N(T_{1}))\T_{1} contains no even cycles. This follows from a straightforward first-moment analysis; we omit the details. Intutition towards the truth of this statement comes from the fact that the expected size of T_{1} is O(1).

Therefore, a.s. T \T_{1} is k-Gallai.

Acknowledgements

We would like to thank the anonymous referee for many helpful comments.

References

[1] D. Achlioptas and E. Friedgut, A sharp threshold for k-colorability. Manuscript.

[2] D. Achlioptas and M. Molloy. Analysis of a greedy list-colouring algorithm on random graphs. Proceedings of STOC 1998, 524 - 529.

[3] A. Bekessy, P. Bekessy and J. Komlos. Asymptotic Enumeration of Regular Matrices, Stud. Sci. Math. Hungar. 7 (1972) 343 - 353.

[4] E. A. Bender and E. R. Canfield. The asymptotic number of labelled graphs with given degree sequences. Journal of Combinatorial Theory (A) 24 (1978), 296-307.

[5] B. Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled random graphs. Eur. J. Comb. 1 (1980), 311 - 316.

[6] B. Bollobás. The evolution of sparse random graphs. Graph Theory and Combinatorics. Proc. Cambridge Combinatorial Conf. in honour of Paul Erdős (B. Bollobás, ed.) Academic Press (1984), 35 - 57.

[7] B. Bollobás and A. Thomason. Random graphs of small order. Random Graphs ’83. Annals of Discrete Math 28 (1985), 47 - 97.

[8] B. Bollobás and A. Frieze. On matchings and Hamiltonian cycles in random graphs. Annals of Discrete Mathematics 28, 23 - 46.

[9] A. Bondy and U.S.R. Murty. Graph Theory With Applications. MacMillan Press (1976).

[10] V. Chvátal. Almost all graphs with 1.44n edges are 3-colourable. Random Structures and Algorithms 2 (1991), 11 - 28.

[11] P. Erdős in Open problems. Random Structures and Algorithms 2,3 (1995), 367 - 369.

[12] P. Erdős and A. Rényi. On the evolution of random graphs. Magayr Tud. Akad. Mat. Kutato Int. Kozl. 5 (1960), 17 - 61.

[13] P. Erdős and A. Rényi. On the existence of a factor of degree one of a connected random graph. Acta Math. Acad. Sci. Hungar. 17 (1966), 359 - 368.

[14] E. Freidgut. Sharp thresholds for graph properties and the k-sat problem. Manuscript.

[15] A. Frieze. Analysis of randomized algorithms. Computing 7 (1990), 209 - 233.

[16] T. Gallai. Kritische Graphen I. Magayr Tud. Akad. Mat. Kutato Int. Kozl. 8 (1963), 165 - 192.

[17] J. Komlós and E. Szemerédi. Limit distributions for the existence of a Hamilton cycle in a random graph. Discrete Math 43 (1983), 55 - 63.

[18] B.D. McKay and N.C. Wormald, Asymptotic enumeration by degree sequence of graphs with degrees o(n^{1/2}). Combinatorica 11 (1991), 369 - 382.

[19] M. Molloy. The Chromatic Number of Sparse Random Graphs. Masters Thesis, University of Waterloo, (1992).

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

[21] M. Molloy and B. Reed. A critical point for random graphs with a given degree sequence. Random Structures and Algorithms 2,3 (1995), 161 - 180.

[22] B. Pittel, J. Spencer and N. C. Wormald. Sudden emergence of a giant k-core in a random graph. J. Comb. Th. B 67 (1996), 111 - 151.

[23] N. C. Wormald. The Asymptotic Connectivity of Labelled Regular Graphs. Journal of Combinatorial Theory (B) 31 (1981), 156 - 167.

[24] N. C. Wormald. The Asymptotic Distribution of Short Cycles in Random Regular Graphs. Journal of Combinatorial Theory (B) 31 (1981), 168 - 182.