\documentstyle[12pt]{article}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 2 (1995), \#R10\hfill}
\thispagestyle{empty}
\parindent 0in
\parskip 1.5ex
\def\bA{\bar{A}}
\def\a{\alpha}
\def\b{\beta}
\def\d{\delta}
\def\D{\Delta}
\def\e{\epsilon}
\def\f{\phi}
\def\F{\Phi}
\def\g{\gamma}
\def\G{\Gamma}
\def\k{\kappa}
\def\K{\Kappa}
\def\z{\zeta}
\def\th{\theta}
\def\TH{\Theta}
\def\l{\lambda}
\def\L{\Lambda}
\def\m{\mu}
\def\n{\nu}
\def\p{\pi}
\def\P{\Pi}
\def\r{\rho}
\def\R{\Rho}
\def\s{\sigma}
\def\S{\Sigma}
\def\t{\tau}
\def\om{\omega}
\def\OM{\Omega}
\def\cK{{\cal K}}
\def\C{\hat{C}}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}

\newcommand{\limninf}{\mbox{$\lim_{n \rightarrow \infty}$}}
\newcommand{\proofstart}{{\bf Proof\hspace{2em}}}
\newcommand{\proofend}{\hspace*{\fill}\mbox{$\Box$}}
\newcommand{\bfm}[1]{\mbox{\boldmath $#1$}}
\newcommand{\reals}{\mbox{\bfm{R}}}
\renewcommand{\Pr}{\mbox{\bf Pr}}
\newcommand{\expect}{\mbox{\bf E}}
\newcommand{\card}[1]{\mbox{$|#1|$}}
\newcommand{\half}{\mbox{$\frac{1}{2}$}}
\newcommand{\scaps}[1]{\mbox{\sc #1}}
\newcommand{\rdup}[1]{{\mbox{$ \lceil #1 \rceil $}}}
\newcommand{\rdown}[1]{{\mbox{$ \lfloor #1 \rfloor $}}}

\begin{document}

\baselineskip 20pt \lineskip 3pt

\title{MULTICOLOURED HAMILTON CYCLES}

\author{Michael Albert, Alan Frieze and Bruce Reed\thanks{Current address 
of Bruce Reed:
Equipe Combinatoire, CNRS, Universit\'e Pierre et Marie Curie, 4 Place 
Jussieu, Paris, France} 
 \\Department of Mathematics, Carnegie-Mellon University,\\
Pittsburgh, U.S.A.\thanks{Alan Frieze: partially supported by NSF grant
CCR-9225008}\\ \\
Submitted: April 25th,1995\\
Accepted May 9th, 1995}
\date{}
\maketitle
\begin{abstract}
The edges of the complete graph $K_n$ are coloured so that no colour appears
more than $\lceil cn\rceil$ 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 \cite{HT}. 
We prove a similar result for the complete digraph with $c<1/64$. 
We also show, by essentially the same technique, that if $t\geq 3$,
$c<(2t^2(1+t))^{-1}$, no 
colour appears more than
$\rdup{cn}$ times and $t|n$ then the vertices can be partitioned into
$n/t$ $t-$sets $K_1,K_2,\ldots,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\H{o}s and Spencer's \cite{ES} modification of
the Local Lemma \cite{AS}.
\end{abstract}
\section{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 {\em multicoloured}
if each edge is of a different colour. We say that the colouring is 
{\bf 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\geq 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 {\em guarantee}
that a $k$-bounded colouring is H-good.

The problem is mentioned in Erd\"os, Nestril and R\"odl \cite{ENR}. There
they mention it as an Erd\"os - Stein problem and show that $k$ can be any
constant.
Hahn and Thomassen \cite{HT}
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\"{o}dl and Winkler \cite{W} in 1984 improved
this to $n^{1/2}$. Frieze and Reed \cite{FR} showed that
there is an absolute constant $A$ such that if $n$ is sufficiently large and
$k$ is at most $\lceil n/(A\ln n)\rceil$ then any $k$-bounded colouring
is H-good.

In this paper we remove the $\log n$ factor and prove the conjecture of
\cite{HT}.
\begin{theorem}
\label{th1}
If $n$ is sufficiently large and
$k$ is at most $\lceil cn\rceil$, where $c<1/32$ then any $k$-bounded
colouring of $K_n$ is H-good.
\end{theorem}
We can extend this to the directed case.
\begin{theorem}
\label{th2}
If $n$ is sufficiently large and
$k$ is at most $\lceil cn\rceil$, where $c<1/64$ then any $k$-bounded
colouring of the edges of 
the complete digraph $DK_n$ is H-good.
\end{theorem}
As another wrinkle on this problem, we have
\begin{theorem}
\label{th5}
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.
\end{theorem}
We prove Theorem's \ref{th1}, \ref{th2} and \ref{th5}  as corollaries of
the following.
\begin{theorem}
\label{th3}
Let $\G$ be a graph whose vertex set is the edge set of $K_n$. Suppose
that $\G$ 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 $\G$.
\end{theorem}
We finally consider multi-coloured sets of cliques of size $t$. More
precisely, assume that 
$t\geq 3,t|n$, and let $\cK=K_1,K_2,\ldots, K_{n/t}$ be a partition of
$[n]$ into subsets of
size $n/t$. We say that $\cK$ is multi-coloured if the set of $n(t-1)/2$
edges which have both endpoints
in the same $t$-set is multi-coloured.
\begin{theorem}
\label{th4}
If $n$ is sufficiently large and
$k$ is at most $\rdup{cn}$, $c<(2t^2(1+t))^{-1}$, then in any
$k$-bounded colouring of the edges of 
$K_n$ there is multi-coloured partition $\cK$.
\end{theorem}
\section{Modification of the Lov\`asz local lemma}
\label{LLL}
Let $A_1,A_2,\ldots,A_N$ denote events in some probability space. Using
$\bar{A }$ to denote the complement
of an event $A$,
we are as usual interested in showing that $\Pr(\bigcap_{i=1}^n\bar{A}_i)>0.$

Suppose that for each $i$ there is a partition of $[N]\setminus \{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\H{o}s and Spencer \cite{ES}.

We consider one of the terms in the expression
\begin{equation}
\label{1}
\Pr\left(\bigcap_{i=1}^N\bA_i\right)=\prod_{i=1}^N\Pr\left(\bA_i\mid
\bigcap_{j=1}^{i-1}\bA_j\right).
\end{equation}
We want to show that for $1\leq i\leq N$,
\begin{equation}
\label{1a}
\Pr\left(\bA_i\mid \bigcap_{j=1}^{i-1}\bA_j\right)>0.
\end{equation}
So, we try to prove by induction on $|S|,\,S\subseteq [N]$, that for
$i\not\in S$,
\begin{equation}
\label{2}
\Pr\left(A_i\mid \bigcap_{j\in S}\bA_j\right)\leq \a,
\end{equation}
for some suitable choice of $\a$.

Now,
\begin{eqnarray}
\Pr\left(A_i\mid \bigcap_{j\in S}\bA_j\right)
&=&
{\Pr\left(A_i\cap \bigcap_{k\in S\cap Y_i}\bA_k\mid 
\bigcap_{j\in S\cap X_i}\bA_j\right)
\over 
\Pr\left(\bigcap_{k\in S\cap Y_i}\bA_k\mid 
\bigcap_{j\in S\cap X_i}\bA_j\right)}
\nonumber\\
&\leq&{\Pr\left(A_i\mid \bigcap_{j\in S\cap X_i}\bA_j\right)
\over \Pr\left(\bigcap_{k\in S\cap Y_i}\bA_k\mid 
\bigcap_{j\in S\cap X_i}\bA_j\right)}\nonumber\\
&\leq&{\Pr\left(A_i\mid \bigcap_{j\in S\cap X_i}\bA_j\right)
\over 1-\sum_{k\in S\cap Y_i}
\Pr\left(A_k\mid \bigcap_{j\in S\cap X_i}\bA_j\right)}\label{3}
\end{eqnarray}
Let now
\begin{equation}
\label{4}
\b=\max\{\Pr(A_i\mid \bigcap_{j\in T}\bA_j):i\in [N],T\subseteq X_i\},
\end{equation}
and
\begin{equation}
\label{5}
m=\max\{|Y_i|:i\in [N]\}.
\end{equation}
We will have to prove that given $m,\b$ we can choose $0\leq\a<1$ such that 
\begin{equation}
\label{6}
\a(1-m\a)\geq \b.
\end{equation}
Assume that (\ref{6}) holds. If $S\subseteq X_i$ then (\ref{4}) and
(\ref{6}) will imply
\begin{eqnarray*}
\Pr\left(A_i\mid \bigcap_{j\in S}\bA_j\right)&\leq&\b\\
&\leq&\a.
\end{eqnarray*}
On the other hand if $S\not\subseteq X_i$ then we can apply the 
induction hypothesis 
to $\Pr(A_k\mid \bigcap_{j\in S\cap X_i}\bA_j)$ in the numerator of
(\ref{3}) and obtain
\begin{eqnarray*}
\Pr\left(A_i\mid \bigcap_{j\in S}\bA_j\right)&\leq&{\b\over 1-m\a}\\
&\leq&\a,
\end{eqnarray*}
by (\ref{6}). 

The base case of the induction, $S=\emptyset$, follows from considering
$T=\emptyset$ in (\ref{4}) 
and using $\b\leq\a$.

So the proof of (\ref{1a}) rests on proving that (\ref{6}) holds. This
is what we do for Theorem 
\ref{th3}. The proof of Theorem \ref{th4} is slightly different, in that
we need to partition $A_1,A_2,\ldots,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.
\begin{lemma}
Let $A_1,A_2,\ldots,A_N$ denote events in some probability space. 
Suppose that for each $i$ there is a partition of $[N]\setminus \{i\}$
into $X_i$ and 
$Y_i$. Let $m=\max\{|Y_i|:i\in [N]\}$ and $\b=\max\{\Pr(A_i\mid 
\bigcap_{j\in T}\bA_j):i\in [N],T\subseteq X_i\}$. If there exists
$0\leq \a<1$ such 
that $\a(1-m\a)\geq \b$ then $\Pr(\bigcap_{i=1}^n\bar{A}_i)>0.$
\end{lemma}
\section{Hamilton Cycles}
\subsection{Proof of Theorems \protect{\ref{th1} and \ref{th2}}}
We show here that Theorems \ref{th1} and \ref{th2} are corollaries of
Theorem \ref{th3}. 
Assume $n$ is large and $k\leq cn$, and an arbitrary $k$-bounded
colouring of $K_n$ is given.

To prove 
Theorem \ref{th1} we define $\G$ as follows. Two edges $e,f$ of $K_n$ 
correspond to the endpoints of an edge of $\G$ if and
only if they have the same colour. 
Thus a  set of vertices of $\G$ is independent if and only it corresponds
to a multicoloured set of edges of $K_n$.
Clearly the maximum degree of $\G$ is at most $k-1$ and so 
we can apply Theorem \ref{th3} to obtain Theorem \ref{th1}. 

To prove Theorem \ref{th2} we need a slight change in the definition of $\G$.
Two edges $e=\{e_0,e_1\},f=\{f_0,f_1\}$ of $K_n$ define an edge of $\G$
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 $\G$ is independent if and only the set
of edges obtained by taking,
each $e=\{e_0,e_1\}\in 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 $\G$ is at most $2(k-1)$ and so 
we can apply Theorem \ref{th3} to obtain a slight strengthening of
Theorem \ref{th1} viz. there is a 
Hamilton cycle and its reversal spanning a multicoloured set of directed
edges. 

To prove Theorem \ref{th5} we let two  edges $e,f$ of $K_n$ 
correspond to the endpoints of an edge of $\G$ if and
only if they have the same colour and are incident with a common vertex.
\subsection{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\leq i\leq N\}$ be an enumeration of the  edges of $\G$. Let 
$$A_i=\{H:e_i,f_i\mbox{ are both edges of }H\}.$$
We will prove Theorem \ref{th1} by using the argument of Section
\ref{LLL} to show 
that $\Pr\left(\bigcap_{i=1}^N\bA_i\right)>0$.
We use the notation of that section.

For $1\leq i\leq N$ let
$$Y_i=\{j\neq i:(e_j\cup f_j)\cap (e_i\cup f_i)\neq \emptyset\}.$$
Thus $j\in 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]\setminus (Y_i\cup \{i\}).$ Clearly, $|Y_i|\leq 4cn^2$ and so
$$m\leq 4cn^2.$$
We will show that
\begin{equation}
\label{beta}
\b\leq{2\over n^2-15n+56}
\end{equation}
and Theorem \ref{th1} follows on choosing 
$$\a = {1\over 8c}\left(1-\sqrt{1-(32+\e)c}\right)n^{-2}$$
and checking that (\ref{6}) holds for $\e>0$ sufficiently small and $n$
sufficiently large. 

[Now $m\a\leq (1-\sqrt{1-(32+\e)})/2$ and so $1-m\a\geq
(1+\sqrt{1-(32+\e)})/2$. Thus $\a(1-m\a)>(2+\e/16)n^{-2}$.]

Equation (\ref{beta}) follows from the following Lemma:
\begin{lemma}
\label{lem1}
Let $e,f$ be edges of $K_n$ and $X\subseteq 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\neq C'$ then
$S(C)\cap S(C')=\emptyset$.
\end{lemma}
\proofstart
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\longrightarrow f_0,f_1\longrightarrow 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:
\begin{eqnarray*}
C&=&e_0,e_1\longrightarrow x_0,x_1\longrightarrow f_0,f_1\longrightarrow
y_0,y_1\longrightarrow e_o.\\
\noalign{or}
C&=&e_0,e_1\longrightarrow f_0,f_1\longrightarrow x_0,x_1\longrightarrow
y_0,y_1\longrightarrow e_o.
\end{eqnarray*}
In the first case define:
\begin{eqnarray*}
\C_{x,y}&=&e_0,x_0\longrightarrow e_1,y_0\longrightarrow
f_1,x_1\longrightarrow f_0,y_1\longrightarrow e_o.\\
\noalign{In the second case define:}
\C_{x,y}&=&e_0,x_1\longrightarrow y_0,f_1\longrightarrow
x_0,e_1\longrightarrow f_0,y_1\longrightarrow e_o.
\end{eqnarray*}
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 $\C_{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 $\C_{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)=\{\C_{x,y}: x,y$ as above \}, we obtain $|S(C)|\geq
(n-6)(n-9)/2$
and $S(C)\cap S(C')=\emptyset$ for $C\neq C'$.
\proofend

To prove (\ref{beta}) we apply Lemma \ref{lem1} with $i\in
[N],\,\{e,f\}=\{e_i,f_i\}$ and $X\subseteq X_i$.
Let ${\cal C}$ denote the set of Hamilton cycles containing $e_i$ and $f_i$. 
Then  
\begin{eqnarray*}
\Pr(A_i\mid\bigcap_{j\in X}\bA_j )&=&\sum_{C\in {\cal C}}\Pr(H=C\mid
\bigcap_{j\in X}\bA_j)\\
&\leq &{2\over n^2-15n+56}\sum_{C\in {\cal C}}\Pr(H\in \{C\}\cup
S(C)\mid \bigcap_{j\in X}\bA_j)\\
&\leq&{2\over n^2-15n+56}.
\end{eqnarray*}
This completes the proof of Theorem \ref{th3}.
\section{Partition into cliques}
Assume $n$ is large and $k\leq cn$, $c<(2t^2(1+t))^{-1}$, and an
arbitrary $k$-bounded colouring of $K_n$ is given. Let $\{(S_1,T_1),
(S_2,T_2),\ldots,(S_N,T_N)\}$ be an enumeration of the pairs of
$t$-subsets of $[n]$ such that for each $1\leq i\leq 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\cap T_i=\emptyset$ and
there are edges $e,f$ of the same colour, $e\subseteq S_i, f\subseteq
T_i$. In either case we say that $(S_i,T_i)$ contains
$e,f$.

Let $I_a=\{i\in [N]:S_i=T_i\}$ and $I_b=[N]\setminus I_a$. Now let $\cK$
be chosen randomly 
from the set of possible partitions and define the events
$$A_i=\{S_i\mbox{ and }T_i\mbox{ are both members of }\cK\}.$$
Once again, we prove that $\Pr(\bigcap_{i=1}^n\bar{A}_i)>0.$

We now define $Y_i=\{j\neq i:$ the following three conditions hold:
\begin{enumerate}
\item $\max\{|S_j\cap S_i|,\,|S_j\cap T_i|\geq t-1$.
\item $\max\{|T_j\cap S_i|,\,|T_j\cap T_i|\geq t-1$.
\item $(S_j,T_j)$ contains a pair of identically coloured edges $e,f$
which are {\em not} contained
in $(S_i,T_i)$\}.
\end{enumerate}
Naturally, $X_i=[N]\setminus (Y_i\cup \{i\})$.

We elaborate the argument of Section \ref{LLL}. We prove the existence
of $0<\a_a,\a_b<1$ such that if $S\subseteq [N]$
and $i\in I_x\setminus S$, where $x=a$ or $b$, then
$$\Pr\left(A_i\mid\bigcap_{j\in S}\bA_j\right)\leq \a_x.$$
To do this, we define, for $x=a$ or $b$, 
\begin{eqnarray*}
\b_x&=&\max\{\Pr(A_i\mid\bigcap_{j\in T}\bA_j ):i\in I_x,T\subseteq X_i\}\\
\noalign{and}
m_x&=&\max\{|Y_i|:i\in I_x\}.
\end{eqnarray*}
We will then, in analogy with (\ref{6}), only need to show that for
$x=a$ or $b$, 
\begin{equation}
\label{c2}
\a_x(1-m_a\a_a-m_b\a_b)\geq \b_x.
\end{equation}
Consider first the case where $i\in I_a$. Then $j\in X_i$ implies $j\in I_a$.

[$|S_j\cap T_j|\geq |S_j\cap S_i\cap T_j\cap S_i|\geq |S_j\cap
S_i|+|T_j\cap S_i|-|S_i|\geq 2(t-1)-t>0$.]

Now 
\begin{equation}
\label{cma}
m_a\leq t{t-1\choose 2}k.
\end{equation}
{\bf Explanation:} We choose $S_j$ by (i) choosing $x\in S_i$, (ii)
$e=\{x_1,x_2\}\subseteq S_i\setminus \{x\}$
and then $y\not\in 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\setminus \{x\})\cup \{y\}$.

We argue next that
\begin{equation}
\label{cba}
\b_a\leq {1\over t(n-t+1)}.
\end{equation}
{\bf Explanation:} Given $\cK\in A_i\cap \bigcap_{j\in T}\bA_j$,
$T\subseteq X_i$, we can obtain $t(n-t)$ distinct
partitions which are in $\bA_i\cap \bigcap_{j\in T}\bA_j$ as follows:
Choose $x\in S_i$ and $y\in S$, where $S$
is another $t$-set of $\cK$. Replace $S_i$ by $(S_i\cup \{y\})\setminus
\{x\}$ and $S$ by $(S\cup \{x\})\setminus \{y\}$
to obtain $\cK'$.
Note that given $\cK'$ we can re-construct $\cK$: $x$ is the unique
element of $S_i$ which is in a set with elements 
not in $S_i$ and $y\not\in 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\in I_b$. Now $j\in X_i$ implies that
$j\in I_b$. Also,
\begin{equation}
\label{cmb}
m_b\leq t^2 {t-1\choose 2} (t-1) (n-t) k.
\end{equation}
{\bf Explanation:} We choose $S_j,T_j$ by (i) choosing $x\in S_i,y\in
T_i$, (ii) $e=\{x_1,x_2\}\subseteq S_i\setminus
\{x\}$, (iii) $z\not\in S_i$, (iv) $w\in T_i\setminus \{y\}$, (v) $v\in
[n]$ such that the colour of $\{v,w\}$ is the 
same as that of $e$. Then take $S_j=(S_i\setminus \{x\})\cup \{z\}$ and
$T_j=(T_i\setminus \{y\})\cup \{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,
\begin{equation}
\label{cbb}
\b_b\leq {1\over t^2(n-2t)(n-3t)+1}.
\end{equation}
{\bf Explanation:} Given $\cK\in A_i\cap \bigcap_{j\in T}\bA_j$,
$T\subseteq X_i$, we can obtain $t^2(n-2t)(n-3t)$ distinct
partitions which are in $\bA_i\cap \bigcap_{j\in T}\bA_j$ as follows:
Choose $x\in S_i$ and $y\in T_i$. Then choose $x',y'\not\in S_i\cup T_i$
in distinct subsets $S,S'$ of $\cK$. Replace $S_i$ by $(S_i\cup
\{x'\})\setminus \{x\}$,  
$T_i$ by $(T_i\cup \{y'\})\setminus \{y\}$, $S$ by $(S\cup
\{x\})\setminus \{x'\}$ and $T$ by $(T\cup \{y\})\setminus \{y'\}$. 
to obtain $\cK'$. Note once again, that given $\cK'$ we can re-construct $\cK$.

With these values for $m_a,m_b,\b_a,\b_b$ we can enforce (\ref{c2}) by
choosing 
$$\a_a= 2/t\mbox{ and }\a_b=2/t^2 .$$
This completes the proof of Theorem \ref{th4}.
\begin{thebibliography}{99}
\bibitem{AS}N.Alon and J.H.Spencer, The probabilistic method, John Wiley
and Sons, 
New York, 1992.
\bibitem{ES}P.Erd\H{o}s and J.Spencer, {\em Lopsided Lov\'asz local
lemma and Latin 
transversals}, Discrete Applied Mathematics 30 (1990) 151-154.
\bibitem{ENR}P.Erd\"os, J.Nesetril and V.R\"odl, {\em Some problems related to 
partitions of edges of a graph} in Graphs and other Combinatorial topics,
Teubner, Leipzig (1983) 54-63.
\bibitem{FF}T.I.Fenner and A.M.Frieze, {\em 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.
\bibitem{FR}A.M.Frieze and B.A.Reed, {\em Polychromatic Hamilton
cycles}, Discrete Mathematics
118, (1993) 69-74.
\bibitem{H}W.H\"{o}effding,{\em Probability inequalities for sums of bounded
random variables}, Journal of the American Statistical Association 58 (1963)
13-30.
\bibitem{HT}G.Hahn and C.Thomassen, {\em Path and cycle sub-Ramsey numbers
and an edge-colouring conjecture}, Discrete Mathematics 62 (1986) 29-33.
\bibitem{P}L.P\'{o}sa,{\em Hamilton circuits in random graphs},Discrete 
Mathematics 14 (1976) 359-64.
\bibitem{W}P.Winkler, Private Communication.
\end{thebibliography}
\end{document}