\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P44}{19(4)}{2012}

\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}


\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{prob}[thm]{Problem}
\newtheorem{claim}[thm]{Claim}

% remarks
\theoremstyle{remark}
\newtheorem{rem}[thm]{Remark}

\newcommand{\E}{\mathbb{E}}
\newcommand{\Var}{{Var\;}}
\newcommand{\Det}{\mbox{Det}}
\newcommand{\whp}{{\bf whp}}
\newcommand{\aas}{{\it a.a.s.}}
\newcommand{\G}{\Gamma} 
\newcommand{\cP}{{\cal P}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\ka}{\kappa}
\newcommand{\La}{\Lambda}
\newcommand{\la}{\lambda}
\newcommand{\threeuniformhg}[2]{H^{(3)}_{#1,#2}} 
%Command for 3-uniform hypergraph symbol, with order and probability as arguments.
\newcommand{\hg}[2]{\threeuniformhg{#1}{#2}} 
%\hg{<order>}{<probability>}
\newcommand{\gbar}{\overline{G}}
\newcommand{\kuniformhg}[2]{H^{(k)}_{#1,#2}} 
%Command for k-uniform hypergraph symbol, with order and probability as arguments.
\newcommand{\hgk}[2]{\kuniformhg{#1}{#2}} 
%\hgk{<order>}{<probability>}


\title{\bf Optimal divisibility conditions for loose Hamilton cycles in random hypergraphs}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address 

\author{Andrzej Dudek\thanks{Supported in part by Simons Foundation Grant \#244712 and WMU Support for Faculty Scholars Award.}\\
\small Department of Mathematics\\[-0.8ex]
\small Western Michigan University\\[-0.8ex] 
\small Kalamazoo, MI, USA\\
\small\tt andrzej.dudek@wmich.edu\\
\and
Alan Frieze\thanks{Supported in part by NSF Grant CCF1013110.}\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Carnegie Mellon University\\[-0.8ex]
\small Pittsburgh, PA, USA\\
\small\tt alan@random.math.cmu.edu\\
\and
Po-Shen Loh\thanks{Supported in part by an NSA Young Investigators Grant and a USA-Israel BSF grant.}\\
\small Department of Mathematical Sciences\\[-0.8ex]
\small Carnegie Mellon University\\[-0.8ex]
\small Pittsburgh, PA, USA\\
\small\tt ploh@cmu.edu
\and
Shelley Speiss\\
\small Department of Mathematics\\[-0.8ex]
\small Western Michigan University\\[-0.8ex] 
\small Kalamazoo, MI, USA\\
\small\tt shelley.k.speiss@wmich.edu
}

\date{\dateline{Jul 7, 2012}{Nov 28, 2012}{Dec 13, 2012}\\
\small Mathematics Subject Classifications: 05C80, 05C65}

\begin{document}

\maketitle

\begin{abstract}
In the random $k$-uniform hypergraph $\hgk{n}{p}$ of order~$n$, each possible $k$-tuple appears independently with 
probability~$p$. A loose Hamilton cycle is a cycle of order~$n$ in which
every pair of consecutive edges 
intersects in a single vertex. It was shown by Frieze that if $p\geq c(\log n)/n^2$ for some absolute constant $c>0$, 
then \aas\ $\hg{n}{p}$ contains a loose Hamilton cycle, provided that $n$ is divisible by $4$. Subsequently, 
Dudek and Frieze extended this result for any uniformity $k\ge 4$, proving that if $p\gg (\log n)/n^{k-1}$, 
then $\hgk{n}{p}$ contains a loose Hamilton cycle, provided that $n$ is divisible by $2(k-1)$. 
In this paper, we improve the divisibility requirement and show that in the above results it is enough to 
assume that $n$ is a multiple of $k-1$, which is best possible.
\end{abstract}

%%%%%%%%%%%%%%%
%%% NEW SECTION  %%%
%%%%%%%%%%%%%%%

\section{Introduction}

Let $G_{n,p}$ be the binomial random graph of order~$n$ in which every
possible edge appears independently with 
probability~$p$.
The problem of determining the threshold for the existence of Hamilton cycles in the random graph $G_{n,p}$ was 
originally raised by Erd\H{o}s and R\'enyi~\cite{ErdosRenyi60} in 1960 and has since been extensively studied 
by many researchers including Ajtai, Bollob{\'a}s, Koml{\'o}s, Kor\u{s}unov, P{\'o}sa, and Szemer{\'e}di 
\cite{AKS, Bol84, KS75, KS83, Korshunov83, Posa76}. Recall an event $E_n$ occurs {\em asymptotically almost surely}, 
or \aas\ for brevity, if $\lim_{n\to\infty}\Pr(E_n)=1$.  The culmination of this research led to one of the most celebrated 
results in the theory of random graphs, which states that if $p=(\log n + \log\log n +\omega(n))/n$, where $\omega(n)$ 
is an arbitrarily slowly growing function, then $G_{n,p}$ is \aas\ Hamiltonian~\cite{AKS, Bol84,Korshunov83}.  Therefore the threshold behavior for the 
existence of Hamiltonian cycles in random graphs is well understood, and naturally raises the question of the existence 
of Hamiltonian cycles in random $k$-uniform hypergraphs.  

A {\em $k$-uniform hypergraph} is a pair $(V,\mathcal{E})$, where $V$ is the set of vertices and  
$\mathcal{E}\subseteq \binom{V}{k}$ is the set of hyperedges. In the random $k$-uniform hypergraph $\hgk{n}{p}$ 
of order~$n$, each possible $k$-tuple appears independently with probability~$p$. (Hence, $G_{n,p}=H_{n,p}^{(2)}$.)  
A {\em loose} Hamilton cycle $C$ in a $k$-uniform hypergraph $H=(V,\mathcal{E})$ of order $n$ is a collection 
of edges of $H$ such that for some cyclic ordering of $V$, every edge
consists of $k$ consecutive vertices, and 
for every pair of consecutive edges $E_{i-1},E_i$ in $C$ (in the natural
ordering of the edges), we have 
$|E_{i-1}\cap E_i|=1$. Thus, in every
loose Hamilton cycle the sets $E_i\setminus E_{i-1}$ are a partition 
of $V$ into sets of size $k-1$. Hence, the number of edges of a loose
Hamilton cycle is $n/(k-1)$, 
implying it is a necessary requirement that $k-1$ divides $n$ in the study of loose Hamilton cycles 
in $k$-uniform hypergraphs.  

Frieze~\cite{F} and Dudek and Frieze~\cite{DF} managed to obtain the thresholds for the 
existence of loose Hamilton cycles in random $k$-uniform hypergraphs in the case when $n$ is a 
multiple of $2(k-1)$. More precisely, the following was shown.  

\begin{thm}[Frieze~\cite{F}]\label{thm:F}
There exists an absolute constant $c>0$ such that if $p\geq c(\log n)/n^2$ then
$$
\lim_{\substack{n\to \infty\\4 | n}}\Pr\left(\hg{n}{p}\ contains\ a\ loose\ Hamilton\ cycle\right)=1.
$$
\end{thm}

\begin{thm}[Dudek and Frieze~\cite{DF}]\label{thm:DF}
Suppose $k\geq 4$.  If $p n^{k-1} / \log n$ tends to infinity, then
$$
\lim_{\substack{n\to \infty\\2(k-1) | n}}\Pr\left(\hgk{n}{p}\ contains\ a\ loose\ Hamilton\ cycle\right)=1.
$$
\end{thm}

For Theorem~\ref{thm:F}, Frieze showed one could randomly generate an edge-colored regular 
graph based on the structure of the hypergraph by using results about perfect matchings 
on specific types of hypergraphs studied by Johansson, Kahn and Vu~\cite{JKV}.  He observed 
that a {\em rainbow} Hamilton cycle in this graph is equivalent to a loose Hamilton cycle in the 
original hypergraph (where a rainbow Hamilton cycle is a Hamilton cycle such that every edge receives a 
different color).  Using a contiguity result and a known result about the existence of rainbow 
Hamilton cycles in random regular graphs, he was able to finish the proof.  In their generalization, 
Dudek and Frieze again used perfect matchings, but focused on randomly
generating sub-hypergraphs 
as opposed to randomly generating edge-colored regular graphs.  They were able to model these newly obtained 
sub-hypergraphs via the configuration model and with this model show that
these types of hypergraphs 
will contain \aas\  a loose Hamilton cycle. In both cases, one has to assume that the order of the 
hypergraph, $n$, is a multiplicity of $2(k-1)$. This restriction is an artifact of the proofs.

This paper completes these results by handling the remaining case 
$n\equiv(k-1)\!\!\mod 2(k-1)$.  We do this by viewing $\hgk{n}{p}$ as a subgraph of 
$\hgk{n+(k-1)}{p}$, and extending the techniques from~\cite{DF,F}.  
Roughly speaking, we are now looking for loose cycles that contain all the
vertices except for the 
$k-1$ that were added to expand the vertex set.  
We obtain the following refined conclusions.

\begin{thm}\label{thm:main_3}
There exists an absolute constant $c>0$ such that if $p\geq c(\log n)/n^2$ then
$$
\lim_{\substack{n\to \infty\\2 | n}}\Pr(\hg{n}{p}\ contains\ a\ loose\ Hamilton\ cycle)=1.
$$
\end{thm}

\begin{thm}\label{thm:main_k}
Suppose $k\geq 4$.  If $p n^{k-1} / \log n$ tends to infinity, then
$$
\lim_{\substack{n\to \infty\\(k-1) | n}}\Pr(\hgk{n}{p}\ contains\ a\ loose\ Hamilton\ cycle)=1.
$$
\end{thm}

%%%%%%%%%%%%%%%
%%% NEW SECTION  %%%
%%%%%%%%%%%%%%%
\section{Proof of Theorem~\ref{thm:main_3}}

\subsection{Auxiliary results}

We start with an analogue of the theorem from Johansson, Kahn and Vu~\cite{JKV}. Let $X$ and $Y$ be disjoint sets.
Let $\G=\G(X,Y,p)$ be the random $3$-uniform hypergraph
such that each $3$-edge in $\binom{X}{2}\times \binom{Y}{1}$ is independently
included with probability $p$.
Assuming that $|X|=2N$ and $|Y|=N$ for some positive integer $N$,
a \textit{perfect matching} of $\G$ is a set of $N$ $3$-edges
$\{u_{2i-1},u_{2i},w_{i}\}$, $1\le i\le N$,
such that $\set{u_1,\ldots,u_{2N}}=X$ and $\set{w_{1},\ldots,w_{N}}=Y$.
\begin{thm}[Johansson, Kahn and Vu~\cite{JKV}]\label{th2}
There exists an absolute constant $c>0$ such that if $p\ge c(\log N)/N^{2}$ then
\aas\ $\G$ contains a perfect matching.
\end{thm}
This version is not actually proved in \cite{JKV}, but can be obtained by straightforward changes to their proof.
For an even integer $d$ let $G_{n,d}$ be a random $d$-regular loopless multigraph of order~$n$. 
The proof of Theorem~\ref{thm:F} 
was based on the following 
result.  Here, a \emph{rainbow}\/ cycle is one in which every edge has a
distinct color.  It is not required that every possible color appear in the cycle.
\begin{thm}[Janson and Wormald~\cite{JW}]
If the edges of $G_{n,d}$ are colored randomly with
$n$ colors so that each color is used exactly $d/2$ times, $d$ is even and at least 8, then 
\aas\ it contains a rainbow Hamilton
cycle. 
\end{thm}
Here we extend this result. A proof is given in Section~\ref{sec:rainbow}.
\begin{thm}\label{thm:rainbow}
Let $G_{n,d}$ be colored randomly with $n$ colors so that each color is used exactly $d/2$ times. 
Fix a vertex $v$ and a color $c$.
Then there exists a positive integer $d_0$ such that if $d$ is even and at least $d_0$, 
then \aas\ $G_{n,d}$ contains a rainbow $(n-1)$-cycle that avoids vertex $v$ and color $c$.
\end{thm}

We will also use a contiguity result. Let $\gbar_{n,d}$ be the union of $d$ perfect matchings on $\{1,2,\ldots,n\}$, 
chosen independently and uniformly at random.
\begin{thm}[Janson \cite{J}; Molloy, Robalewska, Robinson and Wormald~\cite{MRRW}]\label{th4}
$\gbar_{n,d}$ is {\em contiguous} to $G_{n,d}$.
\end{thm}
By this we mean that if $\cP_n$ is some sequence of (multi)graph properties, then
\begin{equation*}
\gbar_{n,d}\in\cP_n\ \aas\ \Longleftrightarrow\ G_{n,d}\in\cP_n\ \aas
\end{equation*}


\subsection{Main part of the proof}

If $n=4m+2$ (for some positive integer $m$) then we may view $\hg{n}{p}$ as a subgraph of 
$\hg{n+2}{p}$, where in the latter random hypergraph, the vertex set is defined to be $[n]\cup\{v,c\}$.  
The goal will be to construct the graph $\gbar_{2m+2,d}$ with vertex set $[2m+1]\cup\{v\}$ 
that is randomly colored with the colors $[2m+2,n]\cup\{c\}$ using each color exactly $d/2$ times.  To obtain 
Theorem~\ref{thm:main_3}, we use the following observation: if $\gbar_{2m+2,d}$ contains a rainbow 
$(2m+1)$-cycle that avoids the vertex $v$ and the color $c$, then $\hg{n+2}{p}$ contains a loose $(4m+2)$-cycle 
avoiding the vertices $v$ and $c$ (every triple consists of an edge from $\gbar_{2m+2,d}$ and its color).  This in 
turn defines a loose Hamiltonian cycle of $\hg{n}{p}$, which will finish the proof of Theorem~\ref{thm:main_3}.

Recall that $n=4m+2$ for some positive integer $m$.  Let $d$ be an even positive integer that is at least $d_0$, where $d_0$ comes from Theorem~\ref{thm:rainbow}.
Consider $H=\hg{n}{p}$.  By adding two new vertices $v$ and $c$, we can view $H$ as a subgraph of 
$\hg{n+2}{p}$ (with vertex set $[n]\cup\{v,c\}$).  Furthermore note $n+2=4(m+1)$.  Partition 
(deterministically) the set $[n+2]$ = $[4m+4]$ into two sets, $X=[2m+1]\cup\{v\}$ and $Y=[2m+2,n]\cup\{c\}$.  
Clearly $|X|=|Y|=2(m+1)$.

To define a suitable $\gbar_{2m+2,d}$ and coloring thereof, we will use the following observation: with the 
given probability $p$, we can define $p_1$ by $p=1-(1-p_1)^{d}$ and also $p_2$ by $p_1=1-(1-p_2)^{d/2}$. 
Note that $p_1,p_2$ will be of the same order of magnitude as $p$. Using $p_1$ and $p_2$, we can 
express $\hg{n+2}{p}$ as the union of $d$ independent copies of $\hg{n+2}{p_1}$ and furthermore 
express $\hg{n+2}{p_1}$ as the union of $d/2$ independent copies of $\hg{n+2}{p_2}$. Denote by 
$H_{j,1},H_{j,2},\dots,H_{j,d/2}$ the $d/2$ independent copies of $\hg{n+2}{p_2}$ that generate the 
$j^{th}$ copy of $\hg{n+2}{p_1}$. 

Next define the multiset $\mathcal{Y}$ of size $d(m+1)$ that consists of $d/2$ copies of each 
element $y\in Y$ (denoted by $y_1,y_2,\dots,y_{d/2}$).  Let $Y_1,Y_2,\dots,Y_{d}$ be a partition of 
$\mathcal{Y}$ into $d$ (multi)sets of size $m+1$ chosen uniformly at random.  We use each set $Y_j$ 
to associate a sub-hypergraph of the $j^{th}$ copy of $\hg{n+2}{p_1}$ to the hypergraph 
$\G_j=\Gamma(X,Y_j,p_2)$ as follows. 

Define the $3$-uniform hypergraph $\Gamma_j$ on vertex set $X\cup Y_j$ with edge set $E_j$ defined by 
placing $\{x,x',y_i\}\in E_j$ if for some $i$ and $x,x'\in X$ and $y=y_i\in Y_j$ the edge $\{x,x',y\}$ 
is an edge of $H_{j,i}$.  Note that $\Gamma_j$ is distributed as the random graph $\Gamma(X,Y_j,p_2)$.  
By Theorem~\ref{th2} 
(applied with $N=m+1$), each $\Gamma_j$ contains \aas\ a perfect matching $M_j$.  That is, each $M_j$ will 
consist of a set of edges of the form $\{u_{2\ell-1},u_{2\ell},w_{\ell}\}$, $1\leq\ell\leq m+1$, where 
$\{u_{1},\dots,u_{2(m+1)}\}=X$ and $\{w_{1},\dots,w_{m+1}\}=Y_j$.  For each $M_j$, define a colored 
matching $M_j^*$ with vertex set $X$ and edges $\{u_{2\ell-1},u_{2\ell}\}$ colored by $w_{\ell}$ for 
$1\leq\ell\leq m+1$. By symmetry, these matchings are uniformly random and they are independent by 
construction. Thus, $\gbar_{2m+2,d}=\bigcup_{j=1}^{d}{M_j^*}$.

Recall that we added two more vertices, $v$ and $c$, when considering $H$; if we fix $v$ as a vertex of 
$\gbar_{2m+2,d}$ and fix $c$ (used in coloring $\gbar_{2m+2,d}$), it follows from Theorem~\ref{thm:rainbow} (using $2m+2$ 
colors) combined with the contiguity result of Theorem~\ref{th4} that $\gbar_{2m+2,d}$ will contain \aas\ a rainbow 
$(2m+1)$-cycle that avoids $v$ and $c$, completing the proof.


%%%%%%%%%%%%%%%
%%% NEW SECTION  %%%
%%%%%%%%%%%%%%%
\subsection{Proof of Theorem \ref{thm:rainbow}}\label{sec:rainbow}

\subsubsection{Configuration model}\label{subsec:config}
Most of the analysis 
here is based on the configuration model due to Bollob\'as~\cite{B} (see also Section~9.1 in~\cite{JLR}). 
We start with the set $W$ of $dn$ points partitioned into $n$ cells of $d$ points, say $W=W_1\cup W_2\cup\dots\cup W_n$.
We then take a uniformly random pairing of the points into $dn/2$ pairs.
Collapsing each cell to a vertex and regarding each pair as an edge, we obtain a random $d$-regular
multigraph that may also contain loops, denoted by $G_{n,d}^*$. This may be regarded as a {\em projection} 
of the configuration onto the vertex set of $G_{n,d}^*$. Having sampled a random graph $G_{n,d}^*$ we color its edges as follows.

Let $C$ be a union of $n$ disjoint sets of size $d/2$, say
$C=C_1\cup C_2\cup\dots\cup C_{n}$. Clearly, $|C|=dn/2$.
We color every edge of $G_{n,d}^*$ by a color of~$C$
in such a way that the union of all colors gives a partition of~$C$. We choose a coloring of
$G_{n,d}^*$ uniformly among all possibilities.

Set $n=m+1$.
Let $H$ be a random variable which counts the number of rainbow $m$-cycles in $G_{n,d}^*$ that avoid the vertex 
and the color corresponding to $W_{m+1}$ and $C_{m+1}$, respectively. We show that \aas\ $H>0$. Note that since 
$d$ is fixed, Theorem~\ref{thm:rainbow} will follow from this (see, e.g., Theorem 9.9 in \cite{JLR}).

\begin{lem}\label{lem:expectation}
Suppose that $d$ is a positive even integer. Then,
$$
\E(H) \sim  \pi \left(\frac{d-2}{d}\right)^{d+\frac{1}{2}}
\left( (d-1) \left(\frac{d-2}{d}\right)^{d-2} \right)^m.
$$
Hence, $\lim_{m\to\infty} \E(H) = \infty$ for every even $d\ge 8$.
\end{lem}

\begin{lem}\label{lem:variance}
There exists a positive integer $d_0$ such that if $d$ is even and at least $d_0$, then
$$
\frac{\E(H^2)}{\E(H)^2} \sim \sqrt{\frac{d}{d-4}}.
$$
\end{lem}

\subsubsection{Expectation (the proof of Lemma~\ref{lem:expectation})}
Let $a_m$ be the number of possible $m$-cycles on~$W$ avoiding the last cell $W_{m+1}$ (recall that an $m$-cycle connects
$m$ different cells). In a similar manner to (9.2) in~\cite{JLR} we get,
$$
a_m = \frac{(d(d-1))^m}{2m} m!.
$$
Let $p_i$ be the probability that a given set of $i$ disjoint pairs of points of $W$ are
contained in a random configuration. From (9.1) in~\cite{JLR} we get,
$$
p_i = \frac{(d(m+1)-2i-1)!!}{(d(m+1)-1)!!}.
$$
In particular, if $i=m$ then
$$
p_m = \frac{(d(m+1)-2m-1)!!}{(d(m+1)-1)!!}.
$$
Let $q_m$ be the probability that a given $m$-cycle is rainbow and avoids the color corresponding to $C_{m+1}$.
Note the union of colors of any such $m$-cycle contains precisely one element from every $C_i$ for $1\le i\le m$. Thus,
$$
q_m = \frac{|C_1|\cdots|C_{m}|}{\binom{|C|}{m}} = \frac{(d/2)^{m}}{\binom{d(m+1)/2}{m}}.
$$
Consequently,
$$
\E(H) = a_m p_m q_m = \frac{d^{2m}(d-1)^m m! (d(m+1)-2m-1)!!
m!(d(m+1)/2-m)!} {2^{m+1} m (d(m+1)-1)!! (d(m+1)/2)!}.
$$
Using the Stirling formula for $N! \sim \sqrt{2\pi N}\left(\frac{N}{e}\right)^N$ and a corollary $(2N-1)!! 
\sim \sqrt{2}\left(\frac{2N}{e}\right)^{N}$ yields Lemma~\ref{lem:expectation}.

\subsubsection{Variance (the proof of Lemma~\ref{lem:variance})}

Let $r_m(b)$ be the probability that two given $m$-cycles $H_1$ and $H_2$ (which avoid $W_{m+1}$) with
$b = |E(H_1)\cap E(H_2)|$ are rainbow (for $0\le b\le m$) and avoid $C_{m+1}$. Observe that
$$
r_m(b) = q_m \frac{(d/2-1)^{m-b}}{\binom{d(m+1)/2-m}{m-b}},
$$
where the second factor corresponds to the probability that $E(H_2)\setminus E(H_1)$ is rainbow 
conditioning that $H_1$ is rainbow.
Moreover, let $N(b)$ be the number of $m$-cycles that intersect a given $m$-cycle in $b$ edges 
(both of them avoid $W_{m+1}$).
By \cite{JLR} (cf. last equation on page~253), we get
$$
N(b) = \sum_{a=0}^{\min\{b,m-b\}} \frac{am}{b(m-b)}2^{a-1}(d-2)^{m+a-b}(d-3)^{m-a-b}(m-b-1)! \binom{b}{a} \binom{m-b}{a}, 
$$
where for $a=b=0$ we set $\frac{a}{b}=1$.
Thus,
$$
\frac{\E(H^2)}{\E(H)^2} = \frac{1}{\E(H)} + \sum_{b=0}^{m-1} \frac{N(b)p_{2m-b}r_m(b)}{a_mp_m^2q_m^2}.
$$

Using the Stirling formula, one can show (by rather complicated and tedious computations) that 
\begin{align*}
\sum_{b=0}^{m-1} \frac{N(b)p_{2m-b}r_m(b)}{a_mp_m^2q_m^2} \qquad\qquad\\
 \le  \frac{1}{2\pi m} \sum_{b=0}^{m-1} \sum_{a=0}^{\min\{b,m-b\}} & h(a/m,b/m)\exp\{m\cdot g(a/m,b/m)\}\\
 & \times\left( 1+ O\left(\frac{1}{\min\{a,b-a,m-a-b\}+1} \right)\right),
\end{align*}
where
\begin{align*}
g(x,y) &= x\log(2) + (d-2)\log(d) - \log(d - 1) + (6-2d + x - 2y)\log(d - 2) \\
&\qquad+ (1 - x - y) \log(d - 3) + y\log(y) + 3 (1 - y)\log(1 - y) 
- (y - x)\log(y - x) \\
&\qquad-  2 x\log(x) - (1 - x - y)\log(1 - x - y) 
+ (d - 4 + 2y)\log(d - 4 + 2 y)
\end{align*}
and
$$
h(x,y) = \left(\frac{\sqrt{d}}{d-2}\right)^{2d+1} \frac{ (-4 + d + 2 y)^{d+1/2} }{ {\sqrt{y(1-y)(1 - x - y)(y-x)}} }.
$$
We ignore here all cases for which $a=0$, $a=b$ or $a+b=n$ since their contribution
is negligible.

It was shown in \cite{DF} (page 9, line 13 with $\ka=1$) that for $d$ sufficiently large\linebreak $(x_0,y_0) = (2(d-2)/(d(d-1)), 2/d)$ is the unique 
global maximum point of $g(x,y)$ in the domain $S=\{(x,y) : 0< x< y< 1-x\}$. Moreover, it was proved that $g(x,y)$ 
has no asymptote near the boundary of $S$, nor does it approach a limit which is greater than~$0$ (for $d$ large enough). 
Let $D^2{g}$ be the
Hessian matrix of second derivatives. Routine calculations show that
$$
D^2{g}(x,y)=\left(
\begin{array}{c c}
-\frac{2}{x} + \frac{1}{x - y} + \frac{1}{-1 + x + y} & \frac{1}{-x + y} + \frac{1}{-1 + x + y}\\
\frac{1}{-x + y} + \frac{1}{-1 + x + y}           &
\frac{3}{1 - y} + \frac{1}{x - y} + \frac{1}{y} + \frac{1}{-1 + x + y} + \frac{4}{-4 + d + 2 y}\\
\end{array}
\right).
$$
Hence,
$$
D^2{g}(x_0,y_0)=\left(
\begin{array}{c c}
-\frac{(d-1)^2 d}{2 (d-3)} & \frac{(d-4) (d-1)^2 d}{2 (d-2)(d-3)} \\
\frac{(d-4) (d-1)^2 d}{2 (d-2)(d-3)} & -\frac{d(d-4)(-4 + (d-3) (d-2) d)}{2 (d-3) (d-2)^2}
\end{array}
\right).
$$

The rest of argument is totally standard for such variance calculations and is given in detail in \cite{FJMRW,JLR}. Finally, we 
obtain
\begin{multline*}
\frac{\E(H^2)}{\E(H)^2} \sim \frac{1}{2\pi} \int_{-\infty}^{\infty} \int_{-\infty}^{\infty} h(x_0,y_0)
\exp\left\{ -\frac{1}{2}(z_1,z_2)D^2{g(x_0,y_0)}(z_1,z_2)^T \right\} \ dz_1\ dz_2\\
= \frac{h(x_0,y_0)}{\Det(D^2{g}(x_0,y_0))^{1/2}} = \frac{(d-1) d^2}{2(d-2)\sqrt{d-3}} \cdot
\frac{2 (d-2) \sqrt{d-3}} { (d-1) \sqrt{d^3 (d - 4)}} = \sqrt{\frac{d}{d-4}},
\end{multline*}
as required.


\subsubsection{Analysis of variance}

Since the order of $\Var(H)$ is the same as $\E(H)^2$, we apply the well known Robinson-Wormald method \cite{RW92,RW94} 
(sometimes described as the small subgraph conditioning me\-thod).  In particular, we follow here the approach employed by 
Janson and Wormald \cite{JW}.  We denote falling factorials as $[x]_m:=x(x-1)\cdots(x-m+1)$.

\begin{thm}[Robinson and Wormald~\cite{RW92,RW94}]\label{thm:avar}
Let $\la_i>0$ and $\delta_i > -1$ be real numbers for $i=1,2,\dots$ and suppose that for each $n$ there are random 
variables $I_i=I_i(n)$, $i=1,2,\dots$ and $H=H(n)$, all defined on the same probability space $\mathcal{G}=\mathcal{G}_n$ 
such that $I_i$ is nonnegative integer valued, $H$ is nonnegative and $\E(H)>0$ (for $n$ sufficiently large).  Suppose 
furthermore that
\begin{enumerate}[(i)]
\item For each $k\geq 1$, the variables $I_1,\dots, I_k$ are asymptotically independent Poisson random variables with 
$\E(I_i)\to\la_i$,
\item if $\mu_i=\la_i(1+\delta_i)$, then
$$\frac{\E(H[I_1]_{m_1}\cdots[I_k]_{m_k})}{\E (H)}\to\prod_{i=1}^{k}{\mu_i^{m_i}}$$
for every finite sequence $m_1,\dots, m_k$ of nonnegative integers,
\item $\sum_i\la_i\delta_i^2<\infty$,
\item $\E (H^2)/\E( H)^2\leq\exp(\sum_i \la_i\delta_i^2)+o(1)$ as $n\to\infty$.
\end{enumerate}
Then $H>0$ \aas.
\end{thm}

Note that a doubly indexed sequence $I_{i,j}$ can be used in place of $I_i$, as this is only a matter of notation.  
Janson and Wormald showed that \aas\ a random regular graph that is randomly colored contains a rainbow Hamilton cycle.  
Our goal differs slightly from theirs as we want to show that \aas\ a random regular graph of order $n$ that is randomly 
colored will contain a rainbow $(n-1)$-cycle that avoids a particular vertex $v$ and a particular color 
$c$.  In applying the method, we will use vertex disjoint paths to condition upon.

Consider $G^*_{n,d}$ that is randomly colored by the method described in Section~\ref{subsec:config}.  Recall that we are 
interested in finding rainbow $(n-1)$-cycles that avoid the vertex $v$ and
the color $c$.  For $i \geq j\geq  1$, denote by 
$\cP_{i,j}$ a sub-configuration that projects to a set of $j$ vertex disjoint paths (cyclically ordered) 
$P_1,P_2,\dots,P_j$ of $G^*_{n,d}$ such that the following hold for all $\ell$, $1\leq\ell\leq j$:
\begin{enumerate}[\quad(a)]
\item $|E(P_{\ell})| \geq 2$,
\item $|E(P_1)|+\cdots+|E(P_j)|=i+j$,
\item $P_{\ell}$ avoids vertex $v$,
\item each edge of $P_{\ell}$ avoids the color $c$, and
\item the last edge of $P_j$ and the first edge of $P_{j+1}$ are the same color (where $j+1=1$ when $\ell=j$).
\end{enumerate}
Equivalently, $\cP_{i,j}$ can be constructed as follows. Choose a cycle of
length~$i$ and remove any $j$ of its edges,
obtaining $j$ disjoint paths (some of them might consist of just one vertex). Then to every endpoint of these paths 
we add one edge and color satisfying (d) and (e). Janson and Wormald~\cite{JW} considered such structures using a 
different language.

Note that the definition of $\cP_{i,j}$ implies a natural ordering of the vertices for each path, e.g., 
$P_{\ell}=v_{\ell,1}v_{\ell,2}\ldots v_{\ell,|E(P_{\ell})|+1}$.  Observe that such a sub-configuration will project to a 
subgraph consisting of $i+2j$ vertices.  Define the random variable $I_{i,j}$ to count the number of sub-configurations 
$\cP_{i,j}$.  We will show that $I_{i,j}$ has a Poisson distribution when $i,j=O(1)$. This will follow from the standard application of 
the method of moments (see, e.g., \cite{JLR}). For simplicity, we only compute the first moment as in all similar 
problems, the argument extends immediately to (mixed) higher factorial moments.

To determine $\E(I_{i,j})$, we first calculate the possible number $a_{i,j}$ of sub-configurations projecting 
to $j$ disjoint paths satisfying (a)-(c), then the probability $p_{i,j}$ that the edges of such a sub-configuration 
are contained in the configuration model, and lastly the probability $q_{i,j}$ that such a projected sub-configuration 
is colored in such a way that (d) and (e) are satisfied.  It will follow that $\E(I_{i,j}) = a_{i,j}p_{i,j}q_{i,j}$. 
We will also consider the case when $j=0$, where in this case $\cP_{i,0}$ can be seen as a sub-configuration that 
projects to a cycle of $G^*_{n,d}$ consisting of $i$ edges.  

Let $|E(P_{\ell})|=x_{\ell}$ for $1\leq\ell\leq j$.  We want to find the number of solutions to $x_1+x_2+\cdots+x_j=i+j$ 
given that $x_{\ell}\geq 2$ for $1\leq\ell\leq j$ which is easily done by considering the equivalent equation 
$(x_1-2)+(x_2-2)+\cdots+(x_j-2)=i-j$ where $x_{\ell}-2\geq 0$ for $1\leq\ell\leq j$.  Hence, the number of solutions is 
$\binom{i-1}{j-1}$. For a given set of path lengths, we consider the number of ways for choosing the vertices for these 
paths.  The total number of ways to choose vertices is
$\frac{1}{2j}[n-1]_{i+2j}\sim \frac{1}{2j}(n^{i+2j})$.  When constructing $G^*_{n,d}$ from 
the configuration model, recall that the edge set is the projection of a disjoint pairing of points of the multiset 
$W=W_1\cup W_2\cup\dots\cup W_n$ where each partition set contains $d$ elements. Thus the number of ways to pick points 
from the configuration model is $d^{i+2j}(d-1)^{(x_1-1)+(x_2-1)+\cdots+(x_j-1)}=d^{i+2j}(d-1)^i.$  Therefore,

$$a_{i,j} \sim \frac{1}{2j} \binom{i-1}{j-1} n^{i+2j}d^{i+2j}(d-1)^i=\frac{1}{2i}\binom{i}{j}n^{i+2j}d^{i+2j}(d-1)^i.$$

Now we turn to finding the probability $p_{i,j}$.  For a given edge of $\cP_{i,j}$, the probability of that edge 
appearing is $\sim 1/(dn)$, implying

$$p_{i,j} \sim \left(\frac{1}{dn}\right)^{i+j}.$$

While considering $q_{i,j}$, recall that the coloring of $G^*_{n,d}$ (using $n$ colors) was chosen uniformly at random 
from all partitions of the multiset $C$ that contained $d/2$ copies of each color.  Given a path $P_{\ell}$ and the 
color of its last edge, we want to determine the probability that the first edge of $P_{\ell+1}$ is colored the same.  
There will be $d/2-1$ choices, out of the total $dn/2$ choices to color this edge.  Hence

$$q_{i,j} \sim \left(\frac{\frac{d}{2}-1}{\frac{d}{2}n}\right)^j = \left(\frac{d-2}{dn}\right)^j.$$

Therefore,
$$
\E(I_{i,j}) \sim \frac{1}{2i}\binom{i}{j}n^{i+2j}d^{i+2j}(d-1)^i \left(\frac{1}{dn}\right)^{i+j} 
\left(\frac{d-2}{dn}\right)^j = \frac{1}{2i}\binom{i}{j}(d-1)^i(d-2)^j.
$$

Similarly, one can compute that $\E(I_{i,0})\sim\frac{1}{2i}(d-1)^i$, which agrees with the above formulation 
for $\E(I_{i,j})$ when $j=0$.  Now define $\la_{i,j}$ and $\delta_{i,j}$ as follows:
\begin{align*}
 \la_{i,j} &= \frac{1}{2i}\binom{i}{j}(d-1)^i(d-2)^j, \\
 \delta_{i,j} & = \begin{cases}
		(-1)^{i+j}\frac{2^j}{(d-1)^i(d-2)^j}, & j > 0, \\
		-\frac{2}{(d-1)^i}{\bf 1}[i~odd], & j=0.
	\end{cases}
\end{align*}

As one could expect, the values we have obtained and those obtained by Janson and Wormald in Lemma~3.3 in~\cite{JW} 
are the same. Thus, as it was shown there, we immediately get that the conditions (i), (iii) and (iv) in 
Theorem~\ref{thm:avar} are satisfied. Moreover, one can check that the condition (ii) also holds. We omit this 
proof here, since basically it is the same as the corresponding proof in~\cite{JW}. 

Thus, by Theorem \ref{thm:avar} \aas\ $H>0$ completing the proof of Theorem~\ref{thm:rainbow}.


\section{Proof of Theorem~\ref{thm:main_k}}

We briefly outline the proof, which is philosophically similar to the proof of Theorem~\ref{thm:main_3}, 
in the sense that we wish to find a particular sub-hypergraph of $\hgk{n+(k-1)}{p}$ and prove a corresponding result in that 
sub-hypergraph.  Take $n=(k-1)(2m+1)$, for $m$ a positive integer. (Clearly, $n\equiv(k-1)\!\!\mod 2(k-1)$.) Let 
$\ka=k-2$.  We may view $\hgk{n}{p}$ as a subgraph of $\hgk{n+(k-1)}{p}$, where the latter hypergraph has vertex 
set $[n]\cup\{v,c_1,\dots,c_{\ka}\}$.  Partition the new vertex set as $X=[2m+1]\cup\{v\}$ and 
$Y=[2m+2,n]\cup\{c_1,\dots,c_{\ka}\}$.  Note $|X|=2(m+1)$ and $|Y|=2(m+1)\ka$.  Next create the multisets 
$\mathcal{X}$ and $\mathcal{Y}$, where $\mathcal{X}$ contains $d$ copies of each $x\in X$ and is of size $2(m+1)d$ 
and where $\mathcal{Y}$ contains $d/2$ copies of each $y\in Y$ and is of size $d(m+1)\ka$.  
(Note that in the proof of Theorem~\ref{thm:main_3} we did not have $\mathcal{X}$. The next paragraph will explain why it is necessary to define~$\mathcal{X}$ here.)

Let $\psi_1:\mathcal{X}\to X$ and $\psi_2:\mathcal{Y}\to Y$ be projection functions, and let 
$\psi:\binom{\mathcal{X}}{2}\times\binom{\mathcal{Y}}{\ka}\to \binom{X}{2}
\times \binom{Y}{\ka}$ denote the 
projection that applies $\psi_1,\psi_2$ to the respective elements coordinate-wise.  
Let $X_1,X_2,\ldots,X_{d}$
be a uniform random partition of $\mathcal{X}$ into $d$ sets of size $2(m+1)$ and let $Y_1,Y_2,\ldots,Y_{d}$
be a uniform random partition of $\mathcal{Y}$ into $d$ sets of size $(m+1)\ka $.  
For each pair $X_j,Y_j$ ($1\leq i \leq d$), we can construct a random $k$-uniform hypergraph 
$\G(X_j,Y_j,p_2)$ (for a certain value of $p_2=\Omega(p)$), whose edge set is a subset of 
$\binom{X_j}{2}\times\binom{Y_j}{\ka}$.  An edge $\{\nu_1,\nu_2,\xi_1,\xi_2,\dots,\xi_{\ka}\}$ of $\G(X_j,Y_j,p_2)$ 
is called {\it spoiled} if $\psi_1(\nu_1)=\psi_1(\nu_2)$ or if there exists $1\leq r < s \leq \ka$ such 
that $\psi_2(\xi_r)=\psi_2(\xi_s)$. 
Dudek and Frieze~\cite{DF} showed that with
probability $1-e^{-\omega(d)},(\omega(d)\to\infty$ with $d$), we can construct independent hypergraphs $\G(X_j,Y_j,p_2)\subseteq \hgk{n}{p},\,j=1,2,\ldots,d$ 
that will each simultaneously contain a random perfect matching $M_j$ with no spoiled edges. 
(If $\mathcal{X}$ would be replaced by $X$, like in the proof of Theorem~\ref{thm:main_3}, then we would still have spoiled edges, and consequently, we could not construct independent hypergraphs $\G(X_j,Y_j,p_2)\subseteq \hgk{n}{p}$.)
Let $\La_d=\psi(M_1\cup M_2\cup\cdots\cup M_d)$ and  denote by $\mathcal{U}$ the event that 
$M_1\cup M_2\cup\cdots M_d$ contains no spoiled edges.
Therefore, $\La_d$ is a subgraph of $\hgk{n}{p}$ and also of $\hgk{n+(k-1)}{p}$.

It was also argued in~\cite{DF} that $\La_d$ can be modeled as follows, conditioning on $\mathcal{U}$: 
construct $\La_d$ by taking a random pairing of $\mathcal{X}$ into $(m+1)d$ sets $e_1,e_2,\dots,e_{(m+1)d}$ of size 
two and a random partition $f_1,f_2,\dots,f_{(m+1)d}$ of $\mathcal{Y}$ into $(m+1)d$ sets of size $\ka$; define the 
edges of $\La_d$ to be $\psi(e_{\ell},f_{\ell})$ for $1\leq\ell\leq (m+1)d$.  
For sub-hypergraphs $\La_d$ of 
$k$-uniform hypergraphs (whose orders are divisible by $2(k-1)$) constructed as above, the following result was 
obtained:

\begin{thm}[Dudek and Frieze~\cite{DF}]
Suppose that ${\ka}\ge 1$ and $d$ is a sufficiently large positive even integer. Then,
$$
\Pr(\La_d\text{ contains a loose Hamilton cycle})\geq 2-(1+o(1))\sqrt{\frac{d}{d-2(\ka+1)}}
\geq 1-\frac{3\ka}{d}.
$$
\end{thm}

Here we will refine this result, showing that $\La_d$ will also contain a loose $(2m+1)$-cycle avoiding 
$\{v,c_1,\dots,c_{\ka}\}$, which will define a loose Hamiltonian cycle of $\hgk{n}{p}$.

\begin{thm}\label{thcolor}
Suppose that ${\ka}\ge 1$ and $d$ is a sufficiently large positive even integer. Then,
\begin{multline*}
$$\Pr(\La_d\text{ contains a loose $(2m+1)$-cycle avoiding $\{v,c_1,\dots,c_{\ka}\}$})\\ \geq 
2-(1+o(1))\sqrt{\frac{d}{d-2(\ka+1)}}
\geq 1-\frac{3\ka}{d}.$$
\end{multline*}
\end{thm}
\noindent
Since $pn^{k-1}/\log n\to\infty$, we can make $d$ arbitrarily large implying Theorem~\ref{thm:main_k}.
 
Let $H$ be a random variable which counts the number of loose $(2m+1)$-cycles avoiding $\{v,c_1,\dots,c_{\ka}\}$ in 
$\La_d$ 
such that the edges only intersect in $X$. Note that every such loose $(2m+1)$-cycle
induces an ordinary cycle of length~$2m+1$ in $X\setminus\{v\}$ and a partition of $Y\setminus \{c_1,\dots,c_{\ka}\}$ 
into $\ka$-sets.

\begin{lem}\label{lem:Expectation}
Suppose that ${\ka}\ge 1$ and $d$ is a positive even integer. Then,
$$
\E(H) \sim \sqrt{\ka}e^{(\ka+1)/2} \pi
\left( \frac{d-2}{d}\right)^{\ka + \frac{3}{2}+\frac{{\ka}+1}{2}(d-2)}
\left( \frac{(d-1)(d-2)^{\frac{{\ka}+1}{2}(d-2)}}{d^{\frac{{\ka}+1}{2}(d-2)}} \right)^{2m+1}.
$$
Hence, $\lim_{m\to\infty} \E(H) = \infty$ for every $d > e^{{\ka}+1}+1$.
\end{lem}

\noindent
The last conclusion holds since for $d> e^{{\ka}+1}+1$,
\begin{align*}
\frac{(d-1)(d-2)^{\frac{{\ka}+1}{2}(d-2)}}{d^{\frac{{\ka}+1}{2}(d-2)}}
&= \left. (d-1) \middle/
\left( \left( \frac{d}{d-2} \right)^{\frac{d-2}{2}} \right)^{\ka + 1}
\right. \\
&= \left. (d-1) \middle/
\left( \left( 1 + \frac{2}{d-2} \right)^{\frac{d-2}{2}} \right)^{\ka + 1}
\right. \\
& >
\frac{d-1}{e^{\ka + 1}}
> 1.
\end{align*}

\begin{lem}\label{lem:Variance}
Suppose that ${\ka}\ge 1$ and $d$ is a sufficiently large positive even integer. Then,
$$
\frac{\E(H^2)}{\E(H)^2} \le (1+o(1)) \sqrt{\frac{d}{d-2({\ka}+1)}}.
$$
\end{lem}
Now Theorem \ref{thcolor} easily follows from this, since
$$\Pr(H=0)\leq  \frac{\Var(H)}{\E(H)^2}\leq  (1+o(1))\sqrt{\frac{d}{d-2({\ka}+1)}}-1.$$

In order to prove the above lemmas we will also need the following simple auxiliary result.

\begin{claim}\label{claim:poisson}\hfill
\begin{enumerate}[(i)]
\item Given a random pairing of $\mathcal{X}$ into $(m+1)d$ sets $e_1,e_2,\dots,e_{(m+1)d}$, let $S$ denote the number 
of pairs $\nu_1,\nu_2$ of elements in $\mathcal{X}$ with $\psi_1(\nu_1)=\psi_1(\nu_2)$ that appear in some $e_{\ell}$ 
for some $\ell$, $1\leq\ell\leq(m+1)d$.  Then
$$
\Pr(S=0) = (1-o(1))e^{-\frac{d-1}{2}}.
$$
\item Given a random partition of $\mathcal{Y}$ into $(m+1)d$ sets $f_1,f_2,\dots,f_{(m+1)d}$ of size $\ka$, let 
$T$ denote the number of pairs $\xi_1,\xi_2$ of elements in $\mathcal{Y}$
with $\psi_2(\xi_1)=\psi_2(\xi_2)$ that appear in some $f_{\ell}$ for some $\ell$, $1\leq\ell\leq(m+1)d$.
Then 
$$
\Pr(T=0) = (1-o(1))e^{-\frac{({\ka}-1)(d-2)}{4}}
$$
\end{enumerate}
\end{claim}

\begin{proof}[Proof of Claim]
It follows from the standard application of the method of moments (see, e.g., \cite{JLR}) that  $S$ and $T$ are 
asymptotically Poisson with means $\frac{(d-1)}{2}$ and $\frac{(\ka-1)(d-2)}{4}$, respectively.
\end{proof}


\subsection{Expectation (the proof of Lemma~\ref{lem:Expectation})}

Let a $(2m+1)$-cycle in $\mathcal{X}$ be a set of $2m+1$ disjoint pairs of points of $\mathcal{X}$ such
that they form a $(2m+1)$-cycle in $X\setminus\{v\}$ when they are projected by $\psi_1$. First note that the 
number $a_{2m+1}$ of such cycles in~$\mathcal{X}$ is 
$$
a_{2m+1} = \frac{(d(d-1))^{2m+1} (2m+1)!}{2(2m+1)}
$$
(see, e.g., (9.2) in~\cite{JLR}).

Let $p_{2m+1}$ be the probability that a given set of $2m+1$ disjoint pairs of points of~$\mathcal{X}$ forming a 
$(2m+1)$-cycle is contained in a random configuration and that $\mathcal{U}$ holds.

First note that from Claim~\ref{claim:poisson} the number of configurations
partitioned
into $(2m+1)$ cells of $d$ points for which $\mathcal{U}$ holds is asymptotically
\begin{equation*}
\sim e^{-(d-1)/2}(2d(m+1)-1)!!=e^{-(d-1)/2}\frac{(2d(m+1))!}{2^{d(m+1)}(d(m+1))!}.
\end{equation*}
After fixing the pairs in a $(2m+1)$-cycle we have to randomly pair up $2(d-2)m$ points.
In other words, we want to compute the number of configurations partitioned
into $2m+1$ cells of $(d-2)$ points for which $\mathcal{U}$ holds. Hence, again by Claim~\ref{claim:poisson} we get,
\begin{equation*}
\sim e^{-(d-3)/2}(2(d-2)(m+1)-1)!!
\end{equation*}
and
$$p_{2m+1} \sim \frac{e^{-(d-3)/2}(2(d-2)(m+1)-1)!!}{e^{-(d-1)/2}(2d(m+1)-1)!!} =
e\frac{(2(d-2)(m+1)-1)!!}{(2d(m+1)-1)!!} .
$$

Let $q_{2m+1}$ be the probability that a randomly chosen set $U$ of $(2m+1)\ka $
points of $\mathcal{Y}$ (represented by $2m+1$ $\ka$-sets) is equal after the projection $\psi_2$
to $Y\setminus\{c_1,\dots,c_{\ka}\}$, i.e., $\psi_2(U)=Y\setminus\{c_1,\dots,c_{\ka}\}$. Note that $U$ must contain 
precisely one copy
of every element of $Y\setminus\{c_1,\dots,c_{\ka}\}$. Hence, we have $(d/2)^{(2m+1)\ka }$ out of 
$\binom{{\ka}d(m+1)}{(2m+1){\ka}}$
choices for $U$. Thus, again by Claim~\ref{claim:poisson} we get,
\begin{equation*}
q_{2m+1} \sim \frac{e^{-(\ka-1)(d-4)/4} (d/2)^{(2m+1)\ka}}{e^{-(\ka-1)(d-2)/4} \binom{{\ka}d(m+1)}{(2m+1){\ka}}}
= e^{(\ka-1)/2} \frac{(d/2)^{(2m+1)\ka }}{\binom{{\ka}d(m+1)}{(2m+1){\ka}}}.
\end{equation*}
We have $e^{-(\ka-1)(d-4)/4}$ in the numerator to account for conditioning on $\mathcal{U}$ after the deletion of $U$
from $\mathcal{Y}$.

Consequently, $\E(H) = a_{2m+1} p_{2m+1} q_{2m+1}$ which asymptotically equals the formula from 
Lemma~\ref{lem:Expectation}. 


\subsection{Variance (the proof of Lemma~\ref{lem:Variance})}

Let $C_1$ and $C_2$ be two $(2m+1)$-cycles in $\mathcal{X}$ sharing precisely $b$ pairs. Clearly, 
$|C_1\cup C_2|=2(2m+1)-b$. Denote by $p_{2m+1}(b)$ the probability that $C_1$ and $C_2$ are 
contained in a random configuration of $\mathcal{X}$ for which $\mathcal{U}$ holds. (Clearly, $p_{2m+1}(2m+1)=p_{2m+1}$).
First note that if we ignore $\mathcal{U}$ then the number of configurations containing $C_1$ 
and $C_2$ equals
$$
(2d(m+1)-2(2(2m+1)-b)-1)!!
$$
Next conditioning on $\mathcal{U}$ we obtain by Claim~\ref{claim:poisson} that the number of configurations 
containing $C_1$ 
and $C_2$ is bounded from above by
$$
(1+o(1))e^{-(d-5)/2}(2d(m+1)-2(2(2m+1)-b)-1)!!
$$
(The factor $e^{-(d-5)/2}$ corresponds to the case when $b=0$.)
Hence,
\begin{align*}
p_{2m+1}(b) &\le (1+o(1))\frac{e^{-(d-5)/2}(2d(m+1)-2(2(2m+1)-b)-1)!!}{e^{-(d-1)/2}(2d(m+1)-1)!!}\\
& =(1+o(1))e^2\frac{(2d(m+1)-2(2(2m+1)-b)-1)!!}{(2d(m+1)-1)!!}.\notag
\end{align*}
Let $U$ and $W$ be two randomly chosen collections of $2m+1$ $\ka$-sets in $\mathcal{Y}$ satisfying
$|W|=|U|=2m+1$ and $|W\setminus U|= 2m+1-b$.
Let $r_{2m+1}(b)$ be the probability
that both $U$ and $W$ are both equal after the projection $\psi_2$ to $Y$, 
i.e., $\psi_2(U)=\psi_2(W)=Y$.
Conditioning on $\psi_2(U)=Y$ we have $(d/2-1)^{{\ka}(2m+1)-{\ka}b}$ out of
$\binom{{\ka}d(m+1)-{\ka}(2m+1)}{{\ka}(2m+1)-{\ka}b}$ choices for $W$.
Thus,  we obtain (with $b=0$ once again a worst-case),
\begin{align*}
r_{2m+1}(b) &\le (1+o(1))q_{2m+1} \frac{e^{-(\ka-1)(d-6)/4} (d/2-1)^{{\ka}(2m+1)-{\ka}b}}{ e^{-(\ka-1)(d-4)/4}
\binom{{\ka}d(m+1)-{\ka}(2m+1)}{{\ka}(2m+1)-{\ka}b}}\\
&\leq (1+o(1))e^{(\ka-1)/2}q_{2m+1} \frac{ (d/2-1)^{{\ka}(2m+1)-{\ka}b} }{ \binom{{\ka}d(m+1)-{\ka}(2m+1)}{{\ka}(2m+1)-{\ka}b}}.
\end{align*}
Moreover, let $N(b)$ be the number of $(2m+1)$-cycles in $\mathcal{X}$ that intersect a given $(2m+1)$-cycle in $b$
pairs.
By \cite{JLR} (cf. last equation on page~253), we get
\begin{align*}
N(b) = \sum_{a=0}^{\min\{b,2m-b+1\}} &\frac{a(2m+1)}{b(2m-b+1)}2^{a-1}(d-2)^{2m+a-b+1}\\
&\times (d-3)^{2m+1-a-b}(2m-b)! \binom{b}{a} \binom{2m-b+1}{a},
\end{align*}
where for $a=b=0$ we set $\frac{a}{b}=1$.

Consequently,
\begin{align*}
\frac{\E(H^2)}{\E(H)^2} &\le \frac{1}{\E(H)} +
\sum_{b=0}^{2m} \frac{N(b)p_{2m+1}(b)r_{2m+1}(b)}{a_{2m+1}p_{2m+1}^2q_{2m+1}^2} .\end{align*}
Below we ignore all cases for which $a=0$, $a=b$ or $a+b=2m+1$
since their contribution is negligible as can be easily checked by the reader.
Using the Stirling formula, one can show that 
\begin{align*}
\sum_{b=0}^{2m} \frac{N(b)p_{2m+1}(b)r_{2m+1}(b)}{a_{2m+1}  p_{2m+1}^2q_{2m+1}^2} \qquad\qquad\\
 \le  \frac{1}{4\pi (m+1)} \sum_{b=0}^{2m} \sum_{a=0}^{\min\{b,2m-b+1\}} & h\big{(}a/(2(m+1)),b/(2(m+1))\big{)}\\
 &\times\exp\{2(m+1)\cdot g\big{(}a/(2(m+1)),b/(2(m+1))\big{)}\}\\
 & \times\left( 1+ O\left(\frac{1}{\min\{a,b-a,2m-a-b\}+1} \right)\right),
\end{align*}

where
\begin{align*}
g(x,y) &= x\log(2) - \log(d) - \log(d - 1) + (1 + x - y)\log(d - 2) \\
&\qquad+ (1 - x - y) \log(d - 3) + y\log(y) + 2 (1 - y)\log(1 - y) \\
&\qquad- (y - x)\log(y - x) -  2 x\log(x) - (1 - x - y)\log(1 - x - y) \\
&\qquad+ (d/2 - 2 + y)\log(d - 4 + 2 y) + (d/2)\log(d) - (d - 2)\log(d - 2) \\
&\qquad+ {\ka}(d/2 - 1)\log(d) + {\ka}(1 - y)\log(1 - y) + {\ka}(d/2 - 2 + y)\log(d - 4 + 2 y) \\
&\qquad- {\ka}(d - 3 + y)\log(d - 2)
\end{align*}
and
$$
h(x,y) = \frac{ d^{{\ka}+3/2} (d-1) }{ (d-2)^{3{\ka}+4} (d-3)} 
\sqrt{\frac{ (1-x-y)(d-4+2y)^{4{\ka}+5}  }{ y(y-x)(1-y)^{2{\ka}+5}  }}.
$$

It was shown in~\cite{DF} that $(x_0,y_0) = (2(d-2)/(d(d-1)), 2/d)$ is the unique global maximum point of 
$g(x,y)$ in $S=\{(x,y) : 0< x< y< 1-x\}$. It was also proved that $g(x,y)$ has no asymptote near the boundary 
of $S$, nor does it approach a limit which is greater than~$0$ (for $d$ large enough). Let $D^2{g}$ be the
Hessian matrix of second derivatives. Routine calculations show that
$$
D^2{g}(x,y)=\left(
\begin{array}{c c}
-\frac{2}{x} + \frac{1}{x - y} + \frac{1}{-1 + x + y} & \frac{1}{-x + y} + \frac{1}{-1 + x + y}\\
\frac{1}{-x + y} + \frac{1}{-1 + x + y}           &
\frac{2 + {\ka}}{1 - y} + \frac{1}{x - y} + \frac{1}{y} + 
\frac{1}{-1 + x + y} + \frac{2 (1 + {\ka})}{-4
+ d + 2 y}\\
\end{array}
\right)
$$
Hence,
$$
D^2{g}(x_0,y_0)=\left(
\begin{array}{c c}
-\frac{(d-1)^2 d}{2 (d-3)} & \frac{(d-4) (d-1)^2 d}{2 (d-2)(d-3)} \\
\frac{(d-4) (d-1)^2 d}{2 (d-2)(d-3)} & -\frac{d (16 + d (-34 + d (28 + (-9 + d) d - 2 {\ka}) + 6
{\ka})}{2 (d-3) (d-2)^2}
\end{array}
\right)
$$
and
$$
\Det(D^2{g}(x_0,y_0)) = \frac{d^3 (d-1)^2 (d - 2 (1 + {\ka}))}{4 (d-3) (d-2)^2}.
$$

As we already noted in the previous section the rest of argument is totally standard for such variance
calculations. Finally, we obtain
\begin{align*}
\frac{\E(H^2)}{\E(H)^2} &\le (1+o(1)) \frac{1}{2\pi} \int_{-\infty}^{\infty}
\int_{-\infty}^{\infty} h(x_0,y_0)
\exp\left\{ -\frac{1}{2}(z_1,z_2)D^2{g(x_0,y_0)}(z_1,z_2)^T \right\} \ dz_1\ dz_2\\
&\sim \frac{h(x_0,y_0)}{\Det(D^2{g}(x_0,y_0))^{1/2}}\\
&= \frac{(d-1) d^2}{2(d-2)\sqrt{d-3}} \cdot \frac{2 (d-2) \sqrt{d-3}} { (d-1)
\sqrt{d^3 (d - 2 (1 + {\ka}))}}\\
&=  \sqrt{\frac{d}{d-2({\ka}+1)}},
\end{align*}
as required.

\bibliographystyle{plain}
\begin{thebibliography}{11}
\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 \textbf{27} (1985), 173--178.

\bibitem{B} B. Bollob\'as,
{\em A probabilistic proof of an asymptotic formula for the number of labelled regular graphs},
European Journal of Combinatorics \textbf{1} (1980), 311--316.

\bibitem{Bol84}
B.~Bollob\'as, \emph{The evolution of sparse graphs}, Conference in Honour of
  Paul Erd\H{o}s (B.~Bollob\'as, ed.), Graph Theory and Combinatorics, Academic
  Press, 1984, pp.~35--57.
  
\bibitem{DF} A.~Dudek and A.~Frieze, 
{\em Loose Hamilton cycles in random uniform hypergraphs},
Electronic Journal of Combinatorics \textbf{18} (2011), \#P48.

\bibitem{ErdosRenyi60}
P.~Erd{\H{o}}s and A.~R{\'e}nyi, \emph{On the evolution of random graphs},
Magyar Tud. Akad. Mat. Kutat\'o Int. K\"ozl.~\textbf{5} (1960), 17--61.
  
\bibitem{F} A.~Frieze,
{\em Loose Hamilton cycles in random 3-uniform hypergraphs},
Electronic Journal of Combinatorics \textbf{17} (2010), \#N28.

\bibitem{FJMRW} A.~Frieze, M.~Jerrum, M.~Molloy, R.~Robinson and N.~Wormald,
{\em Generating and counting Hamilton cycles in random regular graphs},
Journal of Algorithms \textbf{21} (1996), 176--198.

\bibitem{J} S.~Janson,
{\em Random regular graphs: asymptotic distributions and contiguity},
Combinatorics, Probability and Computing \textbf{4} (1995), 369--405.

\bibitem{JLR} S.~Janson, T.~\L{}uczak and A.~Ruci\'nski,
{\em Random Graphs}, Wiley, 2000.

\bibitem{JW} S.~Janson and N.~Wormald,
{\em Rainbow Hamilton cycles in random regular graphs},
Random Structures and Algorithms \textbf{30} (2007), 35--49.

\bibitem{JKV} A.~Johansson, J.~Kahn and V.~Vu,
{\em Factors in random graphs},
Random Structures and Algorithms \textbf{33} (2008), 1--28.

\bibitem{KS75}
J.~Koml{\'o}s and E.~Szemer{\'e}di, \emph{Hamilton cycles in random graphs}, 
Infinite and Finite Sets ({C}olloq., {K}eszthely, 1973; dedicated to {P}.
{E}rd{\H o}s on his 60th birthday), {V}ol. {II}, North-Holland, Amsterdam, 1975, pp.~1003--1010.

\bibitem{KS83} J.~Koml\'os and E.~Szemer\'edi,
{\em Limit distributions for the existence of Hamilton circuits in a random graph},
Discrete Mathematics \textbf{43} (1983), 55--63.

\bibitem{Korshunov83}
  A. Kor\u{s}unov, \emph{A new version of the solution of a problem of {E}rd{\H o}s and {R}\'enyi on {H}amiltonian cycles 
in undirected graphs}, Random Graphs '83 ({P}ozna\'n, 1983), North-Holland Math. Stud., vol. 118, North-Holland, 
Amsterdam, 1985, pp.~171--180.
  
\bibitem{MRRW} M.~Molloy, H.~Robalewska, R.~Robinson and N.~Wormald,
{\em 1-Factorizations of random regular graphs},
Random Structures and Algorithms \textbf{10} (1997), 305--321.

\bibitem{Posa76} L.~P\'osa, 
{\em Hamilton circuits in random graphs}, 
Discrete Mathematics~\textbf{14} (1976), 359--364.  

\bibitem{RW92} R. Robinson and N. Wormald, 
{\em Almost all cubic graphs are Hamiltonian}, 
Random Structures and Algorithms \textbf{3} (1992), 117--125.

\bibitem{RW94} R. Robinson and N. Wormald, 
{\em Almost all regular graphs are Hamiltonian}, 
Random Structures and Algorithms \textbf{5} (1994), 363--374.

\end{thebibliography}

\end{document}