\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 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}