Multicoloured Hamilton cycles in random graphs; an anti-Ramsey threshold.

Colin Cooper

School of Mathematical Sciences,

University of North London, London N7 8DB, U.K. ^{∗}

Alan Frieze Department of Mathematics, Carnegie Mellon University, Pittsburgh PA15213, U.S.A.^{†}

Submitted: August 25, 1995; Accepted October 1, 1995

Abstract

Let the edges of a graph G be coloured so that no colour is used more than k times. We refer to this as a k-bounded colouring. We say that a subset of the edges of G is multicoloured if each edge is of a different colour. We say that the colouring is H-good, if a multicoloured Hamilton cycle exists i.e., one with a multicoloured edge-set. Let AR_{k} = {G : every k-bounded colouring of G is H-good}. We establish the threshold for the random graph G_{n,m} to be in AR_{k}.

∗Research carried out whilst visiting Carnegie Mellon University †Supported by NSF grant CCR-9225008

1 Introduction

As usual, let G_{n,m} be the random graph with vertex set V = [n] and m random edges. Let m = n(log n + log log n + c_{n})/2. Komlós and Szemerédi [14] proved that if λ = e^{−c} then

lim_{n→∞} Pr(G_{n,m}is Hamiltonian) = \{ \begin{matrix}0 & c_{n} → −∞ \\ e^{−λ} & c_{n} → c \\ 1 & c_{n} → ∞ \end{matrix} ,

which is lim_{n→∞} Pr(δ(G_{n,m}) ≥ 2), where δ refers to minimum degree.

This result has been generalised in a number of directions. Bollobás [3] proved a hitting time version (see also Ajtai, Komlós and Szemerédi [1]); Bollobás, Fenner and Frieze [6] proved an algorithmic version; Bollobás and Frieze [5] found the threshold for k/2 edge disjoint Hamilton cycles; Bollobás, Fenner and Frieze [7] found a threshold when there is a minimum degree condition; Cooper and Frieze [9], Łuczak [15] and Cooper [8] discussed pancyclic versions; Cooper and Frieze [10] estimated the number of distinct Hamilton cycles at the threshold.

In quite unrelated work various researchers have considered the following problem: Let the edges of a graph G be coloured so that no colour is used more than k times. We refer to this as a k-bounded colouring. We say that a subset of the edges of G is multicoloured if each edge is of a different colour. We say that the colouring is H-good, if a multicoloured Hamilton cycle exists i.e., one with a multicoloured edge-set. A sequence of papers considered the case where G = K_{n} and asked for the maximum growth rate of k so that every k-bounded colouring is H-good. Hahn and Thomassen [13] showed that k could grow as fast as n^{1/3} and conjectured that the growth rate of k could in fact be linear. In unpublished work Rödl and Winkler [18] in 1984 improved this to n^{1/2}. Frieze and Reed [12] showed that there is an absolute constant A such that if n is sufficiently large and k is at most ⌈n/(A ln n)⌉ then any k-bounded colouring is H-good. Finally, Albert, Frieze and Reed [2] show that k can grow as fast as cn, c < 1/32.

The aim of this paper is to address a problem related to both areas of activity. Let AR_{k} = {G : every k-bounded colouring of G is H-good}. We establish the threshold for the random graph G_{n,m} to be in AR_{k}.

Theorem 1 If m = n(log n + (2k − 1) log log n + c_{n})/2 and λ = e^{−c}, then

lim_{n→∞} Pr (G_{n,m} ∈ AR_{k}) = \{ \begin{matrix}0 & c_{n} → −∞ \\ ∑{k−1 \atop i=0} \frac{e^{−λ}λ^{i}}{i!} & c_{n} → c \\ 1 & c_{n} → ∞ \end{matrix}  (1)
= lim_{n→∞} Pr(G_{n,m} ∈ B_{k}),

where B_{k} = {G : G has at most k − 1 vertices of degree less than 2k}.

Note that the case k = 1 generalises the original theorem of Komlòs and Szemerèdi. We use AR_{k} to denote the anti-Ramsey nature of the result and remark that there is now a growing literature on the subject of the Ramsey properties of random graphs, see for example the paper of Rödl and Ruciński [17].

2 Outline of the proof of Theorem 1

We will prove the result for the independent model G_{n,p} where p = 2m/n and rely on the monotonicity of property AR_{k} to give the theorem as stated, see Bollobás [4] and Łuczak [16]. With a little more work, one could obtain the result that the hitting times for properties AR_{k} and B_{k} in the graph process are coincidental whp^{1}.

We will follow the basic idea of [12] that, given a k-bounded colouring we will choose a multicoloured set of edges E_{1} ∪ E_{2} and show that whp H = (V = [n], E_{1} ∪ E_{2}) contains a Hamilton cycle. E_{1} is chosen randomly, pruned of multiple colours and colours that occur on edges incident with vertices of low degree. E_{2} is chosen carefully so as to ensure that vertices of low degree get at least 2 incident edges and vertices of large degree get a substantial number of incident edges. H is multicoloured by construction. We then use the approach of Ajtai, Komlós and Szemerédi [1] to show that H is Hamiltonian whp.

1with high probability i.e. probability 1-o(1) as n → ∞

3 Required graph properties

We say a vertex v of G = G_{n,p} is small if its degree d(v) satisfies d(v) < log n/10 and large otherwise. Denote the set of small vertices by SMALL and the remaining vertices by LARGE. For S ⊆ V we let

N_{G}(S) = N(S) = {w ∉ S : ∃v ∈ S such that {v, w} is an edge of G}.

We now give a rather long list of properties. We claim

Lemma 1 If p = (log n + (2k − 1) log log n + c)/n then G_{n,p} has properties P1 – P9 below whp and property P10 with probability equal to the RHS of (1).

P1 |SMALL| ≤ n^{1/3}.

P2 SMALL contains no edges.

P3 No v ∈ V is within distance 2 of more than one small vertex.

P4 S ⊆ LARGE, |S| ≤ n/ log n implies that |N(S)| ≥ |S| log n/20.

P5 T ⊆ V, |T | ≤ n/(log n)^{2} implies T contains at most 3|T | edges.

P6 A, B ⊆ V, A ∩ B = ∅, |A|, |B| ≥ 15n log log n/ log n implies G contains at least |A||B| log n/2n edges joining A and B.

P7 A, B ⊆ V, A∩B = ∅, |A| ≤ |B| ≤ 2|A| and |B| ≤ Dn log log n/ log n (D ≥ 1) implies that there are at most 10D|A| log log n edges joining A and B.

P8 If |A| ≤ Dn log log n/ log n (D ≥ 1) then A contains at most 10D|A| log log n edges.

P9 G has minimum degree at least 2k − 1.

P10 G has at most k − 1 vertices of degree 2k − 1.

The proof that G_{n,p} has properties P1–P4 whp can be carried out as in [6]. Erdős and Rényi [11] contains our claim about P9, P10. The remaining claims are simple first moment calculations and are placed in the appendix.

4 A simple necessary condition

We now show the relevance of P9, P10. Suppose a graph G has k vertices v_{1}, v_{2}, …, v_{k} of degree 2k − 1 or less and these vertices form an independent set. (The latter condition is not really necessary.) We can use colour 2i − 1 at most k times and colour 2i at most k − 1 times to colour the edges incident with v_{i}, 1 ≤ i ≤ k − 1. Now use colours 2, 4, 6, …, 2k − 2 at most once and colour 2k − 1 at most k times to colour the edges inicident with v_{k}. No matter how we colour the other edges of G there is no multicoloured Hamilton cycle. Any such cycle would have to use colours 1, 2, …, 2k − 2 for its edges incident with v_{1}, v_{2}, …, v_{k−1} and then there is only one colour left for the edges incident with vertex v_{k}.

Let N_{k} denote the set of graphs satisfying P1–P10. It follows from Lemma 1 and the above that we can complete the proof of Theorem 1 by proving

N_{k} ⊆ AR_{k}.  (2)

5 Binomial tails

We make use of the following estimates of tails of the Binomial distribution several times in subsequent proofs.

Let X be a random variable having a Binomial distribution Bin(n, p) resulting from n independent trials with probability p. If μ = np then

Pr(X ≤ αμ) ≤ (\frac{e}{α})^{αμ} e^{−μ} 0 < α ≤ 1  (3)
Pr(X ≥ αμ) ≤ (\frac{e}{α})^{αμ} e^{−μ} 1 ≤ α.  (4)

6 Main Proof

Assume from now on that we have a fixed graph G = (V, E) ∈ N_{k}. We randomly select a multicoloured subgraph H of G, H = (V, E_{1} ∪ E_{2}) and prove that it is Hamiltonian whp. From now on all probabilistic statements are with respect to the selection of the random set E_{1} ∪ E_{2} and not the choice of G = G_{n,p}.

6.1 Construction of the multicoloured subgraph H

The sets E_{1} and E_{2} are obtained as follows.

6.1.1 Selection of E_{1}

(i) Choose edges of the subgraph of G induced by LARGE independently with probability ϵ/k, ϵ = e^{−200k}, to obtain Ẽ_{1}.

(ii) Remove from Ẽ_{1} all edges whose colour occurs more than once in Ẽ_{1} and also edges whose colour is the same as that of any edge incident with a small vertex.

Denote the edge set chosen by E_{1}, and denote by E_{1}^{⋆} the subset of edges of E which have the same colour as that of an edge in E_{1}.

Lemma 2 For v ∈ LARGE let d′(v) denote the degree of v in (V, E\E_{1}^{⋆}). Then whp

d′(v) > \frac{9}{100k} log n,

for all v ∈ LARGE.

Proof Suppose that large vertex v has edges of r = r(v) different colours c_{1}, c_{2}, …, c_{r} incident with it in G, where d(v)/k ≤ r ≤ d(v). Let X_{i}, 1 ≤ i ≤ r be an indicator for the event that E_{1} contains an edge of colour c_{i} which is incident with v. Let k_{i} denote the number of times colour c_{i} is used in G and let ℓ_{i} denote the number of edges of colour c_{i} which are incident with v. Then

Pr(X_{i} = 1) ≤ ℓ_{i} \frac{ϵ}{k} (1 − \frac{ϵ}{k} )^{k_{i}−1}
≤ ϵ.

The random variables X_{1}, X_{2}, …, X_{r} are independent and so X = X_{1} + X_{2} + ⋯ + X_{r} is dominated by Bin(r, ϵ). Thus, by (4),

Pr (X ≥ \frac{r}{10}) ≤ (10eϵ)^{\frac{r}{10}}
≤ (10eϵ)^{\frac{log n}{100k}}
≤ n^{−3/2},

when ϵ = e^{−200k}. Hence whp,

d′(v) > \frac{9}{10}r ≥ \frac{9}{100k} log n

for every v ∈ LARGE. □

Assume then that

d′(v) > \frac{9}{100k} log n

for v ∈ LARGE.

6.1.2 Selection of E_{2}

We show we can choose a monochromatic subset E_{2} of E \ E_{1}^{∗} in which

D1 The vertices of SMALL have degree at least 2,

D2 The vertices of LARGE have degree at least ⌊\frac{9}{200k^{2}} log n⌋.

In order to select E_{2}, we first describe how to choose for each vertex v ∈ V, a subset A_{v} of the edges of E\E_{1}^{⋆} incident with v. These sets A_{v}, v ∈ V are pairwise disjoint.

The vertices v of SMALL are independent (P2) and we take A_{v} to be the set of edges incident with v if d(v) = 2k − 1, and A_{v} to be an mk subset otherwise, where m = ⌊d(v)/k⌋.

The subgraph F of E\E_{1}^{⋆} induced by LARGE, is of minimum degree greater than (9 log n)/100k. We orient F so that |d^{−}(v) − d^{+}(v)| ≤ 1 for all v ∈ LARGE. We now choose a subset A_{v} of edges directed outward from v by this orientation, of size ⌊(9 log n)/200k^{2}⌋ k.

The following lemma, applied to the sets A_{v} defined above, gives the required monochromatic set E_{2}.

Lemma 3 Let A_{1}, A_{2}, …, A_{n} be disjoint sets with |A_{i}| = 2k − 1, 1 ≤ i ≤ r ≤ k − 1 and |A_{i}| = m_{i}k, r + 1 ≤ i ≤ n, where the m_{i}’s are positive integers. Let A = A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{n}. Suppose that the elements of A are coloured so that no colour is used more than k times. Then there exists a multicoloured subset B of A such that |A_{i} ∩ B| = 2, 1 ≤ i ≤ r and |A_{i} ∩ B| = m_{i}, r + 1 ≤ i ≤ n.

Proof For i = 1, ..., r partition A_{i} into B_{i,1}, B_{i,2} where |B_{i,1}| = k − 1 and |B_{i,2}| = k, and let m_{i} = 2. For i = r + 1, ..., n partition A_{i} into subsets B_{i,j} (j = 1, ..., m_{i}) of size k.

Let X = {B_{i,j} : i = 1, ..., n, j = 1, ..., m_{i}} and let Y be the set of colours used in the k-bounded colouring of A. We consider a bipartite graph Γ with bipartition (X, Y), where (x, y) is an edge of Γ if colour y ∈ Y was used on the elements of x ∈ X.

We claim that Γ contains an X-saturated matching. Let S ⊆ X, |S| = s, and suppose t elements of S are sets of size k − 1 and s − t are of size k. We have

| ⋃_{B_{i,j}∈S} B_{i,j}| = (s − t)k + t(k − 1)
= sk − t.

Thus the set of neighbours N_{Γ}(S) of S in Γ satisfies

|N_{Γ}(S)| ≥ ⌈s − \frac{t}{k}⌉ ≥ ⌈s − (\frac{k−1}{k})⌉ = |S|,

and Γ satisfies Hall’s condition for the existence of an X-saturated matching M = {(B_{i,j}, y_{i,j})}. Now construct B by taking an element of colour y_{i,j} in B_{i,j} for each (i, j).

□

6.2 Properties of H = (V, E_{1} ∪ E_{2})

We first state or prove some basic properties of H.

Lemma 4 H is multicoloured, and δ(H) ≥ 2.

Lemma 5 With high probability

D3 S ⊆ LARGE, |S| ≤ \frac{n}{100 log n} ⟹ |N_{H}(S)| ≥ \frac{ϵ log n}{300k^{2}}|S|.

Proof

Case of |S| ≤ n/(log n)^{3}

If S ⊆ LARGE, then T = N_{H}(S) ∪ S contains at least ⌊\frac{9}{200k^{2}} log n⌋|S|/2 edges in E_{2}. No subset T of size at most n/(log n)^{2} contains more than 3|T | edges (by P5). Thus |T | ≥ ⌊\frac{9}{200k^{2}} log n⌋|S|/6 and so

|N_{H}(S)| ≥ \frac{3}{500k^{2}} log n|S|.

Case of n/(log n)^{3} < |S| ≤ n/100 log n

By P4, G satisfies |N(S)| ≥ (|S| log n)/20 and we can choose a set M of

⌊(|S| log n)/20 − (k|SMALL| log n)/10⌋

edges which have one endpoint in S, the other a distinct endpoint not in S and of a colour different to that of any edge incident with a vertex of SMALL. This set of edges contains at least |M|/k colours. If M contains t edges of colour i and G contains r edges of colour i in total, then the probability ρ that an edge of M of colour i is included in E_{1} satisfies

ρ ≥ \frac{tϵ}{k} (1 − \frac{ϵ}{k} )^{r−1} ≥ \frac{tϵ}{k}(1 − ϵ) > \frac{ϵ}{2k} .  (5)

Thus |N_{H}(S)| dominates Bin(\frac{|M|}{k}, \frac{ϵ}{2k}), and by (3)

Pr (|N_{H}(S)| ≤ \frac{|M|ϵ}{4k^{2}}) ≤ (\frac{2}{e})^{|M|ϵ/4k^{2}} .

Hence the probability that some set has less than the required number of neighbours to its neighbour set is

∑_{s=n/(log n)^{3}}^{n/(100 log n)} \binom{n}{s} (\frac{2}{e})^{(ϵs log n)/100k^{2}} ≤ ∑_{s} [exp − \{\frac{ϵ log(e/2)}{100k^{2}} log n − 4 log log n\}]^{s}
= o(1).

□

Lemma 6 Let D ≥ \frac{32k^{2}}{ϵ}; if |A|, |B| ≥ Dn\frac{log log n}{log n} then whp

D4 H contains more than ⌊\frac{2}{D}|A| |B|\frac{log n}{n}⌋ edges between A and B.

Proof The proof follows that of Lemma 5. By P6, the number of edges between A and B in G of a colour different to that of any edge incident with a vertex of SMALL is at least M = ⌊(|A||B| log n/2n) − (k|SMALL| log n)/10⌋. Thus the number of E_{1}-edges between these sets dominates Bin(M/k, ϵ/2k). Let K = (1 − o(1))\frac{8(1−(log 4e)/4)}{D} \frac{log n}{n}. The probability that there exist sets A, B with at most ⌊\frac{2}{D}|A| |B|\frac{log n}{n}⌋ E_{1}-edges between them is (by (3)) at most

∑_{a,b} \binom{n}{a}\binom{n}{b} (\frac{(4e)^{\frac{1}{4}}}{e} )^{(1−o(1)) \frac{Mϵ}{2k^{2}}} ≤ ∑_{a,b} (\frac{ne}{a})^{a} (\frac{ne}{b})^{b} e^{−Kab}  (6)
≤ ∑_{a,b} exp{(a + b) log log n − Kab}
≤ ∑_{a,b} exp \{ab ((\frac{1}{a} + \frac{1}{b}) log log n − K)\}
≤ ∑_{a,b} exp \{ab (\frac{2 log n}{Dn} − \frac{3 log n}{Dn})\}
≤ n^{2} exp \{−Dn\frac{(log log n)^{2}}{log n} \}
= o(1).
□

Assume from now on that H satisfies D1–D4. We note the following immediate Corollary.

Corollary 1 whp H is connected.

Proof If H is not connected then from D4 its has a component C of size at most Dn\frac{log log n}{log n}. But then D3 and P3 imply C ∩ LARGE = ∅. Now apply D1 and P2 to get a contradiction. □

7 Proof that H is Hamiltonian

Let us suppose we have selected a G satisfying properties P1–P10, and sampled a suitable H which satisfies D1–D4. We now show that it must follow that H contains a multicoloured Hamilton cycle.

7.1 Construction of an initial long path

We use rotations and extensions in H to find a maximal path with large rotation endpoint sets, see for example [6], [14]. Let P_{0} = (v_{1}, v_{2}, …, v_{l}) be a path of maximum length in H. If 1 ≤ i < l and {v_{l}, v_{i}} is an edge of H then P′ = (v_{1}v_{2} … v_{i}v_{l}v_{l−1} … v_{i+1}) is also of maximum length. It is called a rotation of P_{0} with fixed endpoint v_{1} and pivot v_{i}. Edge (v_{i}, v_{i+1}) is called the broken edge of the rotation. We can then, in general, rotate P′ to get more maximum length paths.

Let S_{t} = {v ∈ LARGE : v ≠ v_{1}, is the endpoint of a path obtainable from P_{0} by t rotations with fixed endpoint v_{1} and all broken edges in P_{0}}.

It follows from P3 and D3 that S_{1} ≠ ∅. It then follows that if |S_{t}| ≤ n/(100 log n) then |S_{t+1}| ≥ ϵ log n|S_{t}|/(1000k^{2}), for making this inductive assumption which is true for |S_{1}| by D2,

|S_{t+1}| ≥ |N_{H}(S_{t})|/2 − (1 + |S_{1}| + |S_{2}| + ⋯ |S_{t}|)
≥ ϵ log n|S_{t}|/(600k^{2}) − (1 + |S_{1}| + |S_{2}| + ⋯ |S_{t}|)
≥ ϵ log n|S_{t}|/(1000k^{2}).

Thus there exists t_{0} ≤ (1 + o(1)) log n/ log log n such that |S_{t_{0}}| ≥ cn, c = ϵ/(10^{6}k^{2}). Let B(v_{1}) = S_{t_{0}} and A_{0} = B(v_{1}) ∪ {v_{1}}. Similarly, for each v ∈ B(v_{1}) we can construct a set of endpoints B(v), |B(v)| ≥ cn of endpoints of maximum length paths with endpoint v. Note that l ≥ cn as every vertex of B_{0} lies on P_{0}.

In summary, for each a ∈ A_{0}, b ∈ B(a) there is a maximum length path P (a, b) joining a and b and this path is obtainable from P_{0} by at most (2 + o(1)) log n/ log log n rotations.

7.2 Closure of the maximal path

This section follows closely both the notation and the proof methodology used in [1].

Given path P_{0} and a set of vertices S of P_{0}, we say s ∈ S is an interior point of S if both neighbours of s on P_{0} are also in S. The set of all interior points of S will be denoted by int(S).

Lemma 7 Given a set S of vertices with |int(S)| ≥ 7Dn\frac{log log n}{log n}, D ≥ 32k^{2}/ϵ there is a subset S′ ⊆ S such that, for all s′ ∈ S′ there are at least m = \frac{1}{D} \frac{log n}{n}|int(S)| edges between s′ and int(S′). Moreover, |int(S′)| ≥ |int(S)|/2.

Proof We use the proof given in [1]. If there is a s_{1} ∈ S such that the number of edges from s_{1} to int(S) is less than m we delete s_{1}, and define S_{1} = S\{s_{1}}. If possible we repeat this procedure for S_{1}, to define S_{2} = S_{1}\\{s_{2}\} (etc). If this continued for r = ⌊\frac{1}{6}|int(S)|⌋ steps, we would have a set S_{r} and a set R = {s_{1}, s_{2}, …, s_{r}}, with

|int(S_{r})| ≥ |int(S)| − 3|R| ≥ |int(S)| − 3r ≥ \frac{|int(S)|}{2}.

This step follows because deleting a vertex of S removes at most 3 vertices of int(S). However, there are fewer than

m|S| ≤ \frac{1}{D} \frac{log n}{n}|int(S)| |R|
≤ \frac{2}{D} \frac{log n}{n}|int(S_{r})| |R|,

edges from R to int(S_{r}), which contradicts our assumption D4. □

In Section 7.1 we proved the existence of maximum length paths P (a, b), b ∈ B(a), a ∈ A_{0} where |A_{0}|, |B(a)| ≥ cn. Thus there are at least c^{2}n^{2} distinct endpoint pairs (a, b) and for each such pair there is a path P (a, b) derived from at most ρ = (2 + o(1)) log n/ log log n rotations starting with some fixed maximal path P_{0}.

We consider P_{0} to be directed and divided into 2ρ segments I_{1}, I_{2}, …, I_{2ρ} of length at least ⌊|P_{0}|/2ρ⌋, where |P_{0}| ≥ cn. As each P (a, b) is obtained from P_{0} by at most ρ rotations, the number of segments of P_{0} which occur on this path, although perhaps reversed, is at least ρ. We say that such a segment is unbroken. These segments have an absolute orientation given by P_{0}, and another, relative to this by P (a, b), which we regard as directed from a to b. Let t be a fixed natural number. We consider sequences σ = I_{i_{1}}, ..., I_{i_{t}} of unbroken segments of P_{0}, which occur in this order on P (a, b), where we consider that σ also specifies the relative orientation of each segment. We call such a sequence σ a t-sequence, and say P (a, b) contains σ.

For given σ, we consider the set L = L(σ) of ordered pairs (a, b), a ∈ A_{0}, b ∈ B(a) which contain the sequence σ.

The total number of such sequences of length t is (2ρ)_{t}2^{t}. Any path P (a, b) contains at least ρ ≥ log n/ log log n unbroken segments, and thus at least \binom{ρ}{t} t-sequences. The average, over tsequences, of the number of pairs containing a given t-sequence is therefore at least

\frac{c^{2}n^{2}\binom{ρ}{t}}{(2ρ)_{t}2^{t}} ≥ αn^{2},

where α = c^{2}/(4t)^{t}. Thus there is a t-sequence σ_{0} and a set L = L(σ_{0}), |L| ≥ αn^{2} of pairs (a, b) such that for each (a, b) ∈ L the path P (a, b) contains σ_{0}. Let Â = {a : L contains at least αn/2 pairs with a as first element}. Then |Â| ≥ αn/2. For each a ∈ Â let B̂(a) = {b : (a, b) ∈ L}.

Let t = 1700D^{2}/c, D = 32k^{2}/ϵ and let C_{1} denote the union of the first t/2 segments of σ_{0}, in the fixed order and with the fixed relative orientation in which they occur along any of the paths P (a, b), (a, b) ∈ L. Let C_{2} denote the union of the second t/2 segments of σ_{0}. C_{1} and C_{2} contain at least \frac{t}{2} cn \frac{log log n}{4 log n}(1 − o(1)) interior points which from Lemma 7 gives sets C′_{1}, C′_{2} with at least

\frac{tc(1 − o(1))}{16}n\frac{log log n}{log n} ≥ 100D^{2}n\frac{log log n}{log n}

interior points.

It follows from D4 that there exists â ∈ Â such that H contains an edge from â to C′_{1}. Similarly, H contains an edge joining some b̂ ∈ B̂(â) to C′_{2}. Let x be some vertex separating C′_{1} and C′_{2} along P̂ = P (â, b̂). We now consider the two half paths P_{1}, P_{2} obtained by splitting P̂ at x. We consider rotations of P_{i}, i = 1, 2 with x as a fixed endpoint. We show that in both cases the finally constructed endpoint sets V_{1}, V_{2} are large enough so that D4 guarantees an edge from V_{1} to V_{2}. We deduce that H is Hamiltonian as the path it closes is of maximum length and H is connected.

Consider P_{1}. Let T_{i} = {v ∈ C′_{1} : v ≠ x is the endpoint of a path obtainable from P_{1} by t rotations with fixed endpoint x, pivot in int(C′_{1}) and all broken edges in P_{1}}. We claim we can choose sets U_{i} ⊆ T_{i}, i = 1, 2, … such that |U_{1}| = 1 and |U_{i+1}| = 2|U_{i}|, as long as |U_{i}| ≤ Dn\frac{log log n}{log n}. Thus there is an i^{∗} such that |U_{i^{∗}}| ≥ Dn\frac{log log n}{log n} and we are done. Note that T_{1} ≠ ∅ because â has an H-neighbour in int(C′_{1}). Note also that if we make a rotation with pivot in int(C′_{1}) and broken edge in P_{1} then the new endpoint created is C′_{1}.

Let y be a vertex of U_{i}. Then by Lemma 7 there are at least 100D log log n edges between y and int(C′_{1}). Thus the number of edges from U_{i} to int(C′_{1}) is at least 50|U_{i}|D log log n. As | ⋃_{j=1}^{i} U_{i}| < 2|U_{i}| at most 20D|U_{i}| log log n of these edges are contained in ⋃_{j=1}^{i} U_{j} (from P8), and so by P7 we have |T_{i+1}| > 2|U_{i}| and we select a subset of size exactly 2|U_{i}|.

8 Similar Problems

We note that it is straightforward to extend the above analysis to find the corresponding thresholds when Hamilton cycle is replaced by perfect matching or spanning tree. Now whp one needs enough edges so that the following replacements for conditions P9 and P10 hold true.

P9a G has minimum degree k − 1.

P10a G has at most k − 1 vertices of degree k − 1

That these conditions are necessary can be argued as in Section 4, since connectivity and the existence of a perfect matching require minimum degree one. Lemma 3 is replaced by

Lemma 8 Let A_{1}, A_{2}, …, A_{n} be disjoint sets with |A_{i}| = k − 1, 1 ≤ i ≤ r ≤ k − 1 and |A_{i}| = m_{i}k, r + 1 ≤ i ≤ n, where the m_{i}’s are positive integers. Let A = A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{n}. Suppose that the elements of A are coloured so that no colour is used more than k times. Then there exists a multicoloured subset B of A such that |A_{i} ∩ B| = 1, 1 ≤ i ≤ r and |A_{i} ∩ B| = m_{i}, r + 1 ≤ i ≤ n.

The proof is the same.

We choose E_{1} and E_{2} in the same way as before. The fact that H is connected proves the existence of a multicoloured tree. For a perfect matching one can remove from H all vertices of degree one together with their neighbours and argue that the graph that remains is Hamiltonian (assuming n is even). The proof is essentially that of Section 7.

References

[1] M. Ajtai, J. Komlós and E. Szemerédi. The first occurrence of Hamilton cycles in random graphs. Annals of Discrete Mathematics 27 (1985) 173-178.

[2] M.J. Albert, A.M. Frieze and B. Reed, Multicoloured Hamilton Cycles. Electronic Journal of Combinatorics 2 (1995) R10.

[3] B. Bollobás. The evolution of sparse graphs. Graph Theory and Combinatorics. (Proc. Cambridge Combinatorics Conference in Honour of Paul Erdős (B. Bollobás; Ed)) Academic Press (1984) 35-57

[4] B. Bollobás. Random Graphs. Academic Press (1985)

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

[6] B. Bollobás, T.I. Fenner and A.M. Frieze. An algorithm for finding Hamilton cycles in random graphs. Combinatorica 7 (1987) 327-341.

[7] B. Bollobás, T. Fenner and A.M. Frieze. Hamilton cycles in random graphs with minimal degree at least k. (A Tribute to Paul Erdős (A.Baker, B.Bollobas and A.Hajnal; Ed)) (1990) 59-96.

[8] C. Cooper. 1-pancyclic Hamilton cycles in random graphs. Random Structures and Algorithms 3.3 (1992) 277-287

[9] C. Cooper and A. Frieze. Pancyclic random graphs. Proc. 3rd Annual Conference on Random Graphs, Poznan 1987. Wiley (1990) 29-39

[10] C. Cooper and A. Frieze. On the lower bound for the number of Hamilton cycles in a random graph. Journal of Graph Theory 13.6 (1989) 719-735 the electronic journal of combinatorics 2 (1995), #R19 18 [11] P. Erdős and A. Rényi. On the strength of connectedness of a random graph. Acta. Math. Acad.

Sci. Hungar. 12 (1961) 261-267.

[12] A. Frieze and B. Reed. Polychromatic Hamilton cycles. Discrete Maths. 118 (1993) 69-74.

[13] G. Hahn and C. Thomassen. Path and cycle sub-Ramsey numbers, and an edge colouring conjecture. Discrete Maths. 62 (1986) 29-33

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

[15] T. Łuczak. Cycles in random graphs. Discrete Maths. (1987)

[16] T. Łuczak, On the equivalence of two basic models of random graph, Proceedings of Random graphs 87, Wiley, Chichester (1990), 151-159.

[17] Rödl and A. Ruciński, Threshold functions for Ramsey properties. (to appear)

[18] Rödl and Winkler. Private communication (1984) the electronic journal of combinatorics 2 (1995), #R19 19

Appendix: Proofs of P6–P8

P5 T ⊆ V, |T | ≤ n/(log n)^{2} implies T contains at most 3|T | edges. The number of edges in T is Bin (\binom{|T |}{2}, p). By (4) the probability that there exists T with 3|T | edges is at most

∑_{t=7}^{n/(log n)^{2}} \binom{n}{t} (\frac{e\binom{t}{2}p}{3t})^{3t} e^{−\binom{t}{2}p} ≤ ∑_{t} (\frac{ne}{t})^{t} (\frac{(1 + o(1))et log n}{6n})^{3t}
≤ ∑_{t} (\frac{(log n)^{3}t^{2}}{n^{2}} )^{t}
= o(1).

P6 A, B ⊆ V, A ∩ B = ∅, |A|, |B| ≥ 15n log log n/ log n implies G contains at least |A||B| log n/2n edges joining A and B. The number of edges between A and B is Bin(|A| |B|, p). By (3), the probability there exist sets A, B with less than half the expected number of edges between them, is at most

∑_{a,b} \binom{n}{a}\binom{n}{b} (\frac{2}{e})^{abp} ≤ exp \{a log(ne/a) + b log(ne/b) − abp log(e/2)\}
≤ n^{2} exp \{−\frac{n(log log n)^{2}}{log n} (15)^{2} (log(e/2) − 2/15)\}
= o(1),

by the same arguments as those following (6) in Lemma 6. P7 A, B ⊆ V, A ∩ B = ∅, |A| ≤ |B| ≤ 2|A| and |B| ≤ Dn log log n/ log n (D ≥ 1) implies that there are at most 10D|A| log log n edges joining A and B. Let |B| = 2|A| = 2a. We have then that the probability that there exist A, B such that there are at least 10D|A| log log n edges between the sets is at most

∑_{a} \binom{n}{a}\binom{n}{2a}\binom{2a^{2}}{10Da log log n}p^{10Da log log n} ≤ ∑_{a} [(\frac{ne}{a}) (\frac{ne}{2a})^{2} (\frac{ae log n}{5Dn log log n})^{10D log log n}]^{a}
≤ ∑_{a} [\frac{e^{3}}{4} (\frac{log n}{2D log log n})^{3} (\frac{e}{5})^{10D log log n}]^{a}
≤ ∑_{a} (\frac{1}{log n})^{a}
= o(1).

P8 If |A| ≤ Dn log log n/ log n (D ≥ 1) then A contains at most 10D|A| log log n edges.

We may assume |A| > n/(log n)^{2} by P5. The number of induced edges in A is Bin (\binom{|A|}{2}, p). By (4) the probability there exists a set A with at least 20(1 − o(1)) times the expected number of edges is at most,

∑_{a} \binom{n}{a} (\frac{e}{19})^{10Da log log n} ≤ ∑_{a} n exp \{a log(ne/a) − 10Da log log n log(19/e)\}
≤ ∑_{a} n exp \{−\frac{Dn log log n}{(log n)^{2}} (10 log(19/e) − 2)\}
= o(1).