MULTICOLOURED HAMILTON CYCLES

Michael Albert, Alan Frieze and Bruce Reed^{∗} Department of Mathematics, Carnegie-Mellon University,

Pittsburgh, U.S.A.^{†}

Submitted: April 25th,1995 Accepted May 9th, 1995

Abstract

The edges of the complete graph K_{n} are coloured so that no colour appears more than ⌈cn⌉ times, where c < 1/32 is a constant. We show that if n is sufficiently large then there is a Hamiltonian cycle in which each edge is a different colour, thereby proving a 1986 conjecture of Hahn and Thomassen [7]. We prove a similar result for the complete digraph with c < 1/64. We also show, by essentially the same technique, that if t ≥ 3, c < (2t^{2}(1 + t))^{−1}, no colour appears more than ⌈cn⌉ times and t|n then the vertices can be partitioned into n/t t−sets K_{1}, K_{2}, …, K_{n/t} such that the colours of the n(t − 1)/2 edges contained in the K_{i}’s are distinct. The proof technique follows the lines of Erdős and Spencer’s [2] modification of the Local Lemma [1].

∗Current address of Bruce Reed: Equipe Combinatoire, CNRS, Université Pierre et Marie Curie, 4 Place Jussieu, Paris, France

†Alan Frieze: partially supported by NSF grant CCR-9225008

1 Introduction

Let the edges of the complete graph K_{n} be coloured so that no colour is used more than k = k(n) times. We refer to this as a k-bounded colouring. We say that a subset of the edges of K_{n} is multicoloured if each edge is of a different colour. We say that the colouring is H-good if a multi-coloured Hamilton cycle exists i.e., one with a multi-coloured edge-set. Clearly the colouring is H-good if k = 1 and may not be if k ≥ n/2, since then we may only use n−1 colours. The main question we address here then is that of how fast can we allow k to grow and still guarantee that a k-bounded colouring is H-good.

The problem is mentioned in Erdös, Nestril and Rödl [3]. There they mention it as an Erdös - Stein problem and show that k can be any constant. Hahn and Thomassen [7] were the next people to consider this problem and they 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 [9] in 1984 improved this to n^{1/2}. Frieze and Reed [5] 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.

In this paper we remove the log n factor and prove the conjecture of [7].

Theorem 1 If n is sufficiently large and k is at most ⌈cn⌉, where c < 1/32 then any k-bounded colouring of K_{n} is H-good.

We can extend this to the directed case.

Theorem 2 If n is sufficiently large and k is at most ⌈cn⌉, where c < 1/64 then any k-bounded colouring of the edges of the complete digraph DK_{n} is H-good.

As another wrinkle on this problem, we have

Theorem 3 Suppose the edges of K_{n} are coloured so that the graphs induced by the edges of a single colour all have maximum degree at most cn, where c < 1/32. Then there exists a Hamilton cycle in which each vertex is incident with two edges of a distinct colours.

We prove Theorem’s 1, 2 and 3 as corollaries of the following.

Theorem 4 Let Γ be a graph whose vertex set is the edge set of K_{n}. Suppose that Γ has maximum degree bounded above by cn, where c < 1/32. Then K_{n} contains a Hamilton cycle H whose edge set is an independent subset in Γ.

We finally consider multi-coloured sets of cliques of size t. More precisely, assume that t ≥ 3, t|n, and let K = K_{1}, K_{2}, …, K_{n/t} be a partition of [n] into subsets of size n/t. We say that K is multi-coloured if the set of n(t − 1)/2 edges which have both endpoints in the same t-set is multi-coloured.

Theorem 5 If n is sufficiently large and k is at most ⌈cn⌉, c < (2t^{2}(1+t))^{−1}, then in any k-bounded colouring of the edges of K_{n} there is multi-coloured partition K.

2 Modification of the Lovàsz local lemma

Let A_{1}, A_{2}, …, A_{N} denote events in some probability space. Using Ā to denote the complement of an event A, we are as usual interested in showing that Pr(⋂_{i=1}^{n} Ā_{i}) > 0.

Suppose that for each i there is a partition of [N] \ {i} into X_{i} and Y_{i}. In the usual version of the local lemma, A_{i} will be independent of the the events in X_{i}. Here all of the events will be interdependent, but one can still apply the methodology of the usual proof of the local lemma. We should point out here that this idea is not our own, it is already in Erdős and Spencer [2].

We consider one of the terms in the expression

Pr ( ⋂_{i=1}^{N} Ā_{i}) = ∏_{i=1}^{N} Pr (Ā_{i} | ⋂_{j=1}^{i−1} Ā_{j}) .  (1)

We want to show that for 1 ≤ i ≤ N,

Pr (Ā_{i} | ⋂_{j=1}^{i−1} Ā_{j}) > 0.  (2)

So, we try to prove by induction on |S|, S ⊆ [N], that for i ∉ S,

Pr (A_{i} | ⋂_{j∈S} Ā_{j}) ≤ α,  (3)

for some suitable choice of α.

Now,

Pr (A_{i} | ⋂_{j∈S} Ā_{j}) = \begin{matrix}Pr & (A_{i} ∩ ⋂_{k∈S∩Y_{i}} Ā_{k} | ⋂_{j∈S∩X_{i}} Ā_{j}) \\ Pr & (⋂_{k∈S∩Y_{i}} Ā_{k} | ⋂_{j∈S∩X_{i}} Ā_{j}) \end{matrix}
≤ \begin{matrix}Pr & (A_{i} | ⋂_{j∈S∩X_{i}} Ā_{j}) \\ Pr & (⋂_{k∈S∩Y_{i}} Ā_{k} | ⋂_{j∈S∩X_{i}} Ā_{j}) \end{matrix}
≤ \frac{Pr (A_{i} | ⋂_{j∈S∩X_{i}} Ā_{j})}{1 − ∑_{k∈S∩Y_{i}} Pr (A_{k} | ⋂_{j∈S∩X_{i}} Ā_{j})}  (4)

Let now

β = max{Pr(A_{i} | ⋂_{j∈T} Ā_{j}) : i ∈ [N], T ⊆ X_{i}},  (5)

and

m = max{|Y_{i}| : i ∈ [N]}.  (6)

We will have to prove that given m, β we can choose 0 ≤ α < 1 such that

α(1 − mα) ≥ β.  (7)

Assume that (7) holds. If S ⊆ X_{i} then (5) and (7) will imply

Pr (A_{i} | ⋂_{j∈S} Ā_{j}) ≤ β
≤ α.

On the other hand if S ⊈ X_{i} then we can apply the induction hypothesis to Pr(A_{k} | ⋂_{j∈S∩X_{i}} Ā_{j}) in the numerator of (4) and obtain

Pr (A_{i} | ⋂_{j∈S} Ā_{j}) ≤ \frac{β}{1 − mα}
≤ α,

by (7).

The base case of the induction, S = ∅, follows from considering T = ∅ in (5) and using β ≤ α.

So the proof of (2) rests on proving that (7) holds. This is what we do for Theorem 4. The proof of Theorem 5 is slightly different, in that we need to partition A_{1}, A_{2}, …, A_{N} into two types of event.

It may be useful to summarise the above discussion as a lemma in case it can be used in other circumstances.

Lemma 1 Let A_{1}, A_{2}, …, A_{N} denote events in some probability space. Suppose that for each i there is a partition of [N] \ {i} into X_{i} and Y_{i}. Let m = max{|Y_{i}| : i ∈ [N]} and β = max{Pr(A_{i} | ⋂_{j∈T} Ā_{j}) : i ∈ [N], T ⊆ X_{i}}. If there exists 0 ≤ α < 1 such that α(1 − mα) ≥ β then Pr(⋂_{i=1}^{n} Ā_{i}) > 0.

3 Hamilton Cycles

3.1 Proof of Theorems 1 and 2

We show here that Theorems 1 and 2 are corollaries of Theorem 4. Assume n is large and k ≤ cn, and an arbitrary k-bounded colouring of K_{n} is given.

To prove Theorem 1 we define Γ as follows. Two edges e, f of K_{n} correspond to the endpoints of an edge of Γ if and only if they have the same colour. Thus a set of vertices of Γ is independent if and only it corresponds to a multicoloured set of edges of K_{n}. Clearly the maximum degree of Γ is at most k − 1 and so we can apply Theorem 4 to obtain Theorem 1.

To prove Theorem 2 we need a slight change in the definition of Γ. Two edges e = {e_{0}, e_{1}}, f = {f_{0}, f_{1}} of K_{n} define an edge of Γ if and only if the colours of the four directed edges (e_{0}, e_{1}), (e_{1}, e_{0}), (f_{0}, f_{1}), (f_{1}, f_{0}) are not all distinct. Thus a set S of vertices of Γ is independent if and only the set of edges obtained by taking, each e = {e_{0}, e_{1}} ∈ S and replacing it by (e_{0}, e_{1}), (e_{1}, e_{0}) (giving 2|S| directed edges) is multicoloured. Clearly the maximum degree of Γ is at most 2(k − 1) and so we can apply Theorem 4 to obtain a slight strengthening of Theorem 1 viz. there is a Hamilton cycle and its reversal spanning a multicoloured set of directed edges.

To prove Theorem 3 we let two edges e, f of K_{n} correspond to the endpoints of an edge of Γ if and only if they have the same colour and are incident with a common vertex.

3.2 Proof of Theorem 4

Let H be a Hamilton cycle chosen uniformly at random from the set of (n − 1)!/2 Hamilton cycles of K_{n}. Let {(e_{i}, f_{i}) : 1 ≤ i ≤ N} be an enumeration of the edges of Γ. Let

A_{i} = {H : e_{i}, f_{i} are both edges of H}.

We will prove Theorem 1 by using the argument of Section 2 to show that Pr (⋂_{i=1}^{N} Ā_{i}) > 0. We use the notation of that section.

For 1 ≤ i ≤ N let

Y_{i} = {j ≠ i : (e_{j} ∪ f_{j}) ∩ (e_{i} ∪ f_{i}) ≠ ∅}.

Thus j ∈ Y_{i} if in K_{n}, one of e_{j}, f_{j} shares a vertex with one of e_{i}, f_{i}. Let X_{i} = [N] \ (Y_{i} ∪ {i}). Clearly, |Y_{i}| ≤ 4cn^{2} and so

m ≤ 4cn^{2}.

We will show that

β ≤ \frac{2}{n^{2} − 15n + 56}  (8)

and Theorem 1 follows on choosing

α = \frac{1}{8c} (1 − \sqrt{1 − (32 + ϵ)c}) n^{−2}

and checking that (7) holds for ϵ > 0 sufficiently small and n sufficiently large.

[Now mα ≤ (1 − \sqrt{1 − (32 + ϵ)})/2 and so 1 − mα ≥ (1 + \sqrt{1 − (32 + ϵ)})/2. Thus α(1 − mα) > (2 + ϵ/16)n^{−2}.]

Equation (8) follows from the following Lemma:

Lemma 2 Let e, f be edges of K_{n} and X ⊆ E(K_{n}) be such that no edge in X shares an endpoint with either e or f. Then we can find, for each Hamilton cycle C containing both e and f and no edges of X, a set S(C) of (n − 6)(n − 9)/2 Hamilton cycles containing neither e, f or any edge in X, in such a way that if C ≠ C′ then S(C) ∩ S(C′) = ∅.

Proof Let e_{0}, e_{1} and f_{0}, f_{1} be the endpoints of e and f respectively, chosen so that e_{0} has the smallest index of e_{0}, e_{1}, f_{0}, f_{1}. Let

C = e_{0}, e_{1} ⟶ f_{0}, f_{1} ⟶ e_{o}.

[It is possible that e_{1} = f_{0} here.]

Consider two disjoint edges x = (x_{0}, x_{1}), y = (y_{0}, y_{1}) of C sharing no endpoint with e or f. There are at least (n − 6)(n − 9)/2 choices for x, y. There are now two possibilities:

C = e_{0}, e_{1} ⟶ x_{0}, x_{1} ⟶ f_{0}, f_{1} ⟶ y_{0}, y_{1} ⟶ e_{o}.

or

C = e_{0}, e_{1} ⟶ f_{0}, f_{1} ⟶ x_{0}, x_{1} ⟶ y_{0}, y_{1} ⟶ e_{o}.

In the first case define:

Ĉ_{x,y} = e_{0}, x_{0} ⟶ e_{1}, y_{0} ⟶ f_{1}, x_{1} ⟶ f_{0}, y_{1} ⟶ e_{o}.

In the second case define:

Ĉ_{x,y} = e_{0}, x_{1} ⟶ y_{0}, f_{1} ⟶ x_{0}, e_{1} ⟶ f_{0}, y_{1} ⟶ e_{o}.

In both cases we delete the edges e, f, x, y from C and add edges that are incident with one of e_{0}, e_{1}, f_{0}, f_{1}, so that Ĉ_{x,y} does not contain an edge of X.

It is important to realise that in both cases the procedure is reversible in that C can be reconstructed from Ĉ_{x,y}. We can recognise which case we are in from the relative order of the e’s and f’s and then identify the x’s and y’s from their positions.

Thus taking S(C) = {Ĉ_{x,y} : x, y as above }, we obtain |S(C)| ≥ (n − 6)(n − 9)/2 and S(C) ∩ S(C′) = ∅ for C ≠ C′. □

To prove (8) we apply Lemma 2 with i ∈ [N], {e, f} = {e_{i}, f_{i}} and X ⊆ X_{i}. Let C denote the set of Hamilton cycles containing e_{i} and f_{i}. Then

Pr(A_{i} | ⋂_{j∈X} Ā_{j}) = ∑_{C∈C} Pr(H = C | ⋂_{j∈X} Ā_{j})
≤ \frac{2}{n^{2} − 15n + 56} ∑_{C∈C} Pr(H ∈ \{C\} ∪ S(C) | ⋂_{j∈X} Ā_{j})
≤ \frac{2}{n^{2} − 15n + 56}.

This completes the proof of Theorem 4.

4 Partition into cliques

Assume n is large and k ≤ cn, c < (2t^{2}(1 + t))^{−1}, and an arbitrary kbounded colouring of K_{n} is given. Let {(S_{1}, T_{1}), (S_{2}, T_{2}), …, (S_{N}, T_{N})} be an enumeration of the pairs of t-subsets of [n] such that for each 1 ≤ i ≤ N either (a) S_{i} = T_{i} and S_{i} contains a pair of edges e, f of the same colour, or (b) S_{i} ∩ T_{i} = ∅ and there are edges e, f of the same colour, e ⊆ S_{i}, f ⊆ T_{i}. In either case we say that (S_{i}, T_{i}) contains e, f.

Let I_{a} = {i ∈ [N] : S_{i} = T_{i}} and I_{b} = [N]\I_{a}. Now let K be chosen randomly from the set of possible partitions and define the events

A_{i} = {S_{i} and T_{i} are both members of K}.

Once again, we prove that Pr(⋂_{i=1}^{n} Ā_{i}) > 0.

We now define Y_{i} = {j ≠ i : the following three conditions hold:

1. max{|S_{j} ∩ S_{i}|, |S_{j} ∩ T_{i}| ≥ t − 1.

2. max{|T_{j} ∩ S_{i}|, |T_{j} ∩ T_{i}| ≥ t − 1.

3. (S_{j}, T_{j}) contains a pair of identically coloured edges e, f which are not contained in (S_{i}, T_{i})}.

Naturally, X_{i} = [N] \ (Y_{i} ∪ {i}).

We elaborate the argument of Section 2. We prove the existence of 0 < α_{a}, α_{b} < 1 such that if S ⊆ [N] and i ∈ I_{x} \ S, where x = a or b, then

Pr (A_{i} | ⋂_{j∈S} Ā_{j}) ≤ α_{x}.

To do this, we define, for x = a or b,

β_{x} = max{Pr(A_{i} | ⋂_{j∈T} Ā_{j}) : i ∈ I_{x}, T ⊆ X_{i}}

and

m_{x} = max{|Y_{i}| : i ∈ I_{x}}.

We will then, in analogy with (7), only need to show that for x = a or b,

α_{x}(1 − m_{a}α_{a} − m_{b}α_{b}) ≥ β_{x}.  (9)

Consider first the case where i ∈ I_{a}. Then j ∈ X_{i} implies j ∈ I_{a}.

[|S_{j} ∩ T_{j}| ≥ |S_{j} ∩ S_{i} ∩ T_{j} ∩ S_{i}| ≥ |S_{j} ∩ S_{i}| + |T_{j} ∩ S_{i}| − |S_{i}| ≥ 2(t − 1) − t > 0.]

Now

m_{a} ≤ t\binom{t − 1}{2}k.  (10)

Explanation: We choose S_{j} by (i) choosing x ∈ S_{i}, (ii) e = {x_{1}, x_{2}} ⊆ S_{i} \ {x} and then y ∉ S_{i} such that the colour of e is the same as that of {x_{1}, y} or {x_{2}, y}. We then take S_{j} = (S_{i} \ {x}) ∪ {y}.

We argue next that

β_{a} ≤ \frac{1}{t(n − t + 1)}.  (11)

Explanation: Given K ∈ A_{i} ∩ ⋂_{j∈T} Ā_{j}, T ⊆ X_{i}, we can obtain t(n − t) distinct partitions which are in Ā_{i} ∩ ⋂_{j∈T} Ā_{j} as follows: Choose x ∈ S_{i} and y ∈ S, where S is another t-set of K. Replace S_{i} by (S_{i} ∪ {y}) \ {x} and S by (S ∪ {x}) \ {y} to obtain K′. Note that given K′ we can re-construct K: x is the unique element of S_{i} which is in a set with elements not in S_{i} and y ∉ S_{i} is the unique such element which in a set with t − 1 members of S_{i}.

Now let us consider the case i ∈ I_{b}. Now j ∈ X_{i} implies that j ∈ I_{b}. Also,

m_{b} ≤ t^{2}\binom{t − 1}{2}(t − 1)(n − t)k.  (12)

Explanation: We choose S_{j}, T_{j} by (i) choosing x ∈ S_{i}, y ∈ T_{i}, (ii) e = {x_{1}, x_{2}} ⊆ S_{i} \ {x}, (iii) z ∉ S_{i}, (iv) w ∈ T_{i} \ {y}, (v) v ∈ [n] such that the colour of {v, w} is the same as that of e. Then take S_{j} = (S_{i} \ {x}) ∪ {z} and T_{j} = (T_{i} \ {y}) ∪ {w}. There are some restrictions on the choices of x, y, z, v, w which are ignored for the purposes of getting an upper bound.

Finally,

β_{b} ≤ \frac{1}{t^{2}(n − 2t)(n − 3t) + 1}.  (13)

Explanation: Given K ∈ A_{i}∩⋂_{j∈T} Ā_{j}, T ⊆ X_{i}, we can obtain t^{2}(n−2t)(n− 3t) distinct partitions which are in Ā_{i} ∩ ⋂_{j∈T} Ā_{j} as follows: Choose x ∈ S_{i} and y ∈ T_{i}. Then choose x′, y′ ∉ S_{i}∪T_{i} in distinct subsets S, S′ of K. Replace S_{i} by (S_{i} ∪ {x′}) \ {x}, T_{i} by (T_{i} ∪ {y′}) \ {y}, S by (S ∪ {x}) \ {x′} and T by (T ∪ {y}) \ {y′}. to obtain K′. Note once again, that given K′ we can re-construct K.

With these values for m_{a}, m_{b}, β_{a}, β_{b} we can enforce (9) by choosing

α_{a} = 2/t and α_{b} = 2/t^{2}.

This completes the proof of Theorem 5.

References

[1] N.Alon and J.H.Spencer, The probabilistic method, John Wiley and Sons, New York, 1992.

[2] P.Erdős and J.Spencer, Lopsided Lovász local lemma and Latin transversals, Discrete Applied Mathematics 30 (1990) 151-154.

[3] P.Erdös, J.Nesetril and V.Rödl, Some problems related to partitions of edges of a graph in Graphs and other Combinatorial topics, Teubner, Leipzig (1983) 54-63.

[4] T.I.Fenner and A.M.Frieze, On the existence of polychromatic sets of edges in graphs and digraphs, Progress in Graph Theory, Edited by J.A. Bondy and U.S.R. Murty, Academic Press, 219-232.

[5] A.M.Frieze and B.A.Reed, Polychromatic Hamilton cycles, Discrete Mathematics 118, (1993) 69-74.

[6] W.Höeffding,Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963) 13-30.

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

[8] L.Pósa,Hamilton circuits in random graphs,Discrete Mathematics 14 (1976) 359-64.

[9] P.Winkler, Private Communication.