\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{enumerate}
\usepackage{bbm}
\usepackage{amsthm,amsmath,amssymb}

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

\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\newcommand{\eps}{\varepsilon}
\newcommand{\cI}{\mathcal{I}}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\conntime}{\tau_c}
\newcommand{\isoltime}{\tau_i}
\newcommand{\process}{\{\cH^k(n,M)\}_M}
\newcommand{\hknm}{\cH^k(n,M)}
\newcommand{\hknp}{\cH^k(n,p)}
\newcommand{\omone}{r_0}

\newcommand{\cond}{\; \middle\vert \;}
\newcommand{\EE}{\mathbb{E}}
\newcommand{\Bin}{\mathrm{Bin}}
\newcommand{\Po}{\mathrm{Po}}
\newcommand{\Ind}[1]{\mathbbm{1}_{[#1]}}


\renewcommand{\Pr}{\mathbb{P}}




\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{thm}[theorem] {Theorem} 
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}

\title{Threshold and hitting time for high-order connectedness in random hypergraphs}


\author{Oliver Cooley \qquad Mihyun Kang \qquad Christoph Koch\thanks{The authors are supported by Austrian Science Fund (FWF): P26826, W1230.}\\
\small Institute of Discrete Mathematics\\[-0.8ex]
\small Graz University of Technology\\[-0.8ex] 
\small Steyrergasse 8010, Graz 8010, Austria\\
\small\tt \{cooley,kang,ckoch\}@math.tugraz.at\\
}


\date{\dateline{25th February 2015}{22nd May 2016}\\
\small Mathematics Subject Classifications: 05C80, 05C65}

\begin{document}

\maketitle


\begin{abstract}
We consider the following definition of connectedness in $k$-uniform hypergraphs: two $j$-sets (sets of $j$ vertices) are $j$-connected if there is a walk of edges between them such that two consecutive edges intersect in at least $j$ vertices. The hypergraph is $j$-connected if all $j$-sets are pairwise $j$-connected. We determine the threshold at which the random $k$-uniform hypergraph with edge probability $p$ becomes $j$-connected with high probability. We also deduce a hitting time result for the random hypergraph process -- the hypergraph becomes $j$-connected at exactly the moment when the last isolated $j$-set disappears. This generalises the classical hitting time result of Bollob\'as and Thomason for graphs.

  \bigskip\noindent \textbf{Keywords:} random hypergraphs; connectedness; hitting time
\end{abstract}







\section{Introduction}

\subsection{Preliminaries and main results}
In the study of random graphs, one of the most well-known results concerns the \emph{hitting time} for connectedness. More precisely, if we add randomly chosen edges one by one to an initially empty graph on $n$ vertices, then with high probability at the moment the last isolated vertex gains its first edge, the whole graph will also become connected (this classical result was first proved by Bollob\'as and Thomason in~\cite{BT85}). This interplay between local and global properties is an example of the common phenomenon relating graph properties with their smallest obstruction; the graph can certainly not be connected while an isolated vertex still exists, but this smallest obstruction is also the critical one which is last to disappear.

In this paper we generalise the result of Bollob\'as and Thomason to random $k$-uniform hypergraphs. For an integer $k\ge 2$, a $k$-uniform hypergraph consists of a set $V$ of vertices together with a set $E$ of (hyper-)edges, each consisting of $k$ vertices. (A $2$-uniform hypergraph is simply a graph.) We need to define the notion of connectedness, for which there is a whole family of possible definitions. For any $1\le j \le k-1$, we say that two $j$-sets (sets of $j$ vertices) $J_1,J_2$ are \emph{$j$-connected} if there is a sequence of edges $E_1,\ldots,E_m$ such that
\begin{itemize}
\item $J_1 \subset E_1$ and $J_2\subset E_m$;
\item $|E_{i}\cap E_{i+1}|\ge j$ for all $1\le i \le m-1$.
\end{itemize}
In other words, we may walk from $J_1$ to $J_2$ using edges which consecutively intersect in at least $j$ vertices. A \emph{$j$-component} is a maximal set of pairwise $j$-connected $j$-sets.
A $k$-uniform hypergraph is \emph{$j$-connected} if there is one $j$-component which contains all $j$-sets.%
\footnote{We remark that $j$-connectedness of a $k$-uniform hypergraph $H$ is equivalent to vertex-connectedness of the auxiliary $\binom{k}{j}$-uniform hypergraph $H'$ whose vertices are the $j$-sets of $H$ and with an edge joining $\binom{k}{j}$ such $j$-sets if they lie in a common edge of $H$.}

Note that in the case $k=2,j=1$ this is simply the usual definition of connectedness for graphs. More generally, for arbitrary $k\ge 2$ the case $j=1$ is by far the most well-studied.
The definition for general $j$ is also entirely natural, albeit harder to visualise and often requires more complex analysis. In this paper we will be interested in arbitrary $1\le j \le k-1$ and $k\ge 3$.

There is also more than one model for random hypergraphs. We first define the \emph{uniform model}, the counterpart of the uniform model of Erd\H{o}s and R\'enyi for graphs: given any natural numbers $k,M,n$ such that $M\le \binom{n}{k}$, the random hypergraph $\hknm$ is a hypergraph chosen uniformly at random from all $k$-uniform hypergraphs on vertex set $\{1,\ldots,n\}$ which have $M$ edges. This is closely related to the \emph{random hypergraph process} $\process$ which is defined as follows:
\begin{itemize}
\item $\cH^k(n,0)$ is the hypergraph on vertex set $\{1,\ldots,n\}$ with no edges;
\item For $1\le M \le \binom{n}{k}$, $\hknm$ is obtained from $\cH^k(n,M-1)$ by adding an edge chosen uniformly at random from among those $k$-sets which do not already form an edge.
\end{itemize}
Note that the distribution of the random hypergraph obtained in the $M$-th step of the process is the same as in the uniform model $\hknm$, so the notation is consistent.

We consider asymptotic properties of random hypergraphs and throughout this paper any asymptotics are as $n\to \infty$. In particular we say \emph{with high probability} (or \emph{whp}) to mean with probability tending to $1$ as $n\to \infty$.

We say that a $j$-set is \emph{isolated} if it is not contained in any edges. It is trivial to see that if a hypergraph contains isolated $j$-sets, then it is not $j$-connected (assuming it has more than $j$ vertices). Our main result is that this trivial smallest obstruction is also the critical one in a random hypergraph.

Let $\conntime=\conntime(n,j,k)$ denote the time step in the hypergraph process $\process$ at which the hypergraph becomes $j$-connected. Similarly, let $\isoltime$ denote the time at which the last isolated $j$-set disappears. Note that the properties of being $j$-connected or of having no isolated $j$-set are certainly monotone increasing properties, so these two variables are well-defined. Furthermore, as noted above, $\isoltime \le \conntime$ deterministically.



\begin{thm}\label{thm:hittingtime}
For any $1\le j \le k-1$ and $k\ge 3$, with high probability in the random hypergraph process $\process$ we have $\conntime = \isoltime$.
\end{thm}

The case $j=1$ of this theorem was already proved by Poole as a special case of the results in~\cite{Poole14}. The case $j=k-1$ was previously proved by Kahle and Pittel in~\cite{KP16}. For all other $j$, this result was previously unknown.


The uniform model and the associated hypergraph process allow us to formulate exact hitting time results such as Theorem~\ref{thm:hittingtime}. However, the drawback is that the analysis of the model can become tricky due to the fact that the presence of different edges is not independent (the total number is fixed). For this reason, it is often easier to analyse the \emph{binomial model}: $\hknp$ is a random $k$-uniform hypergraph on vertex set $\{1,\ldots,n\}$ in which each $k$-set is an edge with probability $p$ independently of all other $k$-sets. In Section~\ref{sec:contiguity} we will show that if $p=M/\binom{n}{k}$, then the two models are very similar and we can transfer results from one model to the other.

For the proof of Theorem~\ref{thm:hittingtime} we will also make use of the following result (Theorem~\ref{thm:poisson}), which is interesting in itself and is therefore stated in a significantly more general form than we need for Theorem~\ref{thm:hittingtime}. For integer valued random variables $Z$ and $Z'$ we denote their \emph{total variation distance} by $d_{TV}(Z,Z')$, i.e.\
\begin{equation*}
d_{TV}(Z,Z')=\frac{1}{2}\sum_{i\in \mathbb{Z}}\left|\Pr\left(Z=i\right)-\Pr\left(Z'=i\right)\right|.
\end{equation*}
For integer-valued random variables $X_n$ and $Y$, we say \emph{$X_n$ converges in distribution to $Y$}, denoted by $X_n \stackrel{d}{\longrightarrow} Y$, if for every integer $i$ we have $\Pr(X_n=i)\rightarrow \Pr(Y=i)$.

\begin{theorem}\label{thm:poisson}
For any $k\ge 3$ and $1\le j \le k-1$ and for any integer $s\ge0$, let
$$p_s=p_s(n,k,j)=\frac{j\log n+s\log\log n +c_n}{\binom{n}{k-j}},$$
where $c_n=o(\log n)$, and let $D_s$ be the number of $j$-sets of degree precisely $s$ in $\cH^k(n,p_s)$ (i.e.\ which lie in $s$ edges). Then we have
\begin{equation}\label{Eq:TVBound}
d_{TV}\left(D_s,\Po \left(\EE\left(D_s\right)\right)\right)=O(n^{-j}(\log n)^{s+1}).
\end{equation}
In particular
\begin{center}
\begin{tabular}{rll}
$(i)$ & $D_s=0$ whp & if $c_n\rightarrow \infty$;\\
$(ii)$ & $D_s \stackrel{d}{\longrightarrow} \Po\left(\frac{j^s e^{-c}}{j!s!}\right)$ & if $c_n\rightarrow c$ \quad for any $c\in \mathbb{R}$;\\
$(iii)$ & $D_s\to \infty$ whp & if $c_n \to -\infty$.
\end{tabular}\end{center}
\end{theorem}

These two theorems together give the following corollary.

\begin{theorem}\label{thm:threshold}
Let $k\ge 3$ and $1\le j \le k-1$, and let $p_0=\frac{j\log n + c_n}{\binom{n}{k-j}}$.
\begin{enumerate}
\item If $c_n\rightarrow -\infty$, then with high probability $\hknp$ contains isolated $j$-sets (and is therefore not $j$-connected).
\item If $c_n\rightarrow \infty$, then with high probability $\hknp$ is $j$-connected (and therefore contains no isolated $j$-sets).
\end{enumerate}
In other words, the properties of being $j$-connected and having no isolated $j$-sets both undergo a (sharp) phase transition at threshold $p_{conn}$, defined as
\[
p_{conn} = \frac{j\log n}{\binom{n}{k-j}}.
\]
\end{theorem}


\subsection{Methods}
The main contribution of this paper is to deduce Theorem~\ref{thm:hittingtime} from Theorem~\ref{thm:poisson}. Attempting to prove this directly using standard techniques generalised from the graph case does not work because $j$-components in a hypergraph may be strangely and non-intuitively distributed. To overcome this problem we quote a powerful result from~\cite{CoKaKo14}, which guarantees one component with a large subset which is in some sense \emph{smoothly distributed}. We then show that whp all non-trivial components are connected to this smooth subset.


\subsection{Notation and definitions}
We introduce a few more definitions before we proceed with the proofs. We fix $k\ge 3$ and $1\le j\le k-1$ for the remainder of the paper. The \emph{order} $|H|$ of a hypergraph $H$ is the number of vertices it contains, while its \emph{size} $e(H)$ is the number of edges. Since a $j$-component consists of $j$-sets of vertices, we may view it as a $j$-uniform hypergraph in which the edges are the $j$-sets in the component. In particular, the size of a $j$-component is the number of $j$-sets it contains. In the remainder of the paper we will use \emph{component} to mean $j$-component.

We will sometimes need to relate the $j$-sets of a component to the edges of the hypergraph which connect them. To allow us to do this, for a $k$-uniform hypergraph $H$ we define the \emph{$j$-size} of $H$ to be the number of $j$-sets contained in edges of $H$.

We ignore floors and ceilings whenever this does not significantly affect the argument.




\section{Contiguity of $\cH^k(n,M)$ and $\cH^k(n,p)$}\label{sec:contiguity}
We need to know that $\hknp$ and $\hknm$ are roughly equivalent, which
is a generalisation of a standard fact about the corresponding graph models
(see \cite{Bolbook,JLRBook}).
In fact, \cite{JLRBook} considers a more general setting than we require here, but what we state is an immediate corollary of the results there (see~\cite{JLRBook}, Corollary~1.16). Let $N=\binom{n}{k}$ and to ease notation, for some property $Q$ we will denote by $\Pr_M(Q)$ the probability that $\hknm$ has property $Q$. $\Pr_p(Q)$ is defined similarly.

\begin{lemma}
Let $Q$ be some monotone increasing property of $k$-uniform hypergraphs and let $M=Np\rightarrow \infty$. Then
\begin{enumerate}\label{lem:monotonecontiguity}
\item $\Pr_p(Q)\rightarrow 1$ implies $\Pr_M(Q)\rightarrow 1$;
\item $\Pr_p(Q)\rightarrow 0$ implies $\Pr_M(Q)\rightarrow 0$.
\end{enumerate}
\end{lemma}
This lemma allows us to transfer properties from $\hknp$ to $\hknm$ (transferring in the other direction is also possible, with some small modifications, but we will not need to do this here). However, this only works for monotonically increasing properties. This is fine for the properties of being $j$-connected or of having no isolated $j$-sets, but in the proof of Theorem~\ref{thm:hittingtime} we will need to consider the probability of having a component of size $r$, for various fixed $r$. This property is not even convex (and nor is its complement) and so for this case we will need some more careful arguments.

The following standard argument allows us to transfer high probability events from the binomial to the uniform model provided that the failure probability is small enough.
\begin{lemma}\label{lem:ptoM}
Let $Q$ be an arbitrary property. Suppose $M\rightarrow \infty$ and $p=M/N \rightarrow 0$. Then
\[
\Pr_M(Q) \le \frac{\Pr_p(Q)}{\Pr(e(\cH^k(n,p))=M)} = \Theta(M^{1/2})\Pr_p(Q).
\]
\end{lemma}

\begin{proof}
The inequality follows from the fact that
\begin{align*}
\Pr_p(Q) & = \sum_{m=0}^N \Pr_m(Q)\Pr(e(\cH^k(n,p))=m)\\
& \ge \Pr_M(Q)\Pr(e(\cH^k(n,p))=M).
\end{align*}
For the equality we use Stirling's approximation to deduce that
\begin{align*}
\Pr(e(\cH^k(n,p))=M) & = \binom{N}{M} p^M (1-p)^{N-M}\\
& =  \Theta (1)\sqrt{\frac{N}{M(N-M)}}\frac{N^N}{M^M (N-M)^{N-M}}p^M (1-p)^{N-M}\\
& = \Theta(M^{-1/2}).
\end{align*}
\vspace{-1.4cm}

\end{proof}




\section{Proof of Theorem~\ref{thm:poisson}}\label{sec:poisson}

Let $C=\binom{k}{j}-1$. Fix an integer $s\ge 0$ and suppose $p=p_s=\frac{j\log n+s\log\log n +c_n}{\binom{n}{k-j}}$, where $c_n=o(\log n).$ Then the expected number of $j$-sets of degree $s$ in $\cH^k(n,p)$ satisfies
\begin{align}
\nonumber\EE(D_s)&=\binom{n}{j}\binom{\binom{n-j}{k-j}}{s}p^s(1-p)^{\binom{n-j}{k-j}-s}\\
\nonumber&=(1+o(1))\frac{n^j}{j!}\frac{\left(\frac{n^{k-j}}{(k-j)!}\right)^s}{s!}p^s \exp\left(-p\binom{n}{k-j}\right)\\
\nonumber&=(1+o(1))\frac{1}{j!s!}e^{s(k-j)\log n- s\log((k-j)!)+s\log p -s\log\log n -c_n}\\
&=(1+o(1))\frac{j^s}{j!s!}e^{-c_n},\label{Eq:Expectation}
\end{align}
since
\begin{align*}
\log p=-(k-j)\log n+\log\log n+\log(j(k-j)!) +O\left(\frac{\log\log n+\left|c_n\right|}{\log n}+\frac{1}{n}\right).
\end{align*}

For the Poisson-approximation we use the Chen-Stein method (see~\cite{BarbourHolstJanson92}). For any $j$-set $J$ we denote its degree in $\cH^k(n,p)$ by $\deg(J)$ and analyse how $D_s$ changes by conditioning on the event $\{\deg(J_0)=s\}$ for an arbitrary  $j$-set $J_0$. 

 First we construct $\cH^k(n,p)$ and denote by $E_0$ the set of edges containing $J_0$, then we distinguish three cases:
\begin{enumerate}[(a)]
\item If $\deg(J_0)<s$, add $s-\deg(J_0)$ distinct $k$-sets chosen uniformly at random from $\left\{K\in \binom{V}{k}\cond J_0\subset K\right\}\setminus E_0$ to the hypergraph;
\item If $\deg(J_0)=s$, do nothing;
\item If $\deg(J_0)>s$, delete a set of $\deg(J_0)-s$ edges chosen uniformly at random from $E_0$.
\end{enumerate}
We denote the resulting hypergraph by $\cH^*=\cH^*(J_0)$. For any $j$-set $J$ we write $\deg^*(J)$ for its degree in $\cH^*$ and $D_s^*(J_0)$ for the number of $j$-sets $J\neq J_0$ such that $\deg^*(J)=s$. Furthermore observe that this construction provides a coupling of $\cH^k(n,p)$ and $\cH^*$ such that removing all edges containing $J_0$ in either one of them yields the same random hypergraph $\cH^-=\cH^-(J_0)$.  For any $j$-set  $J$ we write $\deg^-(J)$ for its degree in $\cH^-$. 

We use the following form of the Chen-Stein approximation given by Theorem~1.B in~\cite{BarbourHolstJanson92}.
\begin{theorem}[Chen-Stein approximation \cite{BarbourHolstJanson92}]\label{thm:chen-stein}
Given a finite index set $\cI$ and a random variable  $W=\sum_{i\in \cI} Z_i$, where $Z_i$ is a Bernoulli random variable with parameter $p_i\in [0,1]$, denote by $\lambda=\sum_{i\in \cI} p_i$ the expectation of $W$. Assume that for each $i\in \cI$ there is a pair of coupled random variables $(U_i,V_i)$ such that $U_i$ has the distribution of $W$ and $V_i+1$ has the distribution of $W$ conditioned on $\{Z_i=1\}$. Then we have 
\begin{align*}
d_{TV}\big(W,\Po(\lambda)\big)&\leq \min\{1,\lambda^{-1}\}\sum_{i\in \cI}p_i\EE\left(\left|U_i-V_i\right|\right).
\end{align*}
 \end{theorem}
For the proof of Theorem~\ref{thm:poisson}, we let $\cI$ be the set of all $j$-sets and for all $J$ let\linebreak[4] $Z_J=\Ind{\deg(J)=S}$, $p_{J}=\Pr\left(\deg(J)=s\right)$, $U_{J}=W=D_s$ and $V_{J}=D_s^*(J_0)$. We observe that $\cH^*$ has the same distribution as $\cH$ conditioned on the event $\{\deg(J_0)=s\}$, so $V_J$ has the same distribution as $W$ conditioned on $\{Z_{J_0}=1\}$.

Now applying Thoerem~\ref{thm:chen-stein} and using the upper bound $\min\left\{1,\frac{1}{\EE(D_s)}\right\}\le \frac{1}{\EE(D_s)}$, we obtain
\begin{align}
d_{TV}\big(D_s,\Po(\EE(D_s))\big)&\leq \frac{\sum_{J}\Pr\left(\deg(J)=s\right)\EE\left(\left|D_s-D_s^*(J_0)\right|\right)}{\EE\left(D_s\right)}=\EE\left(\left|D_s-D_s^*(J_0)\right|\right).\label{Eq:ChenSteinBound}
\end{align}
Hence it suffices to estimate the random variable $\left|D_s-D_s^*(J_0)\right|.$
We first observe that
\begin{align*}
|D_s-D_s^*(J_0)| & = \Ind{\deg (J_0)=s} + \sum_{J\neq J_0} |\Ind{\deg(J)=s}-\Ind{\deg^*(J)=s}|\\
& \le \Ind{\deg(J_0)=s} +\sum_{t=1}^{s}\sum_{\substack{J \neq J_0\\ \deg^*(J)>\deg(J)}}\Ind{\deg(J_0)=s-t}\,\\
& \hspace{5cm} + \hspace{-0.2cm} \sum_{t=1}^{\binom{n-j}{k-j}-s}\sum_{\substack{J \neq J_0\\
\deg^*(J)< \deg(J) \\ \deg^-(J)\le s}} \hspace{-0.2cm} \Ind{\deg(J_0)=s+t}. 
\end{align*}
To justify the inequality, first note that if $\deg (J_0)=s$, then $\cH=\cH^*$ and only the first term contributes.
Furthermore, if $\deg(J_0)<s$, say $\deg(J_0)=s-t$ for some $t\in[1,s]$, then the only contribution to $\left|D_s-D_s^*(J_0)\right|$ comes from
$j$-sets $J\neq J_0$ whose degree increased, i.e.\ $\deg^*(J)>\deg(J)$.
Similarly, if $\deg(J_0)=s+t$ for some $t\in\big[1,\binom{n-j}{k-j}-s\big]$, observe that for a $j$-set $J$ to contribute it is necessary
to have either $\deg(J)=s$ or $\deg^*(J)=s$. Note that these cannot hold unless $\deg^-(J)\le s$, and we will simply bound the probability of this (more likely) event.



Moreover, each inner sum has at most $Ct$ terms, since we certainly only sum over $j$-sets $J$ whose degree has changed, and adding or deleting an edge influences the degree of at most $C$ $j$-sets (other than $J_0$).



Note also that $\deg^-(J)$ has distribution
\[
\Bin \left(\binom{n-j}{k-j}-\binom{n-|J_0\cup J|}{k-|J_0\cup J|},p\right),
\]
independently of $\deg(J_0)$, and the probability that $\deg^-(J)\le s$ is maximised when $|J_0\cup J|$ is minimised. Hence for an upper bound we will assume that $|J_0\cup J|=j+1$. This motivates the definition
\begin{align*}
q&=\Pr\left(\Bin \left(\widetilde{N},p\right)\le s\right),
\end{align*}
where $\widetilde{N}=\binom{n-j}{k-j}-\binom{n-j-1}{k-j-1}=(1+o(1))\binom{n}{k-j}$. Combining these two arguments we obtain the upper bound
\begin{align*}
\left|D_s-D_s^*(J_0)\right|\leq\Ind{\deg(J_0)=s} &+\sum_{t=1}^{s}\Ind{\deg(J_0)=s-t}\, Ct+ \hspace{-0.2cm} \sum_{t=1}^{\binom{n-j}{k-j}-s} \hspace{-0.2cm} \Ind{\deg(J_0)=s+t}\Bin(Ct,q).
\end{align*}
Therefore, using the notation $x^+= \max\{x,0\}$ for any $x\in \mathbb{R}$, we have
\begin{align}\label{Eq:TVError}
\hspace{-0.2cm}
\EE\left(\left|D_s-D_s^*(J_0)\right|\right)& \leq \Pr\left(\deg(J_0)=s\right)+C\EE\left(\left(s-\deg(J_0)\right)^+\right)
 +Cq\EE\left(\left(\deg(J_0)-s\right)^+\right).
\end{align}
We can estimate both probabilities in \eqref{Eq:TVError} using
\begin{align*}
\Pr\left(\deg(J_0)=s\right) \le q & = \sum_{i=0}^s \binom{\widetilde{N}}{i}p^i(1-p)^{\widetilde{N}-i}\\
& \le O(1) \big( \widetilde{N}p\big)^s \exp \big(-\widetilde{N}p\big)\\
& =O((\log n)^s n^{-j}),
\end{align*}
where the second and third lines follow because $s$ is bounded.
Moreover, we have 
\begin{align*}
\EE\left(s-\deg(J_0)\right)^+\leq s\,\Pr\left(\deg(J_0)\le s\right)\le sq=O((\log n)^s n^{-j})
\end{align*}
and furthermore
\begin{align*}
\EE\left(\deg(J_0)-s\right)^+\leq \EE(\deg(J_0))+s=O(\log n).
\end{align*}
Therefore~\eqref{Eq:ChenSteinBound} and~\eqref{Eq:TVError} provide~\eqref{Eq:TVBound}, i.e.\ 
\begin{equation}
d_{TV}\left(D_s,\Po\left(\EE\left(D_s\right)\right)\right)=O(n^{-j}(\log n)^{s+1}).
\end{equation}
Now assume $\lim_{n\to\infty}c_n= c$. By \eqref{Eq:Expectation} we know that $\EE\left(D_s\right)\to \frac{j^s e^{-c}}{j!s!}$ and by the continuity in $\lambda$ of the function $\Pr(\Po(\lambda)=i)$ for each $i$
$$
\Po\left(\EE\left(D_s\right)\right)\stackrel{d}{\longrightarrow}\Po\left(\frac{j^s e^{-c}}{j!s!}\right),
$$
hence by the triangle inequality and \eqref{Eq:TVBound}, case~$(ii)$ in the second claim follows. Cases~$(i)$ and~$(iii)$ can be easily deduced from case~$(ii)$.



\section{Proof of Theorem~\ref{thm:hittingtime}}\label{sec:hittingtime}

The proof which we present is largely elementary except for the use of Theorem~\ref{thm:poisson}, which relies on Theorem~\ref{thm:chen-stein}, and one powerful result from~\cite{CoKaKo14} (Lemma~\ref{lem:smoothsubset} below). This result is stated for a much smaller probability than we have in this setting, which is therefore not the optimal range for its application, but nevertheless it will turn out to be strong enough.

We first collect two preliminary results which we will need later (Corollary~\ref{cor:smoothsubset} and Proposition~\ref{prop:structurecount} below).

\subsection{Smooth subset}
The following result from~\cite{CoKaKo14} will be key.
\begin{lemma}\label{lem:smoothsubset}
Suppose $n^{-1/3} \ll \eps \ll 1$ and
let $p^*=\frac{1+\eps}{\left(\binom{k}{j}-1\right)\binom{n}{k-j}}$. Then whp there is a $j$-component of $\cH^k(n,p^*)$ with a subset $S$ of at least $\eps^3 n^j$ $j$-sets satisfying the following property:
\begin{center}
\parbox{10cm}{
Every $(j-1)$-set of vertices in $\cH^k(n,p^*)$ is contained in $(1\pm o(1))\frac{|S|}{\binom{n}{j}}n$ $j$-sets of $S$.
}
\end{center}
\end{lemma}
In other words, we can find a reasonably large subset $S$ of a component which is \emph{smooth} in the sense that all $(j-1)$-sets are in about the ``right'' number of $j$-sets of $S$.
More precisely, we say that a set $S$ of $j$-sets is \emph{smooth} if every
$(j-1)$-set is contained in $(1\pm o(1))\frac{|S|}{\binom{n}{j}}n$ $j$-sets of $S$.

We note that Lemma~\ref{lem:smoothsubset} is not stated explicitly in this form
in~\cite{CoKaKo14}, but is implicit in the proof. We therefore give a brief outline
of how it can be deduced from the results in that paper. The casual reader who is
unfamiliar with~\cite{CoKaKo14} may skip the following proof.

\begin{proof}
Starting from
some $j$-set $J$, we explore the $j$-component containing $J$ using a
breadth-first search process BFS($J$). This partitions the $j$-sets of the
$j$-component into \emph{generations}, which can be numbered according to the
order they were discovered in.

We fix a starting $j$-set $J$ which lies in the largest component of $\cH^k(n,p)$, let
$\partial C_g$ denote the $g$-th generation of this search process BFS($J$), and
$C_g=\cup_{g'\le g} \partial C_{g'}$.
Then there are generations $g_0$ and $g_1$ such that the following statements hold whp.

\begin{enumerate}
\item \label{prop:stopconds} Either $|\partial C_{g_1}|\ge \eps^3 n^j$ or $|C_{g_1}| \ge \eps^{3/2}n^j$;
\item \label{prop:smallstart} $|C_{g_0}|= o(|C_{g_1}|)$ (and in particular $g_0 < g_1$);
\item \label{prop:smoothgens} Every generation
$\partial C_g$ with $g_0\le g \le g_1$ is smooth.
\end{enumerate}

We set $g_0=i_1(j-1)$, where $i_1(j-1)$ is defined immediately before Lemma~16 in~\cite{CoKaKo14}, and set $g_1=i_1$, where $i_1$ is defined in~\cite{CoKaKo14} to be the generation at which one of three stopping conditions (S1), (S2) or (S3) is invoked (see Section~5.4 of~\cite{CoKaKo14}). These stopping conditions contain a parameter $\lambda$, which we choose to be $\lambda=\eps^{3/2}$.

Property~\eqref{prop:stopconds} follows from these stopping conditions.
We use here the fact that $J$ is in the largest component of $\cH^k(n,p)$, which is a giant component whp by Theorem~2 of~\cite{CoKaKo14}, therefore whp either (S2) or (S3) is invoked at time $i_1$ (as (S2) would be invoked before (S1)).

Property~\eqref{prop:smallstart} follows from Lemmas~10, 24 and~25 in~\cite{CoKaKo14}.
More precisely, whp $g_0=i_1(j-1)=i_0(j-1)+O(\log n)$, while
$g_1 = i_1 \ge i_0(j-1)+\Omega(\eps^{-1}\log n)$ by Lemma~25 of~\cite{CoKaKo14}.
Furthermore, whp $|C_{i_0(j-1)}|=o(\eps^{3/2}n^j)$ by Lemma~24 of~\cite{CoKaKo14} applied
with $\ell=0$. Finally, by  Lemma~10 of~\cite{CoKaKo14}, whp the generations between
$g_0$ and $g_1$ are at least as large as those between $i_0(j-1)$ and $g_0$, and there
are significantly more of them ($\Omega (\eps^{-1}\log n)$ compared to $O(\log n)$).

Finally, Property~\eqref{prop:smoothgens} is given by Lemma~16 in~\cite{CoKaKo14} (with $\ell=j-1$ and using the fact that $i_1\ge i_1(j-1)$).



We now use these three properties to prove the existence of the set $S$. We make a case distinction based on Property~\eqref{prop:stopconds}. If $|\partial C_{g_1}|\ge \eps^3 n^j$, then we simply set $S=\partial C_{g_1}$, and $S$ is smooth by~\eqref{prop:smoothgens}.

On the other hand, if $|C_{g_1}| \ge \eps^{3/2}n^j$, then we let $S=C_{g_1}\setminus C_{g_0-1}$.
Then since every generation from $g_0$ to $g_1$ is smooth, and since a union of
smooth sets is also smooth, we have that $S$ is smooth. Furthermore,
$|S|=(1-o(1))|C_{g_1}| \ge \eps^3 n^j$.
\end{proof}



Lemma~\ref{lem:smoothsubset} has the following corollary which we will apply later.

\begin{corollary}\label{cor:smoothsubset}
Suppose $n^{-1/3} \ll \eps \ll 1$ and
$p\ge\frac{1+\eps}{\left(\binom{k}{j}-1\right)\binom{n}{k-j}}$.
Then
$\cH^k(n,p)$ has a $j$-component containing a set $S$ of size at least $\eps^3 n^j$ such that every $(j-1)$-set is contained in $(1\pm o(1))\frac{|S|}{\binom{n}{j}}n$ $j$-sets of $S$.
\end{corollary}
\begin{proof}
We set
$p^*=\frac{1+\eps}{\left(\binom{k}{j}-1\right)\binom{n}{k-j}}$ and
 $p'= \frac{p-p^*}{1-p^*}$ and let $\cH_1= \cH(n,p^*)$ and $\cH_2=\cH(n,p')$ independently. Observe that we may couple in such a way that $\cH^k(n,p) = \cH_1\cup \cH_2$. Furthermore, by Lemma~\ref{lem:smoothsubset}, whp $\cH_1$ has a component containing a smooth set $S$ of the appropriate size. In $\cH^k(n,p)$ this component may be bigger than in $\cH_1$, but certainly still contains $S$.
\end{proof}



\subsection{Well-constructed hypergraphs}

We will also use the following proposition. We say that a hypergraph is $\emph{well-constructed}$ if it can be generated from an initial $j$-set via a search process, i.e.\ by successively adding edges such that each edge contains at least one previously discovered $j$-set and also contains at least one previously undiscovered $j$-set.


\begin{proposition}\label{prop:structurecount}
Up to isomorphism, the number of well-constructed $k$-uniform hypergraphs of $j$-size $s$ is at most $2^{ks^2}$.
\end{proposition}


\begin{proof}
We explore the hypergraph by adding the edges one by one in the order in which it is well-constructed. The resulting hypergraph is uniquely determined, up to isomorphism, by the intersection of each edge with the previous vertices (though we will multiple count the isomorphism classes, this is permissible for an upper bound). When adding the $i$-th edge, we certainly have at most $(i-1)k$ vertices so far, and so the number of possible intersections is at most $2^{(i-1)k}$. Multiplying over all edges, of which there are certainly at most $s$ (each edge gives at least one new $j$-set), we have that the number of such hypergraphs is at most $2^{\sum_{i=1}^s(i-1)k} \le 2^{ks^2}$.
\end{proof}

\subsection{Hitting time}


We now proceed with the proof of Theorem~\ref{thm:hittingtime}. Let us consider any $p,M$ satisfying
\[
\frac{j\log n - \omega}{\binom{n}{k-j}}\le p =M/N \le \frac{j\log n + \omega}{\binom{n}{k-j}}
\]
where $\omega=\log \log n$. We apply Theorem~\ref{thm:poisson} (with $s=0$ and $c_n=\pm \omega$) and Lemma~\ref{lem:monotonecontiguity} to observe that in both $\cH^k(n,p)$ and $\cH^k(n,M)$, whp there are isolated $j$-sets at the lower end of this range but not at the upper end. We will now prove that other than these isolated $j$-sets, there is just one very large component whp. We certainly know by Corollary~\ref{cor:smoothsubset} that there is a component containing a large smooth set $S$. For the rest of the proof we fix this component and the set $S$.

We consider the possibility that there is a second non-trivial component containing $r$ $j$-sets, and make a case distinction on the size of $r$.
Note that for any $j$-component of size $r$ in a $k$-uniform hypergraph, there is a well-constructed subhypergraph of every (up to a constant $\binom{k}{j}$ error) $j$-size up to $r$. (More precisely, for any integer $r'\le r$ there exists an integer $r''$ with $|r''-r'|\le \binom{k}{j}$ and a well-constructed subhypergraph of $j$-size $r''$.) 

Let us set $\omone=\log \log n$.

\smallskip

\noindent \textbf{Case 1:} $2\le r \le \omone$.
We first observe that in a component of size $r \ge 2$ we must have at least one edge, and therefore at least $\binom{k}{j} \ge k \ge 3$ $j$-sets, i.e. we automatically have $r\ge 3$.

We show that the expected number of components of size $r$ is very small and apply Markov's inequality. Any component of size $r$ can be associated with a well-constructed hypergraph $H$ of $j$-size $r$ which is isolated from the remaining $j$-sets of $\hknp$. Then $e(H)\le r$ and furthermore $|H|\le j+(k-j)e(H)$, since each new edge of $H$ gives at most $k-j$ new vertices. For each $j$-set of $H$, we have at least $\binom{n-j}{k-j}-r\binom{n-j-1}{k-j-1}$ non-edges (any $k$-set containing this $j$-set but no other $j$-sets of $H$). Thus the expected number of isolated copies of $H$ in $\cH^k(n,p)$ satisfies
\begin{equation}\label{eq:expH}
\EE (X_H) \le n^{j+(k-j)e(H)}p^{e(H)}(1-p)^{r\left(\binom{n-j}{k-j}-r\binom{n-j-1}{k-j-1}\right)}
\end{equation}
and so
\begin{align*}
\log(\EE (X_H)) \le \; & \left(j+(k-j)e(H)\right)\log n+O(r\log \log n) \\
& \hspace{0.5cm}- (k-j)e(H)\log n -(1-O(r/n)-O(\omega/\log n))rj\log n\\
= \; & (1-r+o(1))j\log n \le (-3rj/5)\log n.
\end{align*}
Note that this bound does not depend on the specific structure of $H$, only on the number of $j$-sets $r$. Let $X_r$ be the number of components of size $r$. Then by Proposition~\ref{prop:structurecount} we have
\[
\EE (X_r) \le 2^{kr^2} n^{-3rj/5} \le n^{-4rj/7}
\]
where for the last inequality we use the fact that $r\le \omone = o(\log n)$.

By taking a union bound over all $3\le r \le \omone$, we conclude that with probability at least $1-2n^{-12j/7}$ there are no $j$-components of this size.

\smallskip

\noindent \textbf{Case 2:} $r \ge \omone$.

In this case, rather than looking at the full component we look at a well-constructed subgraph $H$ of $j$-size $\omone$. Such a subgraph certainly exists up to an additive $\binom{k}{j}$ error term in the $j$-size, which will not affect calculations significantly.
Most of the calculations which lead to~\eqref{eq:expH} are still valid, replacing $r$ by $\omone$. However, since we are no longer considering a full component, we must be more careful about the number of non-edges.

At this point we make use of the set $S$ of $j$-sets guaranteed by
Corollary~\ref{cor:smoothsubset}, which lie in a different component to $H$.
For each of the $\omone$ $j$-sets of $H$, pick an arbitrary $(j-1)$-set
within it and by Corollary~\ref{cor:smoothsubset}, this $(j-1)$-set is contained
in $(1\pm o(1))\eps^3 n$ $j$-sets of $S$. For each such pair of $j$-sets
intersecting in $j-1$ vertices, there are $\binom{n-j-1}{k-j-1}$ $k$-sets
containing both of them, all of which must be non-edges, since the $j$-sets
lie in different components.

It may be that we multiple count the non-edges in this way. However, each $k$-set may only be counted from a pair of $j$-sets it contains, and therefore the number of times it is counted is certainly at most $\binom{k}{j}(k-j)$. Thus in total the number of non-edges is at least
\[
\frac{\omone \eps^3 n}{2\binom{k}{j}(k-j)} \binom{n}{k-j-1} = \Theta\left(\omone\eps^3 n^{k-j}\right).
\]
We may thus calculate the expected number of such structures $H$ (cf.~\eqref{eq:expH}):
\[
\EE (X_H) \le n^{j+(k-j)e(H)}p^{e(H)}(1-p)^{\Theta(\omone \eps^3 n^{k-j})}
\]
and so, letting $Y$ be the number of such well-constructed hypergraphs of $j$-size $\omone$ which are not in the same component as $S$, we have
\begin{align*}
\log(\EE (Y)) & \le k\omone^2\log 2 + j\log n+O\left(\omone \log \log n \right) - \Theta\left(\omone \eps^3 \log n\right).
\end{align*}
Now observe that in Corollary~\ref{cor:smoothsubset} we may choose any $n^{-1/3} \ll \eps \ll 1$. Choosing $\eps^3=\frac1{\log \log \log n}$, we have $\omone \eps^3 \to \infty$ and the last term in the above inequality dominates, and we have $\log(\EE(Y)) \le -C\log n$ for any constant $C$. In particular, choosing $C=12j/7$, we have $\EE(Y)\le n^{-12j/7}$. By Markov's inequality, this implies that with probability at least $1-n^{-12j/7}$ we have $Y=0$ and therefore no further components of size $r$.

Combining the two cases, this tells us that with probability at least $1-3n^{-12j/7}$, $\cH^k(n,p)$ only has one non-trivial component.

Finally note that $M=pN = \Theta(n^j\log n)$. Thus by Lemma~\ref{lem:ptoM} we conclude that with probability at least $1-3n^{-12j/7}\sqrt{M} = 1-o(n^{-8j/7})$, $\cH^k(n,M)$ also has only one non-trivial $j$-component.



We now take a union bound over all possible $M$, of which there are at most $\frac{2\omega}{\binom{n}{k-j}}\binom{n}{k}=O(\omega n^j)$, and deduce that the probability that there is ever a second non-trivial within this time period is at most
\[
O(\omega n^j)n^{-8j/7} = O(\omega n^{-j/7}) = o(1)
\]
as required.

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

Theorem~\ref{thm:threshold} follows almost immediately from Theorems~\ref{thm:hittingtime} and~\ref{thm:poisson}.
In order to apply Theorem~\ref{thm:hittingtime} in the binomial model, we apply the standard trick of birth times: to each $k$-tuple we assign a number (the \emph{birth time}) between $0$ and $1$ uniformly at random and independently of all other $k$-tuples. Then the hypergraph process $\process$ can be obtained by adding edges in increasing order of birth time (with probability $1$ no two edges have the same birth time), while the hypergraph obtained by taking all edges with birth time at most $p$ is distributed as $\cH^k(n,p)$.

Theorem~\ref{thm:chen-stein} (with $s=0$) tells us that if $c_n\to \infty$, then whp there are no isolated $j$-sets, and therefore Theorem~\ref{thm:hittingtime} tells us that whp the hypergraph is $j$-connected. This proves part~(2). Part~(1) is simply an application of Theorem~\ref{thm:poisson} with $s=0$.




\section{Concluding remark}
In~\cite{Poole14}, it is determined for the case $j=1$ that the hitting time for \emph{d-strong} $1$-connectedness, i.e.\ the time at which the hypergraph first has the property that deleting any set of less than $d$ vertices still leaves a $1$-connected hypergraph, is the same as the hitting time for having no vertices of degree less than $d$ whp. It would be interesting to generalise this result to $d$-strong $j$-connectedness (removing fewer than $d$ $j$-sets still leaves a $j$-connected hypergraph), which is presumably attained whp when every $j$-set has degree at least $d$. However, this would present significant additional difficulties, not least that Lemma~\ref{lem:smoothsubset} would no longer give the substructure which we require.

\section{Acknowledgement}

The authors would like to thank an anonymous referee for detailed feedback which greatly improved the quality of the manuscript.




\begin{thebibliography}{1}

\bibitem{BarbourHolstJanson92}
A.~D. Barbour, L.~Holst, and S.~Janson.
\newblock {\em Poisson approximation}, volume~2 of {\em Oxford Studies in
  Probability}.
\newblock The Clarendon Press, Oxford University Press, New York, 1992.
\newblock Oxford Science Publications.

\bibitem{Bolbook}
B.~Bollob{\'a}s.
\newblock {\em Random graphs}, volume~73 of {\em Cambridge Studies in Advanced
  Mathematics}.
\newblock Cambridge University Press, Cambridge, second edition, 2001.

\bibitem{BT85}
B.~Bollob{\'a}s and A.~Thomason.
\newblock Random graphs of small order.
\newblock In {\em Random graphs '83 ({P}ozna\'n, 1983)}, volume 118 of {\em
  North-Holland Math. Stud.}, pages 47--97. North-Holland, Amsterdam, 1985.

\bibitem{CoKaKo14}
O.~Cooley, M.~Kang, and C.~Koch.
\newblock The size of the giant component in random hypergraphs.
\newblock submitted. Preprint:
\arxiv{1501.07835}

\bibitem{JLRBook}
S.~Janson, T.~{\L}uczak, and A.~Ruci\'nski.
\newblock {\em Random graphs}.
\newblock Wiley-Interscience Series in Discrete Mathematics and Optimization.
  Wiley-Interscience, New York, 2000.

\bibitem{KP16}
M.~Kahle and B.~Pittel.
\newblock Inside the critical window for cohomology of random {$k$}-complexes.
\newblock {\em Random Structures Algorithms}, 48(1):102--124, 2016.

\bibitem{Poole14}
D.~Poole.
\newblock On the strength of connectedness of a random hypergraph.
\newblock {\em Electron. J. Combin.}, 22(1):Paper 1.69, 16, 2015.

\end{thebibliography}



\end{document}