\documentstyle[12pt]{article}
\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 2 (1995), \#R19\hfill}
\thispagestyle{empty}
\parindent 0in
\parskip 1.5ex
%\addtolength{\oddsidemargin}{-0.8in}
%\newcommand{\info}[1]{\marginpar{\fbox{\parbox{1in}{#1}}}}
\textwidth=7in
\hoffset -.8in
\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\La{\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}}
\def\Est{E_1^{\star}}
\def\cN{{\cal N}}
\def\whp{{\bf whp}}
\def\whps{{\bf whp }}

\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 $}}}
\newcommand{\ssm}{\mbox{$\setminus$}}
\newcommand{\nlln}{\mbox{$n \frac{ \log \log n}{\log n}$}}
\newcommand{\SMALL}{\mbox{SMALL}}
\newcommand{\LARG}{\mbox{LARGE}}
\newcommand{\bfrac}[2]{\left( \frac{#1}{#2} \right)}

\begin{document}

\baselineskip 20pt \lineskip 3pt

\title{Multicoloured Hamilton cycles in random graphs; an anti-Ramsey
threshold.}
\author{Colin Cooper \\ School of Mathematical Sciences, \\
University of North London,\\ London N7 8DB, U.K. 
\thanks{Research carried out whilst visiting Carnegie Mellon University} 
\and 
Alan Frieze \\Department of Mathematics,\\Carnegie Mellon University,\\
Pittsburgh PA15213, U.S.A.\thanks{ Supported by NSF grant CCR-9225008}\\}
\date{}
\maketitle
\begin{center}
Submitted: August 25, 1995; Accepted October 1, 1995
\end{center}
\vspace{.7in}
\begin{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$-{\em bounded
colouring}. We say that a subset of the edges of $G$ is {\em multicoloured}
if each edge is of a different colour. We say that the colouring is 
{\em $\cal H$-good}, if a multicoloured  Hamilton cycle exists i.e., 
one with a multicoloured edge-set. \\
Let ${\cal AR}_k$ = $\{G :$ every $k$-bounded colouring of $G$ is
$\cal H$-good\}. We establish the threshold 
for the random graph $G_{n,m}$ to be in ${\cal AR}_k$. 
\end{abstract}
\vspace{1in}

\section{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\'os and Szemer\'edi \cite{KS}
proved that if
$\l=e^{-c}$ then
\begin{eqnarray*}
\lim_{n \rightarrow \infty}
\Pr ( G_{n,m} \mbox{is Hamiltonian} ) &=& \left\{\begin{array}{ll}
0&c_n\rightarrow -\infty\\
e^{-\l}&c_n\rightarrow c\\
1&c_n\rightarrow \infty
\end{array}\right. ,
\end{eqnarray*}
which is $\lim_{n \rightarrow \infty}
\Pr ( \d(G_{n,m})\geq 2)$, where $\d$ refers to minimum degree.

This result has been generalised in a number of directions. 
Bollob\'as \cite{Bo1} proved a  
hitting time version (see also Ajtai, Koml\'os and Szemer\'edi
\cite{AKS}); Bollob\'as, Fenner and Frieze \cite{BFF1}
proved an algorithmic version; Bollob\'as and Frieze \cite{BF} found the
threshold for $k/2$ edge disjoint Hamilton cycles;
Bollob\'as, Fenner and Frieze \cite{BFF2} found a threshold when there
is a minimum degree condition; Cooper and Frieze 
\cite{CF1}, {\L}uczak \cite{L1} and Cooper \cite{C} discussed pancyclic
versions; Cooper and Frieze \cite{CF2} 
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$-{\em bounded
colouring}. We say that a subset of the edges of $G$ is {\em multicoloured}
if each edge is of a different colour. We say that the colouring is 
{\em $\cal 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 $\cal H$-good.
Hahn and Thomassen \cite{HT}
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 $\cal H$-good.
Finally, Albert, Frieze and Reed \cite{ABF} 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 ${\cal AR}_k$ = $\{G :$ every $k$-bounded colouring of $G$ is
$\cal H$-good\}. We establish the threshold 
for the random graph $G_{n,m}$ to be in ${\cal AR}_k$. 
\begin{theorem}
\label{th1}
If $m= n(\log n + (2k-1) \log \log n + c_n)/2$ and $\l = e^{-c}$, then
\begin{eqnarray}
\lim_{n \rightarrow \infty}
\Pr \left( G_{n,m} \in {\cal AR}_k \right) &=& \left\{\begin{array}{ll}
0&c_n\rightarrow -\infty\\
\sum_{i=0}^{k-1} \frac{e^{-\l}\l^i}{i!}&c_n\rightarrow c\\
1&c_n\rightarrow \infty
\end{array}\right.\label{1}\\
&=&\lim_{n \rightarrow \infty}
\Pr( G_{n,m}\in {\cal B}_k),\nonumber
\end{eqnarray}
where ${\cal B}_k$ = $\{G:$ $G$ has at most $k-1$ vertices of degree
less than $2k$\}.
\end{theorem}
Note that the case $k=1$ generalises the original theorem of Koml\`os
and Szemer\`edi. We use ${\cal AR}_k$ to
denote the {\em 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\"odl and Ruci\'nski \cite{RR}.

\section{Outline of the proof of Theorem \protect{\ref{th1}}}
We will prove the result for the independent model $G_{n,p}$ where
$p=2m/n$ and rely on the monotonicity of property ${\cal AR}_k$
to give the theorem as stated, see Bollob\'as \cite{Bo2} and {\L}uczak
\cite{L2}. With a little more work, one could obtain 
the result  that the hitting times for properties ${\cal AR}_k$ and
${\cal B}_k$ in the graph process are coincidental 
\whp\footnote{with high probability i.e. probability 1-o(1) as
$n\rightarrow\infty$}.

We will follow the basic idea of \cite{FR} that, given a $k$-bounded
colouring we will choose a multicoloured set of edges $E_1\cup E_2$
and  show that \whps $H=(V=[n],E_1\cup 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\'os and Szemer\'edi \cite{AKS} to show that $H$ is
Hamiltonian \whp.
\section{Required graph properties}

We say a vertex $v$ of 
$G=G_{n,p}$ is {\em small} if its degree $d(v)$ satisfies $d(v) < \log n
/10$ and {\em large} otherwise.
Denote the set of small vertices by \SMALL\ and the remaining vertices
by \LARG. For $S\subseteq V$ we let 
$$N_G(S)=N(S)=\{w\not\in S:\;\exists v\in S \mbox{ such that }\{v,w\}\mbox{ is
an edge of }G\}.$$

We now give a rather long list of properties. We claim 
\begin{lemma}
\label{lprop}
If $p=(\log n+(2k-1)\log\log n +c)/n$ then $G_{n,p}$ has properties
P1 -- P9 below \whps and property P10 with probability equal to the RHS
of (\ref{1}). 
\end{lemma}
\begin{description}
\item[P1] $|\SMALL|\leq n^{1/3}$.
\item[P2] $\SMALL$ contains no edges.
\item[P3] No $v\in V$ is within distance 2 of more than one small vertex.
\item[P4] $S\subseteq \LARG,\,|S|\leq n/\log n$ implies that $|N(S)|\geq
|S|\log n/20$.
\item[P5] $T\subseteq V,\,|T|\leq n/(\log n)^2$ implies $T$ contains at
most 3$|T|$ edges. 
\item[P6] $A,B\subseteq V,\,A\cap B=\emptyset,\,|A|,|B|\geq 15n\log\log
n/\log n$ implies $G$ contains at least
$|A||B|\log n/2n$ edges joining $A$ and $B$.
\item[P7] $A,B\subseteq V,\,A\cap B=\emptyset,|A|\leq |B|\leq 2|A|$ and
$|B|\leq Dn\log\log n/\log n$ ($D\geq 1$) implies
that there are at most $10D|A|\log\log n$ edges joining $A$ and $B$.
\item[P8] If $|A|\leq Dn\log\log n/\log n$ ($D\geq 1$) then $A$ contains
at most $10D|A|\log\log n$ edges.
\item[P9] $G$ has minimum degree at least $2k-1$.
\item[P10] $G$ has at most $k-1$ vertices of degree $2k-1$.
\end{description}
The proof that $G_{n,p}$ has properties P1--P4 \whps can be carried out
as in \cite{BFF1}. Erd\H{o}s and R\'enyi \cite{ER} contains
our claim about P9, P10. The remaining claims are simple first moment
calculations and are placed in the appendix.

\section{A simple necessary condition}
\label{simple}
We now show the relevance of P9, P10. Suppose a graph $G$ has $k$
vertices $v_1,v_2,\ldots,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\leq i\leq k-1$. Now use colours $2,4,6,\ldots,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,\ldots,2k-2$ for its edges
incident with $v_1,v_2,\ldots,v_{k-1}$ and then
there is only one colour left for the edges incident with vertex $v_k$.

Let $\cN_k$ denote the set of graphs satisfying P1--P10. It follows from
Lemma \ref{lprop} and the above that we can 
complete the proof of Theorem \ref{th1} by proving 
\begin{equation}
\label{eqm}
\cN_k\subseteq {\cal AR}_k.
\end{equation}

\section{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
$\mu = np$ then 
\begin{eqnarray}
\Pr(X \le \a \mu ) &\le& \left( \frac{e}{\a} \right)^{\a\mu} e^{-\mu}
\;\;\;\;\;\;\; 0 < \a \le 1\label{chlt}\\
\Pr(X \ge \a \mu ) &\le& \left( \frac{e}{\a} \right)^{\a\mu} e^{-\mu}
\;\;\;\;\;\;\; 1 \le \a.\label{chgt}
\end{eqnarray}

\section{Main Proof}
Assume from now on that we have a {\em fixed} graph $G=(V,E)\in \cN_k$.
We randomly 
select a multicoloured subgraph $H$ of $G$, $H=(V,E_1\cup 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\cup E_2$ and {\em not} the choice of $G=G_{n,p}$.
\subsection{Construction of the multicoloured subgraph $H$}
The
sets $E_1$ and $E_2$ are obtained as follows.

\subsubsection{Selection of $E_1$}
\begin{description}
\item[(i)] Choose edges of the subgraph of $G$ induced by 
\LARG\ independently with probability $\e/k,\;
\e = e^{-200k}$, to obtain $\widetilde{E}_1$.
\item[(ii)] Remove from $\widetilde{E}_1$ all edges whose colour 
occurs more than once in $\widetilde{E}_1$ and
also edges whose colour is the same as that of any edge incident with a
small vertex.

\end{description}
Denote the edge set chosen by $E_1$, and denote by $\Est$ the subset of
edges of $E$
which have the same colour as that of an edge in $E_1$.
\begin{lemma}
For $v\in \LARG$ let $d'(v)$ denote the degree of $v$ in
$(V,E\ssm\Est)$. Then \whp
$$d'(v) > {9 \over 100k}\log n,$$
for all $v\in \LARG$.
\end{lemma}
\proofstart
Suppose that large vertex $v$ has edges of $r=r(v)$ different colours
$c_1,c_2,\ldots,c_r$ incident with it in $G$, where $d(v)/k \le r \le d(v)$. 
Let $X_i,\,1\leq i\leq 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 $\ell_i$
denote the number of edges of colour $c_i$ which are incident with
$v$. Then
\begin{eqnarray*}
\Pr(X_i=1)&\leq&\ell_i {\e\over k}  \left(1-{\e\over k}\right)^{k_i-1}\\
&\leq&\e.
\end{eqnarray*}
The random variables $X_1,X_2,\ldots,X_r$ are independent and so
$X=X_1+X_2+\cdots+X_r$ is dominated by $Bin(r,\e)$. Thus, by
(\ref{chgt}),
\begin{eqnarray*}
\Pr\left(X \ge {r \over 10} \right) &\le& (10 e \e )^{r \over 10} \\ 
&\le&(10e\e)^{\log n \over 100k} \\
&\le& n^{-3/2},
\end{eqnarray*}
when $\e = e^{-200k}$.
Hence \whp, 
$$d'(v) > {9 \over 10} r\ge {9 \over 100k} \log n$$
for every $v\in \LARG$.
\proofend

Assume then that 
$$d'(v)  > {9 \over 100k} \log n$$ 
for $v\in \LARG$.

\subsubsection{Selection of $E_2$}

We show we can choose a monochromatic subset $E_2$ of $E\setminus E_1^*$
in which
\begin{description}
\item[D1] The vertices of \SMALL\ have degree at least 2,
\item[D2] The vertices of \LARG\ have degree at least $\rdown{{9 \over
200k^2}\log n}$.
\end{description}

In order to select $E_2$,  we first describe how to choose for 
each vertex $v\in V$, a 
subset $A_v$ of the edges of
$E\ssm \Est$ incident with $v$. These sets $A_v,\,v\in 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= \rdown{d(v)/k}$.

The subgraph $F$ of $E \ssm \Est$ induced by \LARG, is of minimum
degree greater than
$(9 \log n)/100k$. We orient $F$ so that $|d^-(v)-d^+(v)|\le 1$ for
all $v \in $ \LARG. We now choose a subset
$A_v$ of edges directed outward from $v$ by this orientation,
of size $\rdown{(9 \log n)/200k^2} \; k$.

The following lemma, applied to the sets $A_v$ defined above, 
gives the required monochromatic set $E_2$. 

\begin{lemma}
\label{hall}
Let $A_1,A_2,\ldots,A_n$ be disjoint sets with $|A_i|=2k-1,\,1\leq i\leq
r\leq k-1$ and 
$|A_i|=m_ik,\,r+1\leq i\leq n$, where the $m_i$'s are positive 
integers. Let $A=A_1\cup A_2\cup \cdots \cup 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\cap
B|=2,\,1\leq i\leq r$ and $|A_i\cap B|=m_i,\,r+1\leq i\leq n$.
\end{lemma}
\proofstart
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 $\G$ with bipartition $(X,Y)$,
where $(x,y)$ is an edge of $\G$ if colour $y \in Y$ was used on the 
elements of $x \in X$.

We claim that $\G$ contains an $X$-saturated matching. Let $S \subseteq
X,\;|S|=s$,
and suppose $t$ elements of $S$
are sets of size $k-1$ and $s-t$ are of size $k$. We have
\begin{eqnarray*}
|\bigcup_{B_{i,j}\in S} B_{i,j}| &=& (s-t)k + t(k-1) \\
&=& sk-t.
\end{eqnarray*}
Thus the set of neighbours $N_{\G}(S)$ of $S$ in $\G$ satisfies
\[
|N_{\G}(S)| \ge \rdup{s- \frac{t}{k}} \ge \rdup{s-(\frac{k-1}{k})} = |S|, 
\]
and $\G$ 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)$.

\proofend

\subsection{Properties of $H=(V,E_1\cup E_2)$ }
We first state or prove some basic properties of $H$.

\begin{lemma}
 $H$ is multicoloured, and $\d(H) \ge 2$.
\end{lemma}

\begin{lemma}
\label{fluffy}     ~
With high probability
\begin{description}
\item[D3] $S \subseteq \LARG,\; |S| \le {n \over 100 \log n}
\Longrightarrow |N_H(S)|
\ge {\e \log n \over
300 k^2}|S|.$
\end{description}
\end{lemma}
\proofstart

{\em Case of }$|S| \le n/(\log n)^3$

If $S \subseteq \LARG$, then
$T=N_H(S) \cup S$ contains at least $\rdown{{9 \over 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|\geq \rdown{{9 \over 200k^2} \log n} |S|/6$ and so
$$|N_H(S)| \ge {3 \over 500 k^2}\log n |S|.$$

{\em Case of} $n/(\log n)^3 < |S| \le n/100\log n$

By P4, $G$ satisfies
$|N(S)| \ge (|S|\log n)/20 $ and we can choose a set $M$ of
\[ \rdown{(|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 $\rho$ that an edge of $M$ of colour $i$ is included in
$E_1$ satisfies
\begin{equation}
\label{col}
\rho \geq {t \e \over k}\left(1-{\e \over k}\right)^{r-1} \ge {t \e
\over k}(1-\e) >
{\e \over 2k}.
\end{equation}
Thus $|N_H(S)|$ dominates
$Bin({|M| \over k},{\e \over 2k})$,
and by (\ref{chlt})
$$\Pr \left( |N_H(S)| \le {|M|\e \over 4k^2} \right) \le \left({2 \over
e}\right)^{|M|\e/4k^2}.$$
Hence the probability
that some set has less than the required number of neighbours
to its neighbour set is
\begin{eqnarray*}
\sum_{s=n/(\log n)^3}^{n/(100\log n)}{n \choose s} \left({2 \over
e}\right)^{(\e s \log n) /100 k^2} &\le& 
\sum_{s}\left[ \exp - \left\{ \frac{\e \log(e/2)}{100k^2}\log n - 4 \log
\log n 
\right\}\right]^s\\
&=&o(1).
\end{eqnarray*}

\proofend

\begin{lemma}
\label{prop}
Let $D\geq{32 k^2 \over \e}$; 
if $|A|,|B| \ge D\nlln$
then \whps 
\begin{description}
\item[D4] $H$ contains more than $\rdown{{2 \over D}|A|\;|B| {\log n
\over n}}$ edges
between $A$ and $B$.
\end{description}
\end{lemma}
\proofstart
The proof follows that of Lemma \ref{fluffy}. 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 = \rdown{(|A||B|\log n /2n)-(k|\SMALL|\log n)/10}$. Thus the
number of $E_1$-edges between these sets
dominates $Bin(M/k,\e/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 $\rdown{{2
\over D}|A|\;|B| {\log n \over n}}$
$E_1$-edges between them
is (by (\ref{chlt})) at most
\begin{eqnarray}
\sum_{a,b}{n \choose a}{n \choose b} 
\left(\frac{(4e)^{1 \over 4}}{e}\right)^{(1-o(1))\frac{M \e }{2k^2}} &\le& 
\sum_{a,b}\left(\frac{ne}{a}\right)^a \left(\frac{ne}{b}\right)^b
e^{-Kab}\label{long}\\
&\le&\sum_{a,b}\exp \{ (a+b) \log \log n -Kab \}\nonumber\\
&\le&\sum_{a,b}\exp \left\{ ab\left(\left({1 \over a}+{1 \over b}\right)
\log \log n -K \right)\right\}\nonumber\\
&\le&\sum_{a,b} \exp\left\{ab\left( {2 \log n \over Dn}-{3\log n
\over Dn }\right)\right\}\nonumber\\
&\le&n^2 \exp\left\{-Dn{(\log\log n)^2 \over \log n} \right\}\nonumber\\
&=&o(1).\nonumber
\end{eqnarray}
\proofend

Assume from now on that $H$ satisfies D1--D4.
We note the following immediate Corollary.
\begin{corollary}
\whp\ $H$ is connected.
\end{corollary}
\proofstart
If $H$ is not connected then from D4
its has a component $C$ of size at most $D\nlln$. But then D3 and P3
imply $C\cap \LARG =\emptyset$.
Now apply D1 and P2 to get a contradiction.  
\proofend

\section{Proof that $H$ is Hamiltonian}
\label{proof}
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.

\subsection{Construction of an initial long path}
\label{ILP}
We use rotations and extensions 
in $H$ to
find a maximal path with
large rotation endpoint sets, see for example \cite{BFF1}, \cite{KS}. 
Let $P_0=(v_1,v_2,\ldots,v_l)$ be
a path of maximum length in $H$. If $1\leq i<l$ and $\{v_l,v_i\}$ is an
edge of $H$ then 
$P'=(v_1v_2\ldots v_iv_lv_{l-1}\ldots v_{i+1})$ is also of maximum
length. It is called a {\em rotation} of $P_0$
with {\em fixed endpoint} $v_1$ and {\em pivot} $v_i$. Edge
$(v_i,v_{i+1})$ is called the {\em broken} edge of the rotation. 
We can then, in general, rotate $P'$ to get more maximum length
paths. 

Let 
$S_t=\{v\in \LARG : \;v\neq 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\neq \emptyset$. It then follows that if $|S_t|\leq
n/(100\log n)$
then $|S_{t+1}| \ge \e \log n |S_t|/(1000k^2)$,
for making this inductive
assumption which is true for $|S_1|$ by D2,
\begin{eqnarray*}
|S_{t+1}|&\geq&|N_H(S_t)|/2- (1+|S_1|+|S_2|+\cdots |S_t|)\\
&\geq&\e \log n |S_t|/(600k^2)- (1+|S_1|+|S_2|+\cdots |S_t|)\\
&\geq&\e \log n |S_t|/(1000k^2).
\end{eqnarray*}
Thus there exists $t_0\leq (1+o(1))\log n/\log\log n$ such that
$|S_{t_0}|\geq cn,\,c=\e/(10^6k^2)$.
Let
$B(v_1)=S_{t_0}$ and $A_0=B(v_1)\cup \{v_1\}$. Similarly, for each $v\in
B(v_1)$ we can construct a set of endpoints $B(v),\,|B(v)|\geq cn$ of
endpoints
of maximum length paths with endpoint $v$. Note that $l \geq cn$ as every
vertex of $B_0$ lies  on $P_0$.

In summary, for each $a\in A_0,\,b\in 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.

\subsection{Closure of the maximal path}
This section follows closely both the notation and the proof methodology
used in \cite{AKS}.

Given path $P_0$ and a set of vertices $S$ of $P_0$, we say $s \in S$ is
an {\em 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)$.
\begin{lemma}
\label{AKSL}
Given a set $S$ of vertices with $|int(S)| \ge
7D\nlln,\,D\geq 32 k^2/ \e$ there is a subset $S'
\subseteq S$ such
that, for all $s'\in
S'$ there are at least $m = {1 \over D}{\log n \over n}
|int(S)|$ edges between $s'$ and $int(S')$. Moreover, $|int(S')| \ge
|int(S)|/2$.
\end{lemma} 
\proofstart
We use the proof given in \cite{AKS}. If there is a $s_1 \in 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 \ssm \{s_1\}$.
If possible we
repeat this procedure for $S_1$, to define
$S_2 = S_1 \ssm \{s_2\}$ (etc). If this continued for $r = \rdown{{1 \over 6}
|int(S)|}$ 
steps, we would have a set $S_r$ and a set
$R=
\{s_1,s_2,\ldots,s_r\}$, with 
$$|int(S_r)| \ge |int(S)|-3|R| \ge
|int(S)|-3r \geq {|int(S)| \over 2} .$$
This step  follows because deleting a vertex of $S$ removes at most $3$
vertices of $int(S)$.
However, there are fewer than
\begin{eqnarray*}
m|S| &\leq& {1 \over D} {\log n \over n} |int(S)|\;|R| \\
&\le& {2 \over D}{\log n \over n} |int(S_r)| \; |R|,
\end{eqnarray*}
edges from $R$ to $int(S_r)$, which contradicts our assumption D4.
\proofend

In  Section \ref{ILP} we proved the existence of maximum
length paths $P(a,b), \; b \in
B(a), \; a \in A_0$ where $|A_0|,\;|B(a)| \ge cn$. Thus there
are at least $c^2n^2$ distinct endpoint pairs $(a,b)$ and for each such
pair there is a path $P(a,b)$ derived from at 
most $\r=(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\r$ segments $I_1,I_2,\ldots,I_{2\r}$ of
length at least $\rdown{|P_0|/2\r}$, where
$|P_0|\ge cn$.
As each $P(a,b)$ is obtained from $P_0$ by at most $\r$ rotations, the  
number of segments of $P_0$ which occur on this path,
although perhaps reversed, 
is at least $\r$. We say that such a segment is {\em 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
$\s=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
$\s$ also specifies the relative orientation of
each segment.
We call such a sequence $\s$ a {\em $t$-sequence},
and say $P(a,b)$ {\em contains} $\s$.

For given $\s$, we consider the  set $L=L(\s)$ of
ordered pairs $(a,b)$, $a\in A_0, \; b\in B(a)$  which 
contain the sequence $\s$.

The total number of such sequences of length $t$ is  $(2\r)_t2^t$. Any path
$P(a,b)$ contains at least $\r \geq \log n/\log \log n$
unbroken segments, and thus
at least $\r
\choose t$ $t$-sequences. The average, over $t$-sequences, of the
number of pairs containing a given $t$-sequence is therefore at least
\[
{c^2n^2{{\r} \choose t} \over (2\r)_t 2^t} \ge \a n^2,
\]
where $\a= c^2 /(4t)^t$. Thus there is a $t$-sequence $\s_0$ and a set
$L= L(\s_0),\,|L|\geq \a n^2$ of pairs $(a,b)$
such that  for each $(a,b)\in L$ the path $P(a,b)$ contains $\s_0$.
Let $\hat{A}=\{a:\;L$ contains
at least $\a n/2$ pairs with $a$ as first element\}. Then $|\hat{A}|\geq
\a n/2$. 
For each $a\in \hat{A}$ let $\hat{B}(a)=\{b:\;(a,b)\in L\}$. 

Let $t = {1700 D^2 / c},\,D=32k^2/\e$ and let $C_1$ denote the union of
the first 
$t/2$ segments of $\s_0$,  in the fixed order and with the fixed relative 
orientation in which they occur along {\em any } of the
paths $P(a,b),\,(a,b)\in L$. 
Let $C_2$ denote the union of the second
$t/2$ segments of $\s_0$. $C_1$ and $C_2$ contain at least ${t \over 2}
\; cn \; {\log \log n \over 4 \log n
}(1-o(1))$ interior points
which from Lemma \ref{AKSL} gives sets $C_1',C_2'$ with at least 
\[
{t c (1-o(1)) \over 16} \nlln \geq 100 D^2 \nlln \]
interior points.

It follows from D4 that there exists $\hat{a}\in \hat{A}$ such that $H$
contains an edge from $\hat{a}$ to $C_1'$. 
Similarly, $H$ contains an edge joining some $\hat{b}\in
\hat{B}(\hat{a})$ to $C_2'$.
Let $x$ be some vertex separating $C_1'$ and $C_2'$ along 
$\hat{P}=P(\hat{a},\hat{b})$. 
We now consider the two half paths $P_1,\,P_2$ obtained by splitting
$\hat{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\in C_1':\; v\neq 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\subseteq T_i,\,i=1,2,\ldots$ such that $|U_1|=1$ and
$|U_{i+1}| = 2|U_i|$, as long as $|U_i| \le D\nlln$. Thus
there is an $i^*$ such that $|U_{i^*}| \ge
D \nlln$ and we are done. Note that $T_1\neq \emptyset$ because
$\hat{a}$ 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 \ref{AKSL} there are at least
$100 D \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 $|\bigcup_{j=1}^i U_i| <
2|U_i|$ at most $20D|U_i| \log \log n $ of these edges are contained in
$\bigcup_{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|$.
\section{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 \whps one needs enough edges
so that the following replacements for conditions P9 and P10 hold true.
\begin{description}
\item[P9a] $G$ has minimum degree $k-1$.
\item[P10a] $G$ has at most $k-1$ vertices of degree $k-1$
\end{description}
That these conditions are necessary can be argued as in Section
\ref{simple}, since connectivity and
the existence of a perfect matching require minimum degree one.
Lemma \ref{hall} is replaced by
\begin{lemma}
Let $A_1,A_2,\ldots,A_n$ be disjoint sets with $|A_i|=k-1,\,1\leq i\leq
r\leq k-1$ and 
$|A_i|=m_ik,\,r+1\leq i\leq n$, where the $m_i$'s are positive 
integers. Let $A=A_1\cup A_2\cup \cdots \cup 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\cap
B|=1,\,1\leq i\leq r$ and $|A_i\cap B|=m_i,\,r+1\leq i\leq n$.
\end{lemma}
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 \ref{proof}.
\newpage

\begin{thebibliography}{99}
\bibitem{AKS}
M. Ajtai, J. Koml\'{o}s and E. Szemer\'{e}di. {\em The first occurrence
of Hamilton cycles
in random graphs.} Annals of Discrete Mathematics 27 (1985) 173-178.

\bibitem{ABF} M.J. Albert, A.M. Frieze and B. Reed, {\em Multicoloured
Hamilton Cycles.}
Electronic Journal of Combinatorics 2 (1995) R10.

\bibitem{Bo1} B. Bollob\'{a}s. {\em The evolution of sparse graphs.}
Graph Theory and Combinatorics. (Proc. Cambridge Combinatorics Conference in
Honour of Paul Erd\H{o}s (B. Bollob\'{a}s; Ed)) Academic Press (1984)
35-57
\bibitem{Bo2} B. Bollob\'{a}s. {\em Random Graphs.} Academic Press (1985)
\bibitem{BF} B. Bollob\'{a}s and A.M. Frieze, {\em On matchings and
Hamiltonian cycles in random graphs.}
Annals of Discrete Mathematics 28 (1985) 23-46.

\bibitem{BFF1} B. Bollob\'{a}s, T.I. Fenner and A.M. Frieze. {\em An algorithm
for finding Hamilton cycles in random graphs.} Combinatorica 7 (1987) 327-341.

\bibitem{BFF2} B. Bollob\'{a}s, T. Fenner and A.M. Frieze. {\em Hamilton
cycles in random graphs with minimal degree at least k.}
(A Tribute to Paul Erd\H{o}s (A.Baker, B.Bollobas and A.Hajnal; Ed))
(1990) 59-96.

\bibitem{C} C. Cooper. {\em 1-pancyclic Hamilton cycles in random graphs.} 
Random Structures and Algorithms 3.3 (1992) 277-287
\bibitem{CF1} C. Cooper and A. Frieze. {\em Pancyclic random graphs.} 
Proc. 3rd Annual Conference on Random Graphs, Poznan 1987. Wiley (1990) 29-39

\bibitem{CF2} C. Cooper and A. Frieze. {\em On the lower bound for the
number of Hamilton cycles
in a random graph.} Journal of Graph Theory 13.6 (1989) 719-735

\bibitem{ER} P. Erd\H{o}s and A. R\'{e}nyi. {\em On the strength of
connectedness of a random graph.}
Acta. Math. Acad. Sci. Hungar. 12 (1961) 261-267.

\bibitem{FR} A. Frieze and B. Reed. {\em Polychromatic Hamilton cycles.}
Discrete Maths. 118 (1993) 69-74.

\bibitem{HT} G. Hahn and C. Thomassen. {\em Path and cycle sub-Ramsey numbers,
and an edge colouring conjecture.}
Discrete Maths. 62 (1986) 29-33

\bibitem{KS}  J. Koml\'{o}s and E. Szemer\'{e}di. {\em Limit
distributions for the existence of Hamilton cycles
in a random graph.} Discrete Maths. 43 (1983) 55-63.
\bibitem{L1} T. {\L}uczak. {\em Cycles in random graphs.} Discrete
Maths. (1987)
\bibitem{L2} T. {\L}uczak, {\em On the equivalence of two basic models
of random graph}, Proceedings of Random graphs 87, Wiley, Chichester (1990),
151-159. 
\bibitem{RR} R\"odl and A. Ruci\'{n}ski, {\em Threshold functions for
Ramsey properties.} (to appear)
\bibitem{W} R\"odl and Winkler. Private communication (1984)
\end{thebibliography}
\newpage
\section*{Appendix: Proofs of P6--P8}
{\bf P5} $T\subseteq V,\,|T|\leq n/(\log n)^2$ implies $T$ contains at
most 3$|T|$ edges. 

The number of edges in $T$ is $Bin\left({|T|\choose 2},p\right)$. By
(\ref{chgt})
the probability that there exists $T$ with $3|T|$ edges is at most
\begin{eqnarray*} \sum_{t=7}^{n/(\log n)^2}{n\choose t}\left({e{t\choose
2}p\over 3t}\right)^{3t}e^{-{t\choose 2}p}&\leq&
\sum_t \left({ne\over t}\right)^t\left({(1+o(1))et\log n\over
6n}\right)^{3t}\\
&\leq&\sum_t\left({(\log n)^3t^2\over n^2}\right)^t\\
&=&o(1).
\end{eqnarray*} 
{\bf P6} $A,B\subseteq V,\,A\cap B=\emptyset,\,|A|,|B|\geq 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 (\ref{chlt}),
the probability there exist sets $A,B$ with less than half the expected
number of edges between them, is at most
\begin{eqnarray*}
\sum_{a,b} {n \choose a} {n \choose b} \bfrac{2}{e}^{abp}
&\le& \exp  \left\{ a \log (ne/a) + b \log (ne/b) - abp \log (e/2) \right\}\\
&\le& n^2 \exp \left\{ -\frac{n (\log \log n)^2}{\log n} (15)^2
\left( \log(e/2)-2/15 \right) \right\} \\
&=&o(1),
\end{eqnarray*}
by the same arguments as those following (\ref{long}) in Lemma \ref{prop}.

{\bf P7} 
$A,B\subseteq V,\,A\cap B=\emptyset,|A|\leq |B|\leq 2|A|$ and
$|B|\leq Dn\log\log n/\log n$ ($D\geq 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 
\begin{eqnarray*}
\sum_a{n \choose a}{n \choose 2a} {2a^2 \choose 10Da \log \log n}
p^{10Da \log \log n} &\le&
\sum_a\left[  \bfrac{ne}{a} \bfrac{ne}{2a}^2 \bfrac{ae \log n}{5Dn \log
\log n}^{
10D \log \log n} \right]^a \\
&\le& \sum_a\left[ \frac{e^3}{4} \bfrac{\log n}{2 D \log \log n}^3
\bfrac{e}{5}^{
10D \log \log n} \right]^a \\
&\le & \sum_a\bfrac{1}{\log n}^a\\
&=&o(1).
\end{eqnarray*}

{\bf P8} If $|A|\leq Dn\log\log n/\log n$ ($D\geq 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\left({|A| \choose 2},p\right)$. By (\ref{chgt}) the probability there
exists a set $A$ with at least $20 (1-o(1))$ times the expected
number of edges is at most,
\begin{eqnarray*}
\sum_a {n \choose a} \bfrac{e}{19}^{10D a \log \log n} &\le&
\sum_an \exp \left\{ a \log (ne/a) - 10D a \log \log n \log (19/e) \right\}\\
&\le&\sum_an \exp \left\{- \frac{D n \log \log n}{(\log n)^2} 
\left( 10 \log (19/e)-2 \right) \right\}\\
&=&o(1).
\end{eqnarray*}
\end{document}





.