% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \numberwithin{equation}{section} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins \newcommand{\whp}{with high probability} \newcommand{\V}{\mathcal{V}} \newcommand{\W}{\mathcal{W}} \newcommand{\Po}[1]{\textrm{Po}\left(#1\right)} \newcommand{\Bin}[2]{\textrm{Bin}\left(#1,#2\right)} \newcommand{\EE}{\mathbb{E}} \newcommand{\Var}{{\rm Var}} \newcommand{\coupling}{\preceq} \newcommand{\coup}{\preceq_{1-o(1)}} \newcommand{\Pra}[1]{\Pr\left\{#1\right\}} \newcommand{\Gn}[1]{G_2\left(n,#1\right)} \newcommand{\Gh}[1]{G_3\left(n,#1\right)} \newcommand{\Gnm}[2]{\mathcal{G}_{#1}\left(n,m,#2\right)} \newcommand{\Gnmp}{\mathcal{G}\left(n,m,\overline{p}\right)} \newcommand{\Gnmpp}{\mathcal{G}\left(n,m,p\right)} \newcommand{\Gnmprim}[1]{\mathcal{G}\left(n,#1,p\right)} \newcommand{\G}[2]{\mathbb{G}_{*#1}\left(n,#2\right)} \newcommand{\Gsuma}{\Gn{\hat{p}_2}\cup\Gh{\hat{p}_3}} \newcommand{\pdwa}{\hat{p}_2} \newcommand{\ptrzy}{\hat{p}_3} \newcommand{\phat}{\hat{p}} \newcommand{\Gdelta}{\rg(n)_{\delta\ge k}} \newcommand{\rg}{\mathbb{G}} % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}{Lemma}[section] \newtheorem{corollary}{Corollary}[section] \newtheorem{proposition}{Proposition}[section] %\newtheorem{fact}{Fact}[section] %\newtheorem{observation}{Observation}[section] %\newtheorem{claim}{Claim}[section] \theoremstyle{definition} %\newtheorem{definition}{Definition}[section] %\newtheorem{example}[theorem]{Example} %\newtheorem{conjecture}[theorem]{Conjecture} %\newtheorem{open}[theorem]{Open Problem} %\newtheorem{problem}[theorem]{Problem} %\newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}{Remark}[section] %\newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf The coupling method for\\ inhomogeneous random intersection graphs } % 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{Katarzyna Rybarczyk\thanks{Supported by National Science Center grant DEC--2011/01/B/ST1/03943.}\\ \small Adam Mickiewicz University\\[-0.8ex] \small ul.Umultowska 87, \\[-0.8ex] \small 61-614 Pozna\'{n}, Poland\\ \small\tt kryba@amu.edu.pl\\ } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{XX}{XX}\\ \small Mathematics Subject Classifications: 05C80,60C05} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} We present new results concerning threshold functions for a wide family of random intersection graphs. To this end we improve and generalize the coupling method introduced for random intersection graphs so that it may be used for a wider range of parameters. Using the new approach we are able to tighten the best known results concerning random intersection graphs and establish threshold functions for some monotone properties of inhomogeneous random intersection graphs. Considered properties are: $k$-connectivity, matching containment and hamiltonicity. \end{abstract} \section{Introduction}\label{Introduction} Since their introduction by Karo\'{n}ski, Scheinerman, and Singer--Cohen \cite{GpSubgraph} random intersection graphs have been attracting attention due to their interesting structure and wide applications. The random intersection graph model appears in problems concerning for example ``gate matrix layout" for VLSI design (see e.g. \cite{GpSubgraph}), cluster analysis and classification (see e.g. \cite{RIGGodehardt1}), analysis of complex networks (see e.g. \cite{RIGClustering2, RIGTunableDegree}), secure wireless networks (see e.g. \cite{WSNphase2}) or epidemics (\cite{GpEpidemics}). Several generalizations of the model have been proposed, mainly in order to adapt it to use for specific purposes. In this paper we consider the $\Gnmp$ model studied for example in \cite{Gppdistance,GppDegrees, GppPhaseTransition, SpirakisNiezalezne}. Alternative ways of generalizing the model defined in \cite{GpSubgraph} are given for example in \cite{RIGTunableDegree} and \cite{RIGGodehardt1}. In a random intersection graph $\Gnmp$ there is a set of $n$ vertices $\V=\{v_1,\ldots,v_n\}$, an auxiliary set of $m=m(n)$ features $\W=\{w_1,\ldots,w_{m(n)}\}$, and a vector $\overline{p}=\overline{p}(n)=(p_1,\ldots,p_{m(n)})$ such that $p_i\in (0,1)$, for each $1\le i\le m$. To each vertex $v\in\V$ we attribute a set of its features $W(v)\subseteq \W$ such that for each $i$, $1\le i\le m$, $w_i\in W(v)$ with probability $p_i$ independently of all other features and vertices. If $w\in W(v)$ then we say that $v$ {\em has chosen }$w$. Any two vertices $v,v'\in\V$ are connected by an edge in $\Gnmp$ if $W(v)$ and $W(v')$ intersect. If $\overline{p}(n)=(p,\ldots,p)$ for some $p\in (0,1)$ then $\Gnmp$ is a random intersection graph defined in \cite{GpSubgraph}. We denote it by $\Gnmpp$. The random intersection graph model is very flexible and its properties change a lot if we alter the parameters. For example $\Gnmpp$ for some ranges of parameters behaves similarly to a random graph with independent edges (see \cite{GpEquivalence, GpEquivalence2}) but in some cases it exhibit large dependencies between edge appearance (see for example \cite{GpSubgraph,GpSubgraphPoisson}). It was proved in \cite{GpCoupling} that in both cases $\Gnmpp$ may be coupled with a random graph with independent edges so that with probability tending to $1$ as $n\to\infty$, a graph with independent edges is a subgraph of $\Gnmpp$. It is also explained how this coupling may be used to obtain sharp results on threshold functions for $\Gnmpp$. Such properties as connectivity, a Hamilton cycle containment or a matching containment are given as examples. In general, the coupling technique provides a very elegant method to obtain bounds on threshold functions for random intersection graphs for a large class of properties. The result presented in \cite{GpCoupling} is not tight for some values of $n$, $m$ and $p$. Therefore it cannot be generalized in a straightforward manner to $\Gnmp$ with arbitrary $\overline{p}(n)$. In particular the method does not give sharp results for $np$ tending to a constant. In this article we modify and extend the techniques used in \cite{GpCoupling} in order to overcome these constraints. First of all, to get the general result of this paper, we couple $\Gnmp$ with an auxiliary random graph which does not have fully independent edges. Therefore we need to prove some additional facts about the auxiliary random graph model. Moreover we need tight bounds on the minimum degree threshold function for $\Gnmp$. Due to edge dependencies, estimation of moments of the random variable counting vertices with a given degree in $\Gnmp$ is complicated. Therefore we suggest a different approach to resolve the problem. We divide $\Gnmp$ into subgraphs so that the solution of a coupon collector problem combined with the method of moments provide the answer. The new approach to the coupling method allows us to obtain better results on threshold functions for $\Gnmpp$ and through those means resolve open problems unresolved in \cite{GpCoupling}. In conclusion, we provide a general method to establish bounds on threshold functions for many properties for $\Gnmp$. By means of the method we are able to obtain sharp thresholds (for definition of a sharp threshold see Section 1.6 in \cite{KsiazkaJLR}) for $k$--connectivity, perfect matching containment and hamiltonicity for the general model. Last but not least we considerably improve known results concerning $\Gnmpp$. All limits in the paper are taken as $n\rightarrow \infty$. Throughout this paper we use the standard asymptotic notation $o(\cdot)$, $O(\cdot)$, $\Omega(\cdot)$, $\Theta(\cdot)$, $\sim$, $\ll$, and $\gg$ defined as in \cite{KsiazkaJLR}. By $\Bin{n}{p}$ and $\Po{\lambda}$ we denote the binomial distribution with parameters $n$, $p$ and the Poisson distribution with expected value $\lambda$, respectively. We also use the phrase ``{\whp}'' to say with probability tending to one as $n$ tends to infinity. All inequalities hold for $n$ large enough. If it does not influence the reasoning, for clarity we omit $\lfloor\cdot\rfloor$ and $\lceil\cdot\rceil$. \section{Main Results}\label{SectionTwierdzenie} In the article we compare random intersection graph $\Gnmp$ with a union of a random graph with independent edges $G_2(n,\phat_2)$ and a random graph $G_3(n,\phat_3)$ constructed on the basis of a random 3--uniform hypergraph with independent hyperedges. Generally, for any \linebreak $\phat=\phat(n)\in [0,1]$ and $i=2,\ldots,n$, let $H_i(n,\phat)$ be an $i$--uniform hypergraph with the vertex set $\V$ in which each $i$--element subset of $\V$ is added to the hyperedge set independently with probability $\phat$. $G_i(n,\phat)$ is a graph with the vertex set $\V$ and $\{v,v'\}$, $v,v'\in\V$, is an edge in $G_i(n,\phat)$ if there exists a hyperedge in $H_i(n,\phat)$ containing $v$ and $v'$. Before we present the main results of this paper, we introduce some additional notations which will be used repeatedly. Then we will give an intuitive description of the introduced quantities. This might help understand the main ideas behind the theorems. Let $\overline{p}=(p_1,\ldots,p_m)$ be such that $p_i\in (0,1)$, for all $1\le i\le m$. We will use the following quantities \begin{equation}\label{RownanieS} \begin{split} S_1&=\sum_{i=1}^{m}np_i\left(1-(1-p_i)^{n-1}\right);\\ S_2&=\sum_{i=1}^{m}np_i\left(1-\frac{1-(1-2p_i)^{n}}{2np_i}\right);\\ S_3&=\sum_{i=1}^{m}np_i\left(\frac{1-(1-2p_i)^{n}}{2np_i}-(1-p_i)^{n-1}\right);\\ S_{1,t}&=\sum_{i=1}^{m}t\binom{n}{t}p_i^t(1-p_i)^{n-t}, \text{ for }t=2,3,\ldots,n. \end{split} \end{equation} By definition, the edge set of $\Gnmp$ is a union of edge sets of $m$ cliques. The $i$--th clique, $1\le i\le m$, consists of all the vertices which have chosen feature $w_i$. We will say that these cliques {\it are forming} $\Gnmp$. The size of the $i$--th clique forming $\Gnmp$, $1\le i\le m$, has binomial distribution $\Bin{n}{p_i}$. Moreover cliques (not only their sizes) are independent. Replacing edge sets of cliques forming $\Gnmp$ by sets of (to some extent independent) edges will be the key idea used in the coupling constructed in the proof of Theorem~\ref{LematCoupling}. The quantity $S_1$ is the expected value of the sum of sizes of these cliques forming $\Gnmp$ which contain at least two vertices. This value, among others, will be crucial in determining the number of isolated vertices in $\Gnmp$. This is because a vertex in $\Gnmp$ is isolated if and only if it is not contained in any of the cliques of size at least~2. $S_2$ is the expected value of the sum of sizes of all cliques forming $\Gnmp$ minus the number of cliques of odd size. $S_3$ is the expected value of the number of cliques of odd size with at least $3$ vertices (i.e. the number of cliques of odd size, excluding cliques of size 1). $S_1$, $S_2$ and $S_3$ are, among others, present in the statement of Theorem~\ref{LematCoupling}. In this theorem properties of $\Gnmp$ are compared with properties of two other random graphs whose edge probabilities depend on $S_1$, $S_2$ and $S_3$. The first graph used in Theorem~\ref{LematCoupling} is a random graph with approximately $S_2/2$ independent edges. The second one is $\Gn{\hat{p}_2}\cup\Gh{\hat{p}_3}$ where $\Gn{\hat{p}_2}$ has approximately $(S_1-3S_3)/2$ edges and $\Gh{\hat{p}_3}$ has approximately $3S_3$ edges. The last quantity defined in \eqref{RownanieS} is $S_{1,t}$. It is the expected value of the sum of sizes of these cliques forming $\Gnmp$ which contain exactly $t$ vertices. Moreover $S_{1,t}/t$ is the number of features which were chosen by exactly $t$ vertices. Values $S_{1,t}$, $t\ge 2$, are mainly used in studying the minimum degree of $\Gnmp$. For a more formal description of the relations between $S_1$, $S_2$, $S_3$, $S_{1,t}$ and the sizes of cliques forming $\Gnmp$, we refer the reader to \eqref{RownanieSformal}. In what follows we consider monotone graph properties of random graphs. For the family $\mathcal{G}$ of all graphs with the vertex set $\V$, we call $\mathcal{A}\subseteq \mathcal{G}$ a property if it is closed under isomorphism. Moreover $\mathcal{A}$ is increasing if $G\in \mathcal{A}$ implies $G'\in \mathcal{A}$ for all $G'\in\mathcal{G}$ such that $E(G)\subseteq E(G')$. Examples of increasing properties are: $k$--connectivity, containing a perfect matching and containing a Hamilton cycle. The following theorem is an extension of the result obtained in \cite{GpCoupling}. \begin{theorem}\label{LematCoupling} Let $\overline{p}=(p_1,\ldots,p_m)$ be such that $p_i\in (0,1)$, for all $1\le i\le m$ and $S_1$, $S_2$, and $S_3$ be given by \eqref{RownanieS}. For a function $\omega$ tending to infinity let \begin{equation}\label{RownanieHatp} \begin{split} \hat{p}&= \frac{S_2-\omega\sqrt{S_2}-2S_2^2n^{-2}}{2\binom{n}{2}} ;\\ \hat{p}_2&= \begin{cases} \frac{S_1-3S_3-\omega\sqrt{S_1}-2S_1^2n^{-2}}{2\binom{n}{2}}, &\text{for }S_3\gg \sqrt{S_1} \text{ and } \omega\ll S_3/\sqrt{S_1};\\ \frac{S_1-\omega\sqrt{S_1}-2S_1^2n^{-2}}{2\binom{n}{2}}, &\text{for }S_3=O(\sqrt{S_1}); \end{cases} \\ \hat{p}_3&= \begin{cases} \frac{S_3-\omega\sqrt{S_1}-6S_3^2n^{-3}}{\binom{n}{3}}, \hspace{0.7cm}& \text{for }S_3\gg \sqrt{S_1} \text{ and } \omega\ll S_3/\sqrt{S_1};\\ 0, &\text{for }S_3=O(\sqrt{S_1}). \end{cases} \end{split} \end{equation} If $S_1\to \infty$ and $S_1=o\left(n^2\right)$ then for any increasing property $\mathcal{A}$. \begin{align} \label{RownanieCoupling1} \liminf_{n\to\infty}\Pra{\Gn{\hat{p}}\in \mathcal{A}}\le \limsup_{n\to\infty}\Pra{\Gnmp\in \mathcal{A}},\\ \label{RownanieCoupling2} \liminf_{n\to\infty}\Pra{\Gn{\hat{p}_2}\cup\Gh{\hat{p}_3}\in\mathcal{A}} \le \limsup_{n\to\infty}\Pra{\Gnmp\in \mathcal{A}}. \end{align} \end{theorem} \begin{remark} Assumption $S_1\to \infty$ is natural since for $S_1=o(1)$ {\whp} $\Gnmp$ is an empty graph. \end{remark} \begin{remark} The expected number of edges in $\Gh{\hat{p}_3}$ is asymptotically equal to $3\cdot S_3$. If $S_3=O(\sqrt{S_1})$ then by Markov's inequality {\whp} the number of edges in $\Gh{\hat{p}_3}$ is at most $\omega\sqrt{S_1}$ (for any $\omega\to \infty$). Thus $S_2=S_1-S_3=S_1+O(\omega\sqrt{S_1})$ and the bound provided by \eqref{RownanieCoupling1} is as good as the one taking into consideration the edges from $\Gh{\hat{p}_3}$. \end{remark} \begin{remark} The proof of Theorem~\ref{LematCoupling} might be simply rewritten (see \eqref{RownanieCoupligPrzezPoissonIntro}) for $S_1=\Omega(n^2)$ with \begin{equation*} \begin{split} \hat{p}&=1-\exp\left(-\frac{S_2-\omega\sqrt{S_2}}{2\binom{n}{2}}\right);\\ \hat{p}_2&= \begin{cases} 1-\exp\left(-\frac{S_1-3S_3-\omega\sqrt{S_1}}{2\binom{n}{2}}\right), &\text{for }S_3\gg \sqrt{S_1} \text{ and } \omega\ll S_3/\sqrt{S_1};\\ 1-\exp\left(-\frac{S_1-\omega\sqrt{S_1}}{2\binom{n}{2}}\right), &\text{for }S_3=O(\sqrt{S_1}); \end{cases}\\ \hat{p}_3&= \begin{cases} 1-\exp\left(-\frac{S_3-\omega\sqrt{S_1}}{\binom{n}{3}}\right), \hspace{0.7cm}&\text{for }S_3\gg \sqrt{S_1} \text{ and } \omega\ll S_3/\sqrt{S_1};\\ 0,&\text{for }S_3=O(\sqrt{S_1}). \end{cases} \end{split} \end{equation*} \end{remark} Denote by $\mathcal{C}_k$, $\mathcal{PM}$ and $\mathcal{HC}$ the following graph properties: a graph is $k$--connected, has a perfect matching and has a Hamilton cycle, respectively. We will use Theorem~\ref{LematCoupling} to establish threshold functions for $\mathcal{C}_k$, $\mathcal{PM}$ and $\mathcal{HC}$ in $\Gnmp$. By $\mathcal{C}_k$ we denote the vertex connectivity. From the proof it follows that the threshold function for the edge connectivity is the same as this for $\mathcal{C}_k$. For any sequence $c_n$ attaining a limit (possibly $\pm\infty$) we write \begin{equation}\label{RownanieFcn} f(c_n)= \begin{cases} 0&\text{for }c_n\to -\infty;\\ e^{-e^{-c}} &\text{for }c_n\to c\in (-\infty,\infty);\\ 1&\text{for }c_n\to \infty. \end{cases} \end{equation} \begin{theorem}\label{TwierdzenieSpojnosc} Let $\max_{1\le i\le m}p_i=o((\ln n)^{-1})$ and $S_1$ and $S_{1,2}$ be given by \eqref{RownanieS}. \begin{itemize} \item[(i)] If $ S_1=n(\ln n+ c_n), $ where $c_n$ attains a limit (possibly $\pm\infty$), then $$ \lim_{n\to\infty}\Pra{\Gnmp\in \mathcal{C}_1}=f(c_n), $$ where $f(c_n)$ is given by \eqref{RownanieFcn}. \item[(ii)] Let $k$ be a positive integer and $a_n=\frac{S_{1,2}}{S_1}$. If $$ S_1=n(\ln n+(k-1)\ln\ln n + c_n), $$ then $$ \lim_{n\to\infty}\Pra{\Gnmp\in\mathcal{C}_k}= \begin{cases} 0&\text{ for }c_n\to -\infty\text{ and }\liminf_{n\to\infty}a_n=a\in (0,1];\\ 1&\text{ for }c_n\to \infty. \end{cases} $$ \end{itemize} \end{theorem} \smallskip Assumption $\max_{1\le i\le m}p_i=o((\ln n)^{-1})$ is necessary to avoid large cliques formed by vertices which chose the same feature. In the case $\max_{1\le i\le m}p_i=\Omega((\ln n)^{-1})$, the expected value of the number of isolated vertices depends more on other properties of the sequence $\bar{p}=\bar{p}(n)$. The problem is explained in more detail in Section~\ref{SectionStopnie}. Moreover in the case $\liminf_{n\to\infty}a_n=0$ the value $\Pra{\Gnmp\in\mathcal{C}_k}$ depends also on some properties of the sequence $\bar{p}=\bar{p}(n)$. The problem is studied in more detail in the case $\bar{p}=(p,\ldots,p)$ (see Theorems~\ref{TwierdzenieHamiltonGp} and \ref{TwierdzenieSpojnosckGp} and their proofs). A straightforward corollary of Theorem~\ref{TwierdzenieSpojnosc}(i) is that for $S_1=n(\ln n+c_n)$, $c_n\to -\infty$ and any $k=1,2,\ldots,n$ $$ \lim_{n\to\infty}\Pra{\Gnmp\in \mathcal{C}_k}=0\quad\text{and}\quad\lim_{n\to\infty}\Pra{\Gnmp\in \mathcal{HC}}=0. $$ \begin{theorem}\label{TwierdzeniePM} Let $\max_{1\le i\le m}p_i=o((\ln n)^{-1})$ and $S_1$ be given by \eqref{RownanieS}.\\ If $S_1=n(\ln n+c_n)$, where $c_n$ attains a limit (possibly $\pm\infty$), then $$ \lim_{n\to\infty}\Pra{\mathcal{G}(2n,m,\overline{p}(2n))\in\mathcal{PM}}=f(c_{2n}), $$ where $f(\cdot)$ is given by \eqref{RownanieFcn}. \end{theorem} \begin{theorem}\label{TwierdzenieHamilton} Let $\max_{1\le i\le m}p_i=o((\ln n)^{-1})$, $S_1$ and $S_{1,2}$ be given by \eqref{RownanieS} and $a_n=\frac{S_{1,2}}{S_1}$.\linebreak If $ S_1=n(\ln n+\ln\ln n + c_n), $ then $$ \lim_{n\to\infty}\Pra{\Gnmp\in\mathcal{HC}}= \begin{cases} 0&\text{ for }c_n\to -\infty\text{ and }\liminf_{n\to\infty}a_n = a\in (0,1];\\ 1&\text{ for }c_n\to \infty. \end{cases} $$ \end{theorem} \noindent Simple corollaries of Theorems~\ref{TwierdzenieSpojnosc}--\ref{TwierdzenieHamilton} give threshold functions for properties in $\Gnmpp$, a special case of $\Gnmp$ . \begin{corollary} Let $m\gg \ln^2 n$ and $p(1-(1-p)^{n-1})=(\ln n+c_n)/m$, where $c_n$ attains a limit (possibly $\pm\infty$). Then $$ \lim_{n\to\infty}\Pra{\Gnmpp\in \mathcal{C}_1}=f(c_n) $$ and $$ \lim_{n\to\infty}\Pra{\mathcal{G}(2n,m,p)\in\mathcal{PM}}=f(c_{2n}), $$ where $f(\cdot)$ is given by \eqref{RownanieFcn}. \end{corollary} \noindent In particular we may state the following extension of the result from \cite{SingerPhD}. \begin{corollary} Let $b_n$ be a sequence, $\beta$ and $\gamma$ be constants such that\\ $ \beta\gamma(1-e^{-\gamma})=1. $ If $$ m= \beta n\ln n \quad\text{ and}\quad p=\frac{\gamma}{n}\left(1+\frac{b_n}{\ln n}\right), $$ where $b_n$ attains a limit (possibly $\pm\infty$). Then $$ \lim_{n\to\infty}\Pra{\Gnmpp\in\mathcal{C}_1} =f\left(\left(1+\frac{e^{-\gamma}\gamma}{1-e^{-\gamma}}\right)b_n\right) $$ and $$ \lim_{n\to\infty}\Pra{\mathcal{G}(2n,m,p(2n))\in\mathcal{PM}} =f\left(\left(1+\frac{e^{-\gamma}\gamma}{1-e^{-\gamma}}\right)b_{2n}\right), $$ where $f(\cdot)$ is given by \eqref{RownanieFcn}. \end{corollary} With some additional effort one may show the following results for $\Gnmpp$. \begin{theorem}\label{TwierdzenieHamiltonGp} Let $m\gg \ln^2 n$ and \begin{equation} \label{RownanieHamiltonGp} p(1-(1-p)^{n-1})= \frac{\ln n +\ln\left(\max\left\{1,\left(\frac{ np\ln n}{e^{np}-1}\right)\right\}\right) + c_n}{m}. \end{equation} Then $$ \lim_{n\to\infty}\Pra{\Gnmpp\in\mathcal{HC}}= \begin{cases} 0&\text{ for }c_n\to -\infty;\\ 1&\text{ for }c_n\to \infty. \end{cases} $$ \end{theorem} \begin{theorem}\label{TwierdzenieSpojnosckGp} Let $m\gg \ln ^2 n$, $k$ be a positive integer, and $$ a_n=(np)^{k-1} \left( \left(\frac{\ln n}{e^{np}-1}\right)^{k-1}+\frac{\ln n}{e^{np}-1}\right). $$ If \begin{equation*} p(1-(1-p)^{n-1}) = \frac{\ln n + \ln\left(\max\left\{1,a_n\right\}\right) + c_n}{m}, \end{equation*} then $$ \lim_{n\to \infty}\Pra{\Gnmpp\in \mathcal{C}_k}= \begin{cases} 0&\text{ for }c_n\to -\infty;\\ 1&\text{ for }c_n\to \infty. \end{cases} $$ \end{theorem} One of the questions posed in \cite{GpCoupling} is concerned with the range of $m=m(n)$ for which the threshold function for $\mathcal{C}_k$ in $\Gnmpp$ is the same as the one for $\delta(\Gnmpp)\ge 1$ (where by $\delta(G)$ we denote the minimum degree of graph $G$). Another question is concerned with the range of $m=m(n)$ for which the threshold function for $\mathcal{C}_k$ in $\Gnmpp$ is the same as the one for $\mathcal{C}_k$ in $\Gn{\phat}$ with $\phat=mp^2$. Theorem~\ref{TwierdzenieSpojnosckGp} gives a final answer to these questions. \begin{corollary} Let $k$ be a positive integer. If \begin{equation*} p(1-(1-p)^{n-1})= \begin{cases} \frac{\ln n + c_n}{m}, &\text{ for }\ln^2 n\ll m\ll \frac{n\ln n}{\ln\ln n};\\ \frac{\ln n + (k-1)\ln\ln n + c_n}{m}, &\text{ for }m=\Omega(n\ln n); \end{cases} \end{equation*} then $$ \lim_{n\to \infty}\Pra{\Gnmpp\in\mathcal{C}_k}= \begin{cases} 0&\text{ for }c_n\to -\infty;\\ 1&\text{ for }c_n\to \infty. \end{cases} $$ \end{corollary} \section{Road map of the proofs} The remaining part of the article is organised as follows. Section~\ref{SectionCoupling} is devoted to a construction of a coupling of $\Gnmp$ and $\Gsuma$. Later in this section the coupling is used to prove Theorem~\ref{LematCoupling}. Moreover in the subsequent sections the coupling is applied in the proofs of other theorems. In Section~\ref{SectionStopnie} we find a threshold function for the minimum degree at least $k$ in $\Gnmp$. To this end we construct a coupling of a construction of $\Gnmp$ and a coupon collector process. Section~\ref{SectionGsuma} is devoted to presenting properties of $\Gsuma$. Results gathered in Sections~\ref{SectionStopnie} and \ref{SectionGsuma} are the building blocks of the proofs of Theorems~\ref{TwierdzenieSpojnosc}--\ref{TwierdzenieSpojnosckGp}. In Section~\ref{SectionThresholds} we complete the proofs of Theorems~\ref{TwierdzenieSpojnosc}--\ref{TwierdzenieSpojnosckGp}. The article contains numerous lemmas and partial results which lead to the proofs of the main results. We will now shortly explain which lemmas are crucial in proving which theorems. The proofs of all Theorems~\ref{TwierdzenieSpojnosc}--\ref{TwierdzenieSpojnosckGp} consist of two parts. The first part establishes an upper bound on the value $\lim_{n\to\infty}\Pra{ \Gnmp\in \mathcal{A}}$. The second part gives a lower bound on $\lim_{n\to\infty}\Pra{ \Gnmp\in \mathcal{A}}$ (for $\cal{A}$ being ${\cal C}_k$, ${\cal PM}$, or ${\cal HC}$ -- depending on a theorem). All upper bounds follow by the fact that each of the considered properties impose a minimum degree condition. Namely, a graph in order to be $k$--connected has to have the minimum degree at least $k$. Moreover, a perfect matching is only possible in a graph with no isolated vertices (the minimum degree at least 1) and a Hamilton cycle requires the minimum degree at least $2$. Therefore the upper bounds follow by Lemmas~\ref{LematStopnie}, \ref{LematStopnie2} and~\ref{LematStopniek} obtained in Section~\ref{SectionStopnie}. Establishing lower bounds requires more work, as the minimum degree condition is necessary but not sufficient. The first step towards proving this part of theorems is an analysis of the structure of $\Gsuma$. As we want to use Theorem~\ref{LematCoupling} to show Theorems~\ref{TwierdzenieSpojnosc}, \ref{TwierdzeniePM}, and~\ref{TwierdzenieHamilton}, we need to find a lower bond on the value $\lim_{n\to\infty}\Pra{ \Gsuma\in \mathcal{A}}$ for $\mathcal{A}$ being ${\cal C}_k$, ${\cal PM}$, and ${\cal HC}$, respectively. A large part of Section \ref{SectionGsuma} is devoted to establishing these lower bounds. In particular, Lemma~\ref{LematWlasnosciGsuma} gives some useful, basic properties of $\Gsuma$ which are applied in the proofs of almost all the remaining lemmas of this section, i.e. also in the proofs of all Theorems~\ref{TwierdzenieSpojnosc}--\ref{TwierdzenieSpojnosckGp}. These properties, among others, are used to show lower bounds on $\lim_{n\to\infty}\Pra{ \Gsuma\in \mathcal{A}}$. These lower bounds are stated in Lemmas~\ref{LematGsumaCkPM} and~\ref{LematGsumaHamilton}. They follow by Lemma~\ref{LematWlasnosciGsuma}, Lemma~\ref{LematMinDegreeGsuma}, and an analysis of some couplings discussed in Lemmas~\ref{LematGnCkPM} and~\ref{LematGnHamilton}. Lemmas~\ref{LematGnCkPM} and~\ref{LematGnHamilton} provide properties of graph $G(n)$ for which there exists a coupling such that {\whp} $\Gsuma\subseteq G(n)$. Obtaining lower bounds needed in Theorems~\ref{TwierdzenieHamiltonGp} and~\ref{TwierdzenieSpojnosckGp} is more complex. In this case the proofs are based on Lemmas~\ref{LematGnCkPM} and~\ref{LematGnHamilton}, some additional properties of $\Gnmpp$, and properties of the coupling established in the proof of Theorem~\ref{LematCoupling}. \section{Coupling}\label{SectionCoupling} In this section we present a proof of Theorem~\ref{LematCoupling}. In the proof we use auxiliary random graph models $\G{i}{M}$, $i=2,3,\ldots,n$, in which $M$ is a random variable with non--negative integer values. For $i=2,\ldots,n$, $\G{i}{M}$ is constructed on the basis of a random hypergraph $\mathbb{H}_{*i}(n,M)$. $\mathbb{H}_{*i}(n,M)$ is a random hypergraph with the vertex set $\V$ in which a hyperedge set is constructed by sampling $M$ times with repetition elements from the set of all $i$--element subsets of $\V$ (all sets which are chosen several times are added only once to the hyperedge set). $\G{i}{M}$ is a graph with the vertex set $\V$ in which $v,v'\in\V$ are connected by an edge if $\{v,v'\}$ is contained in at least one of the hyperedges of $\mathbb{H}_{*i}(n,M)$. For simplicity of notation, if $M$ equals a constant $t$ with probability one or has Poisson distribution, we write $\G{i}{t}$ or $\G{i}{\Po{\cdot}}$, respectively. Recall that similarly $G_i(n,\phat)$ is constructed on the basis of $H_i(n,\phat)$ -- a hypergraph with independent hyperedges (see definitions at the beginning of Section~\ref{SectionTwierdzenie}). In this article we treat random graphs as random variables. By a coupling $(\rg_1,\rg_2)$ of two random variables $\rg_1$ and $\rg_2$ we mean a choice of a probability space in which we define a random vector $(\rg_1',\rg_2')$ such that $\rg_1'$ and $\rg_2'$ have the same distributions as $\rg_1$ and $\rg_2$, respectively. For simplicity of notation we will not differentiate between $(\rg_1',\rg_2')$ and $(\rg_1,\rg_2)$. For two random graphs $\rg_1$ and $\rg_2$ we write $$ \rg_1\coupling \rg_2 $$ if there exists a coupling $(\rg_1,\rg_2)$, such that in the probability space of the coupling $\rg_1$ is a subgraph of $\rg_2$ with probability $1$. Moreover, we write $$ \rg_1=\rg_2, $$ if $\rg_1$ and $\rg_2$ have the same probability distribution (equivalently there exists a coupling $(\rg_1,\rg_2)$ such that $\rg_1=\rg_2$ with probability one). For two sequences of random graphs $\rg_1=\rg_1(n)$ and $\rg_2=\rg_2(n)$ we write $$ \rg_1\coup \rg_2, $$ if there exists a sequence of couplings $(\rg_1(n),\rg_2(n))$, such that in the probability space of the coupling $\rg_1(n)$ is a subgraph of $\rg_2(n)$ with probability $1-o(1)$, respectively. Note that, for any $\lambda$, in $\mathbb{H}_{*i}(n,\Po{\lambda})$ each hyperedge appears independently with probability $1-\exp(-\lambda/{\textstyle \binom{n}{i}})$. Thus \begin{equation}\label{RownanieGstarPoisson} \G{i}{\Po{\lambda}}=G_i\left(n,1-\exp\left(-\frac{\lambda}{\binom{n}{i}}\right)\right). \end{equation} We gather here a few useful facts concerning couplings of random graphs. For proofs see~\cite{GpEquivalence2,GpCoupling}. \begin{proposition}\label{FaktCouplingGgwiazdka} Let $M_n$ be a sequence of random variables and let $t_n$ be a sequence of positive integers. (i) If $ \Pra{M_n\ge t_n}=o(1) $ then $ \G{i}{M_n}\coup \G{i}{t_n}. $ (ii) If $ \Pra{M_n\le t_n}=o(1) $ then $ \G{i}{t_n}\coup \G{i}{M_n}. $ \end{proposition} \begin{proposition}\label{FaktCouplingIndependent} Let $(\rg_i)_{i=1,\ldots,m}$ and $(\rg'_i)_{i=1,\ldots,m}$ be sequences of independent random graphs. If $$ \rg_i\coupling \rg_i', \text{ for all }i=1,\ldots,m, $$ then $$ \bigcup_{i=1}^{m}\rg_i\coupling \bigcup_{i=1}^{m}\rg'_i. $$ \end{proposition} \begin{proposition}\label{FaktPrzechodniosc} Let $\rg_1=\rg_1(n)$, $\rg_2=\rg_2(n)$, and $\rg_3=\rg_3(n)$ be random graphs.\linebreak If $$ \rg_1\coup \rg_2\quad\text{and}\quad \rg_2\coup \rg_3 $$ then $$ \rg_1\coup \rg_3. $$ \end{proposition} \begin{proposition}\label{FaktCouplingPrawdopodobienstwa} Let $\rg_1=\rg_1(n)$ and $\rg_2=\rg_2(n)$ be two random graphs, such that \begin{equation}\label{RownanieG1G2} \rg_1\coup \rg_2. \end{equation} Then for any increasing property $\mathcal{A}$ $$ \liminf_{n\to\infty}\Pra{ \rg_1(n)\in \mathcal{A}}\le \limsup_{n\to\infty}\Pra{\rg_2(n)\in \mathcal{A}}. $$ \end{proposition} \begin{proof} Define event $ \mathcal{E}:=\{\rg_1\subseteq \rg_2\} $ on a probability space of a coupling $(\rg_1,\rg_2)$ existing by~\eqref{RownanieG1G2}. Then for any increasing property $\mathcal{A}$ \begin{align*} \Pra{\rg_2\in \mathcal{A}} &\ge\Pra{ \rg_2\in \mathcal{A}|\mathcal{E}\}\Pr\{\mathcal{E}} \\ &\ge\Pra{ \rg_1\in \mathcal{A}|\mathcal{E}\}\Pr\{\mathcal{E}} \\ &=\Pra{ \{\rg_1\in \mathcal{A}\}\cap\mathcal{E}}\\ &=\Pra{ \rg_1\in \mathcal{A}}+\Pra{ \mathcal{E}}-\Pra{ \{\rg_1\in \mathcal{A}\}\cup\mathcal{E}}\\ &\ge \Pra{ \rg_1\in \mathcal{A}}+\Pra{\mathcal{E}}-1\\ &= \Pra{ \rg_1\in \mathcal{A}}+o(1).\\ \end{align*} The result follows by taking $n\to \infty$. \end{proof} In the proof of Theorem~\ref{LematCoupling} we will use notations introduced in \eqref{RownanieS}. First, we give a formal explanation of the relations between $S_1$, $S_2$, $S_3$, and $S_{1,t}$ and the sizes of cliques forming $\Gnmp$. In addition we will give some useful simple relations between $S_1$, $S_2$, $S_3$, and $S_{1,t}$. Let $w_i\in\W$, $1\le i\le m$. Denote by $V_i$ the set of vertices which have chosen feature $w_i$ (i.e.~$V_i=\{v\in\V: w_i\in W(v)\}$). Let \begin{equation}\label{RownanieVprim} V'_i= \begin{cases} V_i&\text{ for }|V_i|\ge 2;\\ \emptyset&\text{ otherwise}. \end{cases} \end{equation} Moreover, for each $i$, $1\le i\le m$, let \begin{align} X_i&=|V_i|;\nonumber\\ Y_i&=|V'_i|;\label{RownanieYi} \\ \nonumber Z_i&=\mathbb{I}_{\{Y_i \text{ is odd}\}}, \end{align} where $\mathbb{I}_A$ is an indicator random variable of the event $A$. Note that $X_i$, $1\le i\le m$, are independent random variables with the binomial distributions $\Bin{n}{p_i}$, $1\le i\le m$. Therefore by \eqref{RownanieS} \begin{equation}\label{RownanieSformal} \begin{split} S_1&=\EE \sum_{i=1}^m (X_i-\mathbb{I}_{\{X_i=1\}})=\EE \sum_{i=1}^m Y_i;\\ S_2&=\EE \sum_{i=1}^m (X_i-\mathbb{I}_{\{X_i \text{ is odd}\}})=\EE \sum_{i=1}^m (Y_i-\mathbb{I}_{\{Y_i \text{ is odd}\}}) =\EE \sum_{i=1}^m (Y_i-Z_i);\\ S_3&=\EE \sum_{i=1}^m (\mathbb{I}_{\{X_i \text{ is odd}\}}-\mathbb{I}_{\{X_i=1\}})=\EE \sum_{i=1}^m \mathbb{I}_{\{Y_i \text{ is odd}\}}=\EE \sum_{i=1}^m Z_i;\\ S_{1,t}&=\EE \sum_{i=1}^m X_i\mathbb{I}_{\{X_i=t\}} =\EE \sum_{i=1}^m Y_i\mathbb{I}_{\{Y_i=t\}}=\EE \sum_{i=1}^m t\cdot \mathbb{I}_{\{X_i=t\}},\quad \text{for }t=2,3,\ldots,n. \end{split} \end{equation} Therefore \begin{equation} \label{RownanieStrelacje} S_1 = \sum_{t=2}^{n} S_{1,t}\quad \text{and} \quad S_2=S_1-S_3. \end{equation} In addition a calculation shows that, for large $n$, $\EE Y_i\ge 6 \EE Z_i$ (see Appendix A). Therefore \begin{equation} \label{RownanieSrelacje} 6S_3\le S_1 \quad \text{and}\quad \frac{5}{6} S_1 \le S_2 \le S_1. \end{equation} \begin{proof}[Proof of Theorem~\ref{LematCoupling}] First we will show \eqref{RownanieCoupling2} in the case where $S_3\gg \sqrt{S_1}$. Then we will explain shortly how to adjust the proof to prove Theorem~\ref{LematCoupling} in the remaining cases. Recall that the definition of $V'_i$ is given by \eqref{RownanieVprim}. For each $i$, let $\mathcal{G}[V'_i]$ be a graph with the vertex set~$\V$ and edge set containing these edges from $\Gnmp$ which have both ends in $V'_i$ (i.e. its edges form a clique with the vertex set $V'_i$). In the proof we will use the fact that $\bigcup_{i=1}^{m}\mathcal{G}[V'_i]=\Gnmp$. First, for each $i$ we will construct a coupling of $\mathcal{G}[V'_i]$ with an auxiliary random graph and then we will couple a union of the auxiliary random graphs with $\Gsuma$. For each $i$, $1\le i\le m$, we construct independently a coupling of $\G{2}{\frac{Y_i-3Z_i}{2}}\cup \G{3}{Z_i}$ and $\mathcal{G}[V'_i]$. Given $Y_i=y_i$ and $Z_i=z_i$, for each $i$ independently, we generate instances of $\G{2}{\frac{y_i-3z_i}{2}}$ and $\G{3}{z_i}$. Let $Y_i'=y_i'$ be the number of non-isolated vertices in the constructed instance of $\G{2}{\frac{y_i-3z_i}{2}}\cup \G{3}{z_i}$. By definition $y_i'\le y_i$. Set now $V'_i$ to be the union of the set of non--isolated vertices of the constructed instance of $\G{2}{\frac{y_i-3z_i}{2}}\cup \G{3}{z_i}$ and $y_i-y_i'$ vertices chosen uniformly at random from the remaining vertices. This coupling implies \begin{equation}\label{RownanieCouplingKlika} \G{2}{\frac{Y_i-3Z_i}{2}}\cup \G{3}{Z_i}\coupling\mathcal{G}[V_i']. \end{equation} Now let $$ M_2=\sum_{1\le i\le m} \frac{Y_i-3Z_i}{2}\quad\text{and}\quad M_3=\sum_{1\le i\le m} Z_i. $$ Graphs $\G{2}{\frac{Y_i-3Z_i}{2}}\cup \G{3}{Z_i}$, $1\le i \le m$, are independent and $\mathcal{G}[V_i']$, $1\le i \le m$, are independent. Therefore by Proposition~\ref{FaktCouplingIndependent}, the definition of $\Gnmp$, and the definitions of $\G{2}{\cdot}$ and $\G{3}{\cdot}$ we have \begin{equation}\label{RownanieGgwiazdkaGw} \begin{split} \G{2}{M_2} \cup \G{3}{M_3} &= \bigcup_{1\le i \le m}\left(\G{2}{\textstyle{\frac{Y_i-3Z_i}{2}}}\cup \G{3}{Z_i}\right)\\ &\coupling \bigcup_{1\le i \le m}\mathcal{G}[V_i']\\ &=\Gnmp. \end{split} \end{equation} By \eqref{RownanieSformal} $$ \EE{ M}_2=\frac{S_1-3S_3}{2}\quad\text{and}\quad\EE{ M}_3 = S_3. $$ We will prove that $M_2$ and $M_3$ {\whp} are concentrated around their expected values. Since for each $i$, $1\le i\le m$, $X_i$ is a random variable with the binomial distribution $\Bin{n}{p_i}$ and $\EE (X_i\mathbb{I}_{\{X_i=1\}})=\EE \mathbb{I}_{\{X_i=1\}}$ we have \begin{align*} \Var \sum_{i=1}^{m}Y_i &=\sum_{i=1}^{m}\Var \left(X_i-\mathbb{I}_{\{X_i=1\}}\right) \\ &= \sum_{i=1}^{m} \left( \Var X_i + \Var \mathbb{I}_{\{X_i=1\}} - 2(\EE (X_i\mathbb{I}_{\{X_i=1\}})-\EE X_i\EE \mathbb{I}_{\{X_i=1\}}) \right) \\ &\le \sum_{i=1}^{m} \left( \EE X_i + \EE \mathbb{I}_{\{X_i=1\}} - 2\EE \mathbb{I}_{\{X_i=1\}}+2\EE X_i\EE \mathbb{I}_{\{X_i=1\}} \right) \\ &= \sum_{i=1}^{m} \left( \EE X_i - \EE \mathbb{I}_{\{X_i=1\}} + 2\EE X_i\EE \mathbb{I}_{\{X_i=1\}} \right)\\ &= \sum_{i=1}^{m} \left( \EE Y_i + 2(np_i)^2(1-p_i)^{n-1} \right)\\ &\le \sum_{i=1}^{m} \left( \EE Y_i + 3(np_i-np_i(1-p_i)^{n-1}) \right)\\ &= 4S_1. \end{align*} In the penultimate line we use the fact that, for large $n$, function $(2nx+3)(1-x)^{n-1}$ is decreasing for $x\in [0,1)$. Similarly \begin{align*} \Var \sum_{i=1}^{m}Z_i &=\sum_{i=1}^{m} \Var\left(\mathbb{I}_{\{X_iodd\}}-\mathbb{I}_{\{X_i=1\}}\right) \\ &=\sum_{i=1}^{m} \left( \Var \mathbb{I}_{\{X_i\,odd\}} + \Var \mathbb{I}_{\{X_i=1\}} - 2(\EE (\mathbb{I}_{\{X_i\,odd\}}\mathbb{I}_{\{X_i=1\}})-\EE \mathbb{I}_{\{X_i\,odd\}}\EE \mathbb{I}_{\{X_i=1\}}) \right) \\ &\le \sum_{i=1}^{m} \left( \EE \mathbb{I}_{\{X_i\,odd\}} + \EE \mathbb{I}_{\{X_i=1\}} - 2\EE \mathbb{I}_{\{X_i=1\}} + 2\EE \mathbb{I}_{\{X_i\,odd\}}\EE \mathbb{I}_{\{X_i=1\}} \right)\\ &= \sum_{i=1}^{m} \left( \EE \mathbb{I}_{\{X_i\,odd\}} - \EE \mathbb{I}_{\{X_i=1\}} + 2\EE \mathbb{I}_{\{X_i\,odd\}}\EE \mathbb{I}_{\{X_i=1\}} \right)\\ &\le \sum_{i=1}^{m} \left( \EE X_i - \EE \mathbb{I}_{\{X_i=1\}} + 2\EE X_i\EE \mathbb{I}_{\{X_i=1\}} \right)\\ &\le 4S_1. \end{align*} Therefore by Chebyshev's inequality, for any function $\omega'=\omega'(n)$ tending to infinity \begin{align} \label{RownanieYikoncentracja} \Pra{ \left|\sum_{i=1}^{m}Y_i - S_1\right|\ge \omega'\sqrt{S_1} }\le \frac{4}{(\omega')^2}=o(1), \\ \nonumber \Pra{ \left|\sum_{i=1}^{m}Z_i - S_3\right|\ge \omega'\sqrt{S_1} }\le \frac{4}{(\omega')^2}=o(1). \end{align} Thus {\whp} for $1\ll \omega'\ll S_3/\sqrt{S_1}$ \begin{align*} M_2&\ge \frac{S_1-3S_3-4\omega'\sqrt{S_1}}{2},\\ M_3&\ge S_3-\omega'\sqrt{S_1}. \end{align*} Note that \eqref{RownanieSrelacje} and $\omega'\ll S_3/\sqrt{S_1}$ imply that r.h.s. is positive for large $n$. Therefore by Proposition~\ref{FaktCouplingGgwiazdka} and \eqref{RownanieGgwiazdkaGw} \begin{multline}\label{RownanieG2G3coupling} \G{2}{\frac{S_1-3S_3-4\omega'\sqrt{S_1}}{2}}\cup\G{3}{S_3-\omega'\sqrt{S_1}}\\ \coup^{(*)} \G{2}{M_2}\cup\G{3}{M_3}\coupling \Gnmp. \end{multline} We may assume that in the above coupling $\G{2}{\frac{S_1-3S_3-4\omega'\sqrt{S_1}}{2}}$ and $\G{3}{S_3-\omega'\sqrt{S_1}}$ are independent. The main reason for this is the fact that even though $M_2$ and $M_3$ are dependent (i.e. also $\G{2}{M_2}$ and $\G{3}{M_3}$ are dependent), the choices of hyperedges of $\mathbb{H}_{*i}(n,\cdot)$ (related to $\G{i}{\cdot}$) in distinct draws are independent. We describe the coupling $(*)$ below. Set $m_{2}^-=\frac{S_1-3S_3-4\omega'\sqrt{S_1}}{2}$ and $m_{3}^-=S_3-\omega'\sqrt{S_1}$. We construct the coupling (*) from \eqref{RownanieG2G3coupling} in the following way. Assume we have independent instances of $\mathbb{H}_{*2}(n,m_{2}^-)$ and $\mathbb{H}_{*3}(n,m_3^-)$ (i.e. $\G{2}{m_{2}^-}$ and $\G{3}{m_{3}^-}$). Moreover let $M_2=m_2$ and $M_3=m_3$. \medskip -- If $m_2>m_2^-$ (or $m_3>m_3^-$ resp.) then we perform $m_2-m_2^-$ (or $m_3-m_3^-$) additional draws and add hyperedges to $\mathbb{H}_{*2}(n,m_2^-)$ ($\mathbb{H}_{*3}(n,m_3^-)$ resp.) to get an instance of $\G{2}{M_2}$ ($\G{3}{M_3}$ resp.) with $M_2=m_2$ ($M_3=m_3$ resp.). -- If $m_2\le m_2^-$ ($m_3\le m_3^-$ resp.) then we delete from $\mathbb{H}_{*2}(n,m_2^-)$ ($\mathbb{H}_{*3}(n,m_3^-)$ resp.) hyperedges created by the last draws to get exactly $m_i$, $i=2,3$, draws.\\ Let $M_2'$ and $M_3'$ be independent random variables with the Poisson distributions $$ \Po{\frac{S_1-3S_3-5\omega'\sqrt{S_1}}{2}}\quad\text{and}\quad\Po{S_3-2\omega'\sqrt{S_1}},\text{ respectively.} $$ Then by a sharp concentration of the Poisson distribution \begin{align*} \Pra{M_2'\le \frac{S_1-3S_3-4\omega'\sqrt{S_1}}{2}}&=1-o(1) \quad \text{and} \\ \Pra{M_3'\le S_3-\omega'\sqrt{S_1}}&=1-o(1). \end{align*} Therefore by Proposition~\ref{FaktCouplingGgwiazdka} and \eqref{RownanieGstarPoisson} \begin{equation}\label{RownanieCoupligPrzezPoissonIntro} \begin{split} &\Gn{1-e^{\left(-\frac{S_1-3S_3-5\omega'\sqrt{S_1}}{2\binom{n}{2}}\right)}} \cup \Gh{1-e^{\left(-\frac{S_3-2\omega'\sqrt{S_1}}{\binom{n}{3}}\right)}}\\ &= \G{2}{M'_2}\cup\G{3}{M'_3}\\ &\coup \G{2}{\frac{S_1-3S_3-4\omega'\sqrt{S_1}}{2}}\cup\G{3}{S_3-\omega'\sqrt{S_1}}\\ &\coup \Gnmp . \end{split} \end{equation} For $x\ge 0$ we have $1-e^{-x}\ge x-\frac{x^2}{2}$, therefore \begin{align*} \hat{p}_2&=\frac{S_1-3S_3-5\omega'\sqrt{S_1}-\frac{2S_1^2}{n^2}}{2\binom{n}{2}} \le 1-e^{\left(-\frac{S_1-3S_3-5\omega'\sqrt{S_1}}{2\binom{n}{2}}\right)};\\ \hat{p}_3&\le\frac{S_3-2\omega'\sqrt{S_1}-\frac{6S_3^2}{n^3}}{\binom{n}{3}} \le 1-e^{\left(-\frac{S_3-2\omega'\sqrt{S_1}}{\binom{n}{3}}\right)}. \end{align*} Therefore using standard couplings of $\Gn{\cdot}$ and $H_3(n,\cdot)$ finally we get \begin{equation}\label{RownanieCoupligPrzezPoisson} \begin{split} &\Gn{\hat{p}_2}\cup\Gh{\hat{p}_3} \\ &\coupling \Gn{1-e^{\left(-\frac{S_1-3S_3-5\omega'\sqrt{S_1}}{2\binom{n}{2}}\right)}}\cup \Gh{1-e^{\left(-\frac{S_3-2\omega'\sqrt{S_1}}{\binom{n}{3}}\right)}}\\ &=\G{2}{\Po{\frac{S_1-3S_3-5\omega'\sqrt{S_1}}{2}}}\cup\G{3}{\Po{S_3-2\omega'\sqrt{S_1}}} \\ &\coup \Gnmp. \end{split} \end{equation} The result follows by Propositions~\ref{FaktPrzechodniosc} and~\ref{FaktCouplingPrawdopodobienstwa}. An analogous reasoning gives \eqref{RownanieCoupling1} and \eqref{RownanieCoupling2} in the case $S_3=O(\sqrt{S_1})$. One need to replace \eqref{RownanieCouplingKlika} by $$ \G{2}{\frac{Y_i-Z_i}{2}}\coupling\mathcal{G}[V_i']\quad\text{and}\quad \G{2}{\frac{Y_i-3Z_i}{2}}\coupling\mathcal{G}[V_i'], $$ respectively, and modify the proof accordingly. \end{proof} \section{Vertex degrees in $\Gnmp$}\label{SectionStopnie} For any graph $G$ denote by $\delta(G)$ the minimum vertex degree in $G$. \begin{lemma}\label{LematStopnie} Let $c_n$ be a sequence of real numbers such that $c_n$ attains a limit (possibly $\pm\infty$), $\bar{p}=(p_1,\ldots,p_m)$ such that $\max_{1\le i\le m}p_i=o((\ln n)^{-1})$, and $S_1$ be given by \eqref{RownanieS}.\\ If $$ S_1=n(\ln n+ c_n) $$ then $$\lim_{n\to \infty}\Pra{\delta(\Gnmp)\ge 1}=f(c_n),$$ where $f(\cdot)$ is given by \eqref{RownanieFcn}. \end{lemma} \noindent Note that the condition $\max_{1\le i\le m}p_i=o((\ln n)^{-1})$ is necessary. Otherwise the number of vertices of a given degree depends more on the fluctuations of the values of vector $\overline{p}$. For example let $m=n^{2}$ and $\overline{p}=(p_1,p_2,\ldots,p_m)$ equal \begin{align*} \Big(\underbrace{\frac{b_n}{\ln n},\ldots,\frac{b_n}{\ln n}}_{\ln n(\ln n+c_n)/b_n}, \frac{1}{nm},\ldots,\frac{1}{nm}\Big) \quad\text{ or }\\ \left(\frac{1}{\sqrt{\ln n}},\sqrt{\frac{\ln n+c_n}{nm}},\ldots,\sqrt{\frac{\ln n+c_n}{nm}}\right), \end{align*} for some $b_n,c_n=\Theta(1)$. In both cases $$ S_1=\sum_{i=1}^{m}np_i\left(1-(1-p_i)^{n-1}\right)=n(\ln n+c_n+o(1)). $$ On the other hand the expected number of vertices of degree $0$ in $\Gnmp$ is $$n\prod_{i=1}^m((1-p_i)+p_i(1-p_i)^{n-1})=n\prod_{i=1}^m((1-p_i(1-(1-p_i)^{n-1})),$$ since a vertex $v$ is isolated if for each $i$, $1\le i\le m$, $v$ does not choose $w_i$ or $v$ chooses $w_i$ but no other vertex does. Therefore this expected value equals $$ %n\left(1-\frac{b_n}{\ln n}\right)^{\ln n(\ln n+c_n)/b_n}\sim (1+o(1))\exp\left(-c_n-\frac{b_n}{2}\right) \quad\text{ or }\quad (1+o(1))\exp(-c_n), $$ respectively. \begin{lemma}\label{LematStopnie2} Let $c_n$ be a sequence of real numbers, $k$ be a positive integer, and $\bar{p}=(p_1,\ldots,p_m)$ such that $\max_{1\le i\le m}p_i=o((\ln n)^{-1})$. Moreover let $S_1$ and $S_{1,t}$, $t=2\ldots,k$, be given by \eqref{RownanieS}. \begin{itemize} \item[(i)] If $$ S_1=n\left(\ln n+(k-1)\ln \left(\max\left\{1, \left(\frac{S_{1,2}}{S_1}\ln n\right)\right\}\right) + c_n\right) $$ then $$ \lim_{n\to \infty}\Pra{\delta(\Gnmp)\ge k}=0 \quad \text{for }c_n\to - \infty. $$ \item[(ii)] If $$ S_1-\sum_{t=3}^{k}S_{1,t}=n\left(\ln n+(k-1)\ln \left(\max\left\{1, \left(\frac{S_{1,2}}{S_1}\ln n\right)\right\}\right) + c_n\right) $$ then $$ \lim_{n\to \infty}\Pra{\delta(\Gnmp)\ge k}=1 \quad \text{for }c_n\to \infty. $$ \end{itemize} \end{lemma} \noindent Here and in the proof we assume that $\sum_{t=3}^{2}S_{1,t}=0$. If we assume that $p_i=p=p(n)$, for all $1\le i\le m$, then with a little more work the result of Lemma~\ref{LematStopnie2} may be improved. \begin{lemma}\label{LematStopniek} Let $p=p(n)\in (0,1)$, $k$ be a positive integer, $m=m(n)$ be such that $m\gg \ln^2 n$, and $$ a_n=(np)^{k-1} \left( \left(\frac{e^{-np}\ln n}{1-e^{-np}}\right)^{k-1}+\frac{e^{-np}\ln n}{1-e^{-np}}\right). $$ If \begin{equation*} p(1-(1-p)^{n-1}) = \frac{\ln n + \ln\left(\max\left\{1,a_n\right\}\right) + c_n}{m}, \end{equation*} then $$ \lim_{n\to \infty}\Pra{\delta(\Gnmpp)\ge k}= \begin{cases} 0&\text{ for }c_n\to -\infty;\\ 1&\text{ for }c_n\to \infty. \end{cases} $$ \end{lemma} \begin{proof}[Proof of Lemma \ref{LematStopnie}] Assume first that $c_n=\Omega(\ln n)$ and $c_n\ge 0$, for large $n$. Then for any $c_n'=o(\ln n)$ there exists $\overline{p}'=(p'_1,\ldots,p'_m)$ such that $p'_i\le p_i$, for all $1\le i\le m$, and $\sum_{i=1}^m np'_i(1-(1-p'_i)^{n-1})=n(\ln n + c_n')$ (as $f(x)=x(1-(1-x)^{n-1})$ is a continuous, increasing function for $x\in (0,1)$). Therefore $\Gnm{}{\overline{p}'}\coupling \Gnmp$ and $\Pra{\delta(\Gnm{}{\overline{p}'})\ge 1}\le \Pra{\delta(\Gnmp)\ge 1}$. Now assume that $c_n=\Omega(\ln n)$ and $c_n\le 0$, for large $n$. Then for any $c_n'=o(\ln n)$ we may find $p=o((\ln n)^{-1})$ and $m'$ such that $m'np(1-(1-p)^{n-1})=n(c_n'-c_n)$. Let $\overline{p}'=(p_1',\ldots,p'_{m+m'})$ be such that $p_i'=p_i$, for $1\le i\le m$ and $p_i'=p$, for $m+1\le i\le m+m'$. Then $\sum_{i=1}^m np'_i(1-(1-p'_i)^{n-1})=n(\ln n + c_n')$, $\Gnmp\coupling{\cal G}(n,m+m',\overline{p}')$, and $\Pra{\delta(\Gnmp)\ge 1} \le \Pra{\delta({\cal G}(n,m+m',\overline{p}'))\ge 1}$. Therefore we may restrict ourselves to the case $c_n=o(\ln n)$. Imagine an experiment consisting of an infinite sequence of draws. In each draw we pick independently and uniformly at random one element from the vertex set $\V$. If a vertex is picked in the $i$-th draw we call it {\sl collected} in the $i$-th draw. The outcome of the experiment is an infinite sequence with elements from the vertex set $\V$. We will call this experiment the vertex collector process. Moreover assume that independently we pick a vector $$ (Y_1,Y_2,\ldots,Y_m) $$ chosen so that $Y_i$ are independent random variables with the distribution of the random variables defined in \eqref{RownanieYi}. Now we will construct an instance of $\Gnmp$ basing on those two random independent incomes. In fact we will construct a random family of sets $\{V_i':i=1,\ldots,m\}$ with $|V_i'|=Y_i$, for all $i=1,\ldots,m$, which is equivalent to constructing an instance of $\Gnmp$. Set a vector $$ (Y_1,Y_2,\ldots,Y_m)=(y_1,y_2,\ldots,y_m). $$ Now, independently, we create an infinite sequence of draws described above. We divide this sequence of draws into subsequences. We will call them phases. In the first phase we perform as many draws as necessary to collect $y_1$ distinct vertices form $\V$. We set $V_1'$ to be the set consisting of the vertices collected in the first phase and $T_1$ to be the number of draws made in the first phase. Then we continue and in the second phase we perform as many draws as needed to collect $y_2$ distinct vertices from $\V$. Note that the number of draws and vertices collected in the second phase are independent of the first phase. As before $V_2'$ is the set of collected vertices and $T_2$ is the number of draws in the second phase. We continue in the same manner till the $m$-th phase. After constructing $V'_m$ we proceed with draws without constructing any other sets. Note that sets $V_1',\ldots,V_m'$ constructed in this manner are independent, their sizes are independent random variables $Y_1,\ldots,Y_m$, and each $V_i'$, $1\le i\le m$, is chosen uniformly at random from all subsets of $\V$ of size $Y_i$. In the coupling of the vertex collector process and the construction of $\Gnmp$ described above, the construction of $\Gnmp$ is finished in $\sum_{i=1}^{m}T_i$ draws. Now we will prove that for some $T_-=T_-(n)$ and $T_+=T_+(n)$ {\whp} \begin{equation*} T_-\le \sum_{i=1}^{m}T_i\le T_+. \end{equation*} The values $T_-$ and $T_+$ will be specified later on. Recall that by \eqref{RownanieYikoncentracja}, for any $1\ll\omega\ll \sqrt{S_1}/\ln n$, $$ \Pra{S_1-\omega\sqrt{S_1}\le \sum_{i=1}^m Y_i\le S_1+\omega\sqrt{S_1}}=1-o(1) $$ Therefore we are left with studying the random variable $$ \sum_{i=1}^m T_i-\sum_{i=1}^m Y_i=\sum_{i=1}^m (T_i-Y_i). $$ If $Y_i=y_i=0$ then $T_i=0$ and $T_i-Y_i=0$. Assume now that $Y_i=y_i\ge 2$. If, in the $i$--th phase, we have already collected $j 1/2$. Moreover by Markov's inequality for any $\omega$ $$ \Pra{ \sum_{i=1}^{m}(T_i-Y_i)\ge \frac{S_1}{\omega \ln n} }\le \EE \left(\sum_{i=1}^{m}(T_i-Y_i)\right)\frac{\omega \ln n}{S_1}. $$ Therefore {\whp} \begin{equation}\label{RownanieTY} \sum_{i=1}^{m}(T_i-Y_i)\le \frac{S_1}{\omega \ln n}\quad \text{, for any }1\ll \omega\ll \frac{S_1}{(\ln n\ \EE (\sum_{i=1}^{m}(T_i-Y_i)))}. \end{equation} This combined with \eqref{RownanieYikoncentracja} gives that {\whp} \begin{equation}\label{RownanieSumaT} T_-\le \sum_{i=1}^{m} T_i\le T_+, \end{equation} where $$ T_-=S_1-\omega\sqrt{S_1}\quad\text{and}\quad T_+=S_1+\omega\sqrt{S_1}+\frac{S_1}{\omega \ln n}$$ for some $1\ll\omega\ll\min \{S_1/(\ln n\ \EE (\sum_{i=1}^{m}(T_i-Y_i))),\sqrt{S_1}/\ln n\}.$ Therefore {\whp} the number of draws needed to construct $\Gnmp$ is between $T_-$ and $T_+$. Now we will describe a relation between the minimum degree of $\Gnmp$ and the number of collected vertices in the first $T_-$ and $T_+$ draws. If the construction of $\Gnmp$ is finished between $T_-$ and $T_+$ draws and each vertex has been collected at least once in the first $T_-$ draws then there is no isolated vertex in $\Gnmp$. Moreover the number of isolated vertices in $\Gnmp$ is at least the number of non collected vertices at time $T_+$. In the probability space of the coupling of the vertex collector process with the construction of $\Gnmp$ define events: \medskip \begin{tabular}{lcp{15cm}} $\mathcal{A_-}$&--&all vertices are collected in at most $T_-$ draws;\\ $\mathcal{A_+}$&--&all vertices are collected in at most $T_+$ draws;\\ $\mathcal{A}$&--&$\delta(\Gnmp)\ge 1$; \\ $\mathcal{B}$&--&the construction of $\Gnmp$ is finished between $T_-$-th and $T_+$-th draw. \end{tabular} \medskip \noindent Recall that $\delta(\Gnmp)\ge 1$ if and only if all vertices are collected before the construction of $\Gnmp$ is finished. Therefore $$ \mathcal{A_+}\cap\mathcal{B} \subseteq \mathcal{A}\cap\mathcal{B} \subseteq \mathcal{A_-}\cap\mathcal{B}. $$ This implies \begin{equation}\label{RownanieAplusminus} \Pra{\mathcal{A_+}}-\Pra{\mathcal{B}^c} \le \Pra{\mathcal{A}} \le \Pra{\mathcal{A_-}}+\Pra{\mathcal{B}^c}, \end{equation} where for any event $\mathcal{C}$ we denote by $\mathcal{C}^c$ its complement. Let $S_1=n(\ln n + c_n)$, then $$T_\pm=n(\ln n+c_n+o(1)).$$ By the classical results on the coupon collector problem \cite{CouponCollector}, if $T=T_n=n(\ln n + d_n)$, $d_n\to d \in [-\infty,+\infty]$, then the probability of the event that all vertices are collected in at most $T$ draws tends to $f(d_n)$ as $n\to\infty$. Therefore $$\Pra{\mathcal{A}_-}\sim\Pra{\mathcal{A}_+}\sim f(c_n).$$ Moreover by \eqref{RownanieSumaT} $$ \Pra{\mathcal{B}^c}=o(1). $$ Thus the lemma follows by substituting the above values to \eqref{RownanieAplusminus}. \end{proof} The proofs of Lemmas~\ref{LematStopnie2} and~\ref{LematStopniek} rely on couplings with the vertex collector process similar to the one used in the proof of Lemma~\ref{LematStopnie} and a technique of dividing $\Gnmp$ into auxiliary subgraphs. We will give here the idea of the proofs of Lemmas~\ref{LematStopnie2} and~\ref{LematStopniek} and present technical details in Appendix B. First we gather some simple facts concerning the division of $\Gnmp$. Let $k\ge 2$ be an integer. For each $2\le t\le k$, let $\Gnm{t}{\overline{p}}$ be a random graph with the vertex set $\V$ and edge set consisting of these edges from $\Gnmp$, which are contained in at least one of the sets $\{V_i: |V_i|=t\}$, where $V_i$ is defined as in the proof of Theorem~\ref{LematCoupling}. Moreover let $\Gnm{\ge k+1}{\overline{p}}$ be the subgraph of $\Gnmp$ containing only these edges which are subsets of at least one of the sets $\{V_i: |V_i|\ge k+1\}$. We also define $\Gnm{\neq t}{\overline{p}}$ to be the subgraph of $\Gnmp$ containing only these edges which are subsets of at least one of the sets $\{V_i: |V_i| \neq t\}$. Then, for any $k$ and $2\le t\le k$ $$ \Gnmp =\bigcup_{t=2}^k\Gnm{t}{\overline{p}}\cup \Gnm{\ge k+1}{\overline{p}} = \Gnm{\neq t}{\overline{p}}\cup \Gnm{t}{\overline{p}}. $$ Let \begin{equation}\label{RownanieQt} \begin{split} Q_t &=\sum_{i=1}^{m}\mathbb{I}_{Y_i=t}, \text{ for all }t=2,\ldots,k;\\ Q_{\ge k+1} &=\sum_{i=1}^{m}Y_i\mathbb{I}_{Y_i\ge k+1}=\sum_{i=1}^{m}Y_i-\sum_{t=2}^{k}tQ_t;\\ Q_{\neq t} &= \sum_{i=1}^{m}Y_i\mathbb{I}_{Y_i\neq t}=\sum_{i=1}^{m}Y_i-tQ_t. \end{split} \end{equation} By definition $Q_t$, $2\le t\le k$, is the number of features which have been chosen by exactly $t$ vertices, i.e. the number of cliques forming $\Gnmp$, which have exactly $t$ vertices. Thus $Q_t$, $2\le t\le k$, is also the number of cliques forming $\Gnm{t}{\overline{p}}$ i.e. $\Gnm{t}{\overline{p}}=\G{t}{Q_t}$ (where $\G{t}{\cdot}$ is defined at the beginning of Section \ref{SectionCoupling}). Moreover by \eqref{RownanieSformal} \begin{equation*} \EE Q_t =\frac{S_{1,t}}{t} \text{ for all }t=2,\ldots,k. \end{equation*} Moreover $Q_{\ge k+1}$ is the sum of sizes of the cliques forming $\Gnmp$ which have at least $k+1$ vertices, i.e. the sum of sizes of the cliques forming $\Gnm{\ge k+1}{\overline{p}}$. Therefore by \eqref{RownanieSformal} and \eqref{RownanieStrelacje} $$\EE Q_{\ge k+1} = S_1-\sum_{t=2}^{k}S_{1,t}.$$ Last but not least, the expected value of the sum of sizes of the cliques forming $\Gnm{\neq t}{\overline{p}}$ is $$ \EE Q_{\neq t} = S_1-S_{1,t}. $$ For all $1\le t\le k$, $Q_t$ is a sum of independent Bernoulli random variables and $S_{1,t}\le S_1$ (see \eqref{RownanieStrelacje}). Therefore by Chebyshev's inequality and by \eqref{RownanieYikoncentracja} for any $\omega\to\infty$ {\whp} \begin{align} \label{RownanieMtkoncentracja} \max\left\{0,\frac{S_{1,t}-\omega\sqrt{S_1}}{t}\right\}&\le Q_t\le \frac{S_{1,t}+\omega\sqrt{S_1}}{t}, \text{ for all }t=2,3,\ldots,k \\ \label{RownanieM3koncentracja} Q_{\ge k+1}&\ge S_1-\sum_{t=2}^{k}S_{1,t} - k\omega\sqrt{S_1},\\ \label{RownanieMtbrakkoncentracja} S_1-S_{1,t}-2\omega\sqrt{S_1} &\le Q_{\neq t} \le S_1-S_{1,t}+2\omega\sqrt{S_1}, \text{ for all }t=2,3,\ldots,k. \intertext{ Moreover, for any $t=2,3,\ldots,k$, if $S_{1,t}\to \infty$ then {\whp}} \frac{S_{1,t}- \omega\sqrt{S_{1,t}}}{t} &\le Q_t \le \frac{S_{1,t}+ \omega\sqrt{S_{1,t}}}{t}. \label{RownanieM2koncentracja} \end{align} Now we are ready to give sketches of the proofs of Lemmas~\ref{LematStopnie2} and~\ref{LematStopniek}. Technical details of the proofs are presented in Appendix B. \begin{proof}[Sketch of the proof of Lemma~\ref{LematStopnie2} (i)] We prove the lemma in the case $c_n=o(\ln n)$ and $a_n=S_{1,2}/S_1\gg 1/\ln n$, i.e. $S_{1,2}\to \infty$. In the latter cases the result follows by Lemma~\ref{LematStopnie}. We use the division $\Gnmp=\Gnm{2}{\overline{p}}\cup\Gnm{\neq 2}{\overline{p}}$. If there exists a vertex which is isolated in $\Gnm{\neq 2}{\overline{p}}$ and has degree at most $k-1$ in $\Gnm{2}{\overline{p}}$ then $\delta(\Gnmp)\le k-1$. In order to bound the number of vertices which are isolated in $\Gnm{\neq 2}{\overline{p}}$ and have degree at most $k-1$ in $\Gnm{2}{\overline{p}}$ we will use a coupling. First of all, note that using \eqref{RownanieM2koncentracja} and the same technique as in the proof of Theorem~\ref{LematCoupling} we may show that $$ \Gnm{2}{\overline{p}}\coup G_2(n,\phat_{2+})\quad\text{with }\quad \phat_{2+} = \frac{S_{1,2}+2\omega\sqrt{S_{1,2}}}{2\binom{n}{2}}. $$ Moreover we may construct a coupling of the vertex collector process described in the proof of Lemma~\ref{LematStopnie} and a construction $\Gnm{\neq 2}{\overline{p}}$. This coupling is analogous to the one described in the proof of Lemma~\ref{LematStopnie}. The only change is that during the construction of $\Gnmp$ we omit phases related to the cliques of size $2$. By \eqref{RownanieTY} and \eqref{RownanieMtbrakkoncentracja} {\whp} the construction of $\Gnm{\neq 2}{\overline{p}}$ takes at most $T_+=S_1-S_{1,2}+2\omega\sqrt {S_1}+\frac{S_1}{\omega\ln n}$ draws in the vertex collector process. The only problem might be caused by the dependency between graphs $\Gnm{2}{\overline{p}}$ and $\Gnm{\neq 2}{\overline{p}}$. This dependency is due to the fact that $Q_2$ and $Q_{\neq 2}$ are dependent. On the other hand the choices of cliques forming $\Gnm{2}{\overline{p}}$ and $\Gnm{\neq 2}{\overline{p}}$ are independent. Therefore ideas used in proving \eqref{RownanieG2G3coupling} might also be used here to show that we may couple $\Gnm{2}{\overline{p}}\cup\Gnm{\neq 2}{\overline{p}}$ with $G_2(n,\phat_{2+})$ and an independent vertex collector process in such a manner that {\whp} $\Gnm{2}{\overline{p}}\subseteq G_2(n,\phat_{2+})$ and the construction of $\Gnm{\neq 2}{\overline{p}}$ is finished in at most $T_+$ draws. With the second moment method we may show that if $$ S_1=n\left(\ln n+(k-1)\ln \left(\max\left\{1, \left(\frac{S_{1,2}}{S_1}\ln n\right)\right\}\right) + c_n\right),\quad c_n\to -\infty, $$ then {\whp} there exists a vertex of degree at most $k-1$ in $G_2(n,\phat_{2+})$ which has not been collected in $T_+$ draws of the vertex collector process. Therefore, by the constructed coupling, {\whp} there exists a vertex which has degree at most $k-1$ in $\Gnm{2}{\overline{p}}$ and is isolated in $\Gnm{\neq 2}{\overline{p}}$. Hence $$ \lim_{n\to\infty}\Pra{\delta(\Gnmp)\ge k}=0. $$ \end{proof} \begin{proof}[Sketch of the proof of Lemma~\ref{LematStopnie2} (ii)] We use a similar reasoning as in the proof of (i). We may concentrate on the case $c_n=O(\ln n)$ and $S_{1,2}/S_1\gg 1/\ln n$. Let $k\ge 2$, then $$\Gnm{2}{\overline{p}}\cup\Gnm{\ge k+1}{\overline{p}}\subseteq \Gnmp$$ As before, we may construct a coupling of $\Gnm{2}{\overline{p}}\cup\Gnm{\ge k+1}{\overline{p}}$ with $G_2(n,\phat_{2-})$ and an independent vertex collector process with at least $T_-$ draws where $$\phat_{2-}=\frac{S_{1,2}-2\omega\sqrt{S_{1,2}}-2S^2_{1,2}n^{-2}}{2\binom{n}{2}},\quad T_-=\max\left\{0,S_1-\sum_{t=2}^{k}S_{1,t} - k\omega\sqrt{S_1},\right\}. $$ In this coupling {\whp} $G_2(n,\phat_{2-})\subseteq\Gnm{2}{\overline{p}}$ and the construction of $\Gnm{\ge k+1}{\overline{p}}$ takes at least $T_{-}$ draws. By the first moment method we may show that if $$ S_1-\sum_{t=3}^{k}S_{1,t}=n\left(\ln n+(k-1)\ln \left(\max\left\{1, \left(\frac{S_{1,2}}{S_1}\ln n\right)\right\}\right) + c_n\right),\quad c_n\to\infty, $$ then {\whp} each vertex has degree at least $k$ in $G_2(n,\phat_{2-})$ or is collected in $T_-$ draws in the vertex collector process. Therefore, by the coupling, {\whp} each vertex has degree at least $k$ in $\Gnm{2}{\overline{p}}$ or is not isolated in $\Gnm{\ge k+1}{\overline{p}}$. This implies that {\whp} each vertex has degree at least $k$ in $\Gnm{2}{\overline{p}}\cup\Gnm{\ge k+1}{\overline{p}}$ and $$ \lim_{n\to \infty}\Pra{\delta(\Gnmp)\ge k}=1 \quad \text{for }c_n\to \infty. $$ \end{proof} \begin{proof}[Sketch of the proof of Lemma~\ref{LematStopniek}] The main ideas behind the proof of Lemma~\ref{LematStopniek} are the same as in the proof of Lemma~\ref{LematStopnie2}. As before, we may restrict ourselves to the case $S_1\sim n\ln n$ (recall that $p(1-(1-p)^{n-1})=S_1/nm$). We divide the proof into cases, depending on the value $np$ (recall that the expected size of $V_i$ is $\EE X_i = np$, $1\le i\le m$). For convenience in the case $\overline{p}=(p,\ldots,p)$ we replace $\overline{p}$ by $p$ in notations $\Gnm{t}{\overline{p}}$, $\Gnm{\ge k+1}{\overline{p}}$, $\Gnm{\neq t}{\overline{p}}$. If $S_{1,2}=O(S_1/\ln n)$ and $S_{1,t}=O(S_1/\ln n)$ then the result follows by Lemma~\ref{LematStopnie2}. Otherwise $S_{1,2}\gg S_1/\ln n$ or $S_{1,k}\gg S_1/\ln n$ (i.e. $np\le \ln \ln n + (k-1) \ln\ln\ln n - \omega$ for some $\omega=\omega(n)\to \infty$). For $c_n\to - \infty$ we use either the division $\Gnm{\neq k}{p}\cup \Gnm{k}{p}$ or the division $\Gnm{\neq 2}{p}\cup \Gnm{2}{p}$. For $c_n\to \infty$ we use the division $\bigcup_{t=2}^{k}\Gnm{2}{p}\cup \Gnm{\ge k+1}{p}$. \end{proof} \section{Structural properties of $\Gn{\hat{p}_2}\cup\Gh{\hat{p}_3}$}\label{SectionGsuma} In this section we give several structural results concerning $\Gn{\hat{p}_2}\cup\Gh{\hat{p}_3}$. Some of the presented facts are analogous to those known for $\Gn{\hat{p}_2}$. Then we will combine obtained results with the coupling constructed in the proof of Theorem~\ref{LematCoupling} in order to obtain the lower bounds on $\lim_{n\to\infty}\Pra{\Gnmp\in {\cal A}}$, for ${\cal A}$ being ${\cal C}_k$, ${\cal PM}$ or ${\cal HC}$. For any graph $G$ and any set $S\subseteq V(G)$ denote by $N_G(S)$ the set of neighbours of vertices from $S$ contained in $V(G)\setminus S$. For simplicity we write $N_2(\cdot)=N_{\Gn{\hat{p}_2}}(\cdot)$ and $N_3(\cdot)=N_{\Gsuma}(\cdot)$. Note that given an instance of $\Gsuma$ we have $|N_2(S)|\le |N_3(S)|$. %In order to prove the lemma we will first prove some simple structural properties of $\Gsuma$. %\begin{lemma} %Let $c_n\to \infty$ and %$$ %\pdwa+\frac{n}{2}\ptrzy=\frac{\ln n + (k-1)\ln\ln n + c_n}{n} %$$ %Then {\whp} % %(i) for any $S\subseteq \V$, $1\le |S|\le n/2$ %$$ %|N_3(S)|\ge k %$$ % %(ii) for $k=2$ and any $S\subseteq \V$, $1\le |S|\le n/4$ %$$ %|N_3(S)|\ge 2|S| %$$ % %(iii) for $k=1$ and any $S\subseteq \V$, $1\le |S|\le 2n/3$ %$$ %|N_3(S)|\ge \min{|S|,\alpha(\Gsuma)}, %$$ % %where $\alpha(\Gsuma)$ is the independence number of $\Gsuma$. %\end{lemma} \begin{lemma}\label{LematWlasnosciGsuma} Let $k$ and $C$ be positive integers and \begin{equation} \begin{split}\label{RownanieWarunekPdwaPtrzy} \pdwa+\frac{n}{2}\ptrzy&=\frac{\theta_n\ln n}{n}, \quad \text{where } \liminf_{n\to\infty}\theta_n=\theta>\frac{1}{2}\text{ and }\theta_n=O(1),\\ \pdwa&=\frac{\theta'_n\ln n}{n},\quad \text{where } \liminf_{n\to\infty}\theta'_n=\theta'\ge\frac{1}{2}\text{ and }\theta'_n=O(1).\end{split} \end{equation} Let moreover $\gamma$ be a positive real number such that $1-\theta'<\gamma<1$. Then {\whp} $\Gsuma$ has the following properties: \begin{itemize} \item[(i)] $\mathcal{B}_1$ -- for all $S\subseteq \V$ such that $n^{\gamma}\le |S|\le \frac{1}{4}n$ $$ |N_3(S)|>2|S|. $$ \item[(ii)] $\mathcal{B}_2$ -- for all $S\subseteq \V$ such that $n^{\gamma}\le |S|\le \frac{2}{3}n$ \begin{align*} |N_3(S)| &>\min\{|S|,4n\ln \ln n/\ln n\}\\ &>\min\{|S|,\alpha(\Gsuma)\}, \end{align*} where $\alpha(\Gsuma)$ is the stability number of $\Gsuma$. \item[(iii)] $\mathcal{B}_{3,k}$ -- for all $S\subseteq \V$, if $1\le |S|\le n^{\gamma}$ and all vertices in $S$ have degree at least $4k+14$ in $\Gsuma$ we have $$ |N_3(S)|\ge 2k|S|. $$ \item[(iv)] $\mathcal{B}_{4,C}$ -- any two vertices of degree at most $C$ are at distance at least $5$. \item[(v)] $\mathcal{B}_5$ -- contains a path of length at least $$ \left(1-\frac{9\ln 2}{\ln n}\right)n. $$ \end{itemize} \end{lemma} \begin{proof} \noindent(i) and (ii)\ By Chernoff's inequality (for the proof see for example Theorem~2.1 in \cite{KsiazkaJLR}) for any $\delta=\delta(n)=o(1)$ and any binomial random variable $X=X_n$ we have $$ \Pra{X\le \delta \EE X}\le \exp(-\EE X(\delta\ln \delta + 1 - \delta)) =\exp(-(1+o(1))\EE X). $$ First consider the case $n^{\gamma}\le |S|\le 4n\ln\ln n/\ln n$. Let $s=|S|$. Then $|N_2(S)|$ has binomial distribution $\Bin{n-s}{1-(1-\pdwa)^s}$ with the expected value $\EE |N_2(S)|\gg 2|S|$. Denote by $X$ the number of sets $S$ of cardinality $n^{\gamma}\le |S|\le 4n\ln\ln n/\ln n$ such that $|N_2(S)|\le 2|S|$. Using Chernoff's inequality we get \begin{align*} \EE X \le& \sum_{s=n^{\gamma}}^{4 n\ln\ln n/\ln n} \binom{n}{s}\exp\left(-(1+o(1))(n-s)(1-(1-\pdwa)^s)\right) \\ \le& \sum_{s=n^{\gamma}}^{n/(\ln n\ln\ln n)} \exp\left(s\left(1+\ln\frac{n}{s}\right)-(1+o(1))sn\pdwa \right)\\ &+ \sum_{s=n/(\ln n\ln\ln n)}^{4 n\ln\ln n/\ln n} \exp\left(s\left(1+\ln\frac{n}{s}\right)-n\frac{\theta'}{2\ln \ln n}\right)\\ \le& \sum_{s=n^{\gamma}}^{n/(\ln n\ln\ln n)} \exp\left(s\left(1+(1-\gamma)\ln n-(1+o(1))\theta'\ln n\right)\right)\\ &+ \sum_{s=n/(\ln n\ln\ln n)}^{4 n\ln\ln n/\ln n} \exp\left(s\left((1+o(1))\ln \ln n - \frac{\theta'\ln n}{8(\ln \ln n)^2}\right)\right)\\ =&\ o(1). \end{align*} Therefore {\whp} for all sets $S\subseteq \V$, $n^{\gamma}\le |S|\le 4n\ln\ln n/\ln n$, we have $$ |N_2(S)|\ge 2|S|. $$ Now consider the case $|S|\ge 4n\ln\ln n/\ln n$. Let $r=4n\ln\ln n/\ln n$. Let moreover $\overline{K}_r$ and $\overline{K}_{r,r}$ be the complement of the complete graph on $r$ vertices and the complement of the complete bipartite graph with each set of bipartition of cardinality $r$. Denote by $X_r$ and $X_{r,r}$ the number of $\overline{K}_r$ and $\overline{K}_{r,r}$ in $\Gsuma$, respectively. Then \begin{align*} \EE X_r &= \binom{n}{r}(1-\pdwa)^{\binom{r}{2}}(1-\ptrzy)^{\binom{r}{3}+\binom{r}{2}(n-r)}\\ &\le \left( \frac{en}{r}\exp\left(-\frac{r}{2}\left(\pdwa+(n-r)\ptrzy\right)+o(1)\right) \right)^r\\ &\le \left( \frac{e\ln n}{4\ln \ln n}\exp\left(-2\theta_n\ln \ln n\right) \right)^r=o(1) \end{align*} and \begin{align*} \EE X_{r,r} &\le \binom{n}{r}^2(1-\pdwa)^{r^2}(1-\ptrzy)^{2\binom{r}{2}r+r^2(n-2r)}\\ &\le \left( \frac{en}{r}\exp\left(-\frac{r}{2}(\pdwa+(n-2r)\ptrzy)+o(1)\right) \right)^{2r}=o(1). \end{align*} Therefore {\whp} $X_r=0$ which implies that {\whp} $$\alpha(\Gsuma)\le r.$$ Moreover {\whp} $X_{r,r}=0$ thus {\whp} for any $S\subseteq \V$ such that $r\le |S|$ we have $$ N_3(S)\ge n-|S|-r. $$ (Otherwise $\Gsuma$ would contain $\overline{K}_{r,r}$.)\\ Therefore {\whp} for any $S\subseteq \V$ such that $r\le |S|\le 2n/3$ $$N_3(S) \ge \min\{|S|,r\} \ge \min\{|S|,\alpha(\Gsuma)\}. $$ Moreover {\whp} for any $S\subseteq \V$ such that $r\le |S|\le n/4$ we have $$ N_3(S)\ge n-|S|-r\ge 2|S|. $$ This finishes the proof of (i) and (ii). \noindent (iii) For any two disjoint sets $S\subseteq \V$ and $S'\subseteq \V$ we denote by $e(S,S')$ the number of edges in $\Gsuma$ with one end in $S$ and one end in $S'$ and by $e(S)$ the number of edges in $\Gsuma$ with both ends in $S$. We will bound the numbers $e(S)$ and $e(S,S')$ for $S\subseteq \V$ and $S'\subseteq \V\setminus S$ such that $1\le |S|\le n^{\gamma}$ and $|S'|=O(|S|)$. Let $k$ be a positive integer, $S\subseteq \V$, $S'\subseteq \V\setminus S$, $|S|=s$, $1\le s\le n^{\gamma}$ and $|S'|=2ks$. A pair $\{v,v'\}$ ($v\in S$ and $v'\in S'$) is an edge in $\Gsuma$ if at least one of the three following events occurs: \begin{itemize} \item $\{v,v'\}$ is an edge in $\Gn{\pdwa}$, \item there is a hyperedge $\{v,v',v''\}$ with $v''\in \V\setminus(S\cup S')$ in $H_3(n,\ptrzy)$ associated with $\Gh{\ptrzy}$, \item there is a hyperedge $\{v,v',v''\}$ with $v''\in S\cup S'$ in $H_3(n,\ptrzy)$ associated with $\Gh{\ptrzy}$. \end{itemize} The union of the two first events occurs with probability at most $\pdwa+(n-(2k+1)s)\ptrzy=O(\ln n/n)$ independently for all $v\in S$ and $v'\in S'$. Moreover each hyperedge of $H_3(n,\ptrzy)$ with all vertices in $S\cup S'$ appears independently with probability $\ptrzy=O(\ln n/n^2)$ and generates two edges between $S$ and $S'$ in $\Gh{\ptrzy}$. Therefore \begin{align*} &\Pra{ \exists_{\begin{subarray}{l} S,S'\subseteq\V,\\ |S'|=2k|S|\\ 1\le |S|\le n^{\gamma} \end{subarray}} e(S,S')\ge 4(k+1)|S|}\\ &\quad\le \sum_{s=1}^{n^{\gamma}} \binom{n}{s}\binom{n-s}{2ks} \Bigg[\binom{2ks^2}{(2k+2)s}(\pdwa+(n-(2k+1)s)\ptrzy)^{(2k+2)s}\\ &\quad\quad+ \binom{\binom{s}{2}2ks+\binom{2ks}{2}s}{(k+1)s}\ptrzy^{(k+1)s} \Bigg] \\ &\quad\le \sum_{s=1}^{n^{\gamma}} \Bigg[ \left(O(1)\left(\frac{n}{s}\right)^{2k+1}\left(\frac{s\ln n}{n}\right)^{2k+2}\right)^s\\ &\quad\quad+ \left(O(1)\left(\frac{n}{s}\right)^{2k+1}s^{k+1}\left(\frac{\ln n}{n^2}\right)^{k+1}\right)^s\Bigg] \\ &\quad\le \sum_{s=1}^{n^{\gamma}} \Bigg[\left( O(1)\frac{\ln^{2k+2}n}{n^{1-\gamma}} \right)^s + \left( O(1)\frac{\ln^{k+1} n}{n} \right)^s\Bigg] \\ &\quad=o(1). \end{align*} Similarly \begin{align*} &\Pra{ \exists_{\begin{subarray}{l} S\subseteq\V\\ 1\le |S|\le n^{\gamma} \end{subarray}} e(S)\ge 5|S|}\\ &\quad\le \sum_{s=1}^{n^{\gamma}} \binom{n}{s} \Bigg[\binom{\binom{s}{2}}{2s}(\pdwa+(n-s)\ptrzy)^{2s} + \binom{\binom{s}{3}}{s}\ptrzy^{s} \Bigg]\\ &\quad\le \sum_{s=1}^{n^{\gamma}} \left( O(1)\frac{\ln^{2}n}{n^{1-\gamma}} \right)^s + \left( O(1)\frac{\ln n}{n^{1-\gamma}} \right)^s \\ &\quad=o(1). \end{align*} Therefore {\whp} for any set $S$ ($1\le |S|\le n^{\gamma}$) of vertices of degree at least $4k+14$ in $\Gsuma$ we have $$ |N_3(S)|\ge 2k|S|. $$ Otherwise for $S'=N_3(S)$ there would be $|S'|=|N_3(S)|\le 2k|S|$ and $e(S,N_3(S))+2e(S)\ge (4k+14)|S|$, i.e. $e(S,N_3(S))\ge 4(k+1)|S|$ or $e(S)\ge 5|S|$. \noindent(iv) The probability that in $\Gsuma$ there are two vertices of degree at most $C$ at distance at most $4$ is at most \begin{align*} &n^2\sum_{l=0}^{3}n^l(\pdwa+n\ptrzy)^{l+1}\\ &\cdot \Bigg(\sum_{i=0}^{C} \sum_{j=0}^{\lfloor i/2\rfloor} \binom{\binom{n-1-l}{2}}{j}\ptrzy^{j} \binom{n-1-l}{i-2j}\pdwa^{i-2j}\\ &\cdot (1-\pdwa)^{n-1-i-l} (1-\ptrzy)^{\binom{n-1-l}{2}-\binom{i+l}{2}} \Bigg)^2\\ &=O(1)n(\ln n)^{2C+4}e^{-2n(\pdwa+\frac{n}{2}\ptrzy)}=o(1). \end{align*} \noindent (v) Follows by Theorem~8.1 in \cite{KsiazkaBollobas}. \end{proof} \begin{lemma}\label{LematMinDegreeGsuma} Let $k$ be a positive integer and $\pdwa=\pdwa(n)\in(0,1)$, $\ptrzy=\ptrzy(n)\in (0,1)$ be such that $$ \pdwa+\frac{n}{2}\ptrzy=\frac{\ln n + (k-1)\ln \ln n + c_n}{n}, $$ \begin{itemize} \item[(i)] If $k=1$ and $c_n$ attains a limit (possibly $\pm\infty$) then $$\Pra{\delta(\Gsuma)\ge 1}\to f(c_n),$$ where $f(\cdot)$ is defined by \eqref{RownanieFcn}. \item[(ii)] If $c_n\to \infty$ then $$\Pra{\delta(\Gsuma)\ge k}\to 1.$$ \end{itemize} \end{lemma} \begin{proof} (i) Follows by Theorem~3.10 in~\cite{Magisterka}. \noindent(ii) Let $X_t$ be the number of vertices of degree $0\le t\le k-1$ in $\Gsuma$. Then \begin{align*} \EE X_t &\le n\binom{n-1}{t} \sum_{i=0}^{t}\binom{\binom{t}{2}}{i}\ptrzy^{i}\pdwa^{\max\{t-2i,0\}} (1-\pdwa)^{n-t-1}(1-\ptrzy)^{\binom{n-1}{2}-\binom{t}{2}}\\ &=O(1)n(\ln n)^{t}\exp(-\ln n + (k-1)\ln \ln n + c_n)=o(1). \end{align*} Thus {\whp} $X_t=0$ for all $t\le k-1$. \end{proof} \begin{lemma}\label{LematGnCkPM} Let $k$ be a positive integer and $\pdwa$ and $\ptrzy$ be as in \eqref{RownanieWarunekPdwaPtrzy}. Let $\rg(n)$ be a random graph such that \begin{equation}\label{RownanieCouplingGsumaGn} \Gsuma\coup \rg(n) \end{equation} and in the probability space of the coupling {\whp} all vertices of degree at most $4k+13$ in $\Gsuma$ are at distance at least~$5$ in $\rg(n)$. If $\Pra{\delta(\rg(n))\ge k}$ is bounded away from zero by a constant then \begin{align} &\Pra{\rg(n)\in \mathcal{C}_k|\delta(\rg(n))\ge k}\to 1,\label{RownanieGnCk}\\ &\Pra{\rg(2n)\in \mathcal{PM}|\delta(\rg(2n))\ge 1}\to 1 \label{RownanieGnPM}. \end{align} \end{lemma} \noindent In particular, if we substitute $\rg(n)=\Gsuma$ then by Lemmas~\ref{LematWlasnosciGsuma}(iv), \ref{LematMinDegreeGsuma}, and~\ref{LematGnCkPM} we obtain the following result. \begin{lemma}\label{LematGsumaCkPM} Let $\pdwa$ and $\ptrzy$ fulfil \eqref{RownanieWarunekPdwaPtrzy}. \begin{itemize} \item[(i)] If $ \pdwa+\frac{n}{2}\ptrzy=(\ln n + c_n)/n $ for $c_n$ attaining a limit (possibly $\pm\infty$) then \begin{align*} &\Pra{\Gsuma\in \mathcal{C}_1}\to f(c_n);\\ &\Pra{G_2(2n, \pdwa(2n))\cup G_3(2n, \ptrzy(2n))\in \mathcal{PM}}\to f(c_{2n}), \end{align*} where $f(\cdot)$ is defined by \eqref{RownanieFcn}. \item[(ii)] If $ \pdwa+\frac{n}{2}\ptrzy=(\ln n + (k-1)\ln \ln n +c_n)/n $ and $c_n\to \infty$ then \begin{align*} &\Pra{\Gsuma\in \mathcal{C}_k}\to 1. \end{align*} \end{itemize} \end{lemma} \begin{proof}[Proof of Lemma~\ref{LematGnCkPM}] Denote by $\Gdelta$ a graph $\rg(n)$ under condition $\delta(\rg(n))\ge k$. Let ${\cal A}$ be a graph property. In what follows we will use the fact that if $\Pra{\delta(\rg(n)\ge k)}$ is bounded away from zero and $\rg(n)$ has ${\cal A}$ {\whp}, then also $\Gdelta$ has property ${\cal A}$ {\whp}. From now on we assume that $\Gsuma$ and $\rg(n)$ are defined on the same probability space existing by \eqref{RownanieCouplingGsumaGn}. We call a vertex $v\in\V$ {\em small} if its degree in $\Gsuma$ is at most $4k+13$. Otherwise we call $v$ a {\em large} vertex. Let $S\subseteq\V$ and $|S|\le n^{\gamma}$. Denote by $S^+$ and $S^-$ the subset of large and small vertices in $S$, respectively. Then by Lemma~\ref{LematWlasnosciGsuma}(iii) {\whp} $$ |N_{\Gdelta}(S^+)|\ge |N_3(S^+)|\ge 2k|S^+|. $$ Moreover in $\Gdelta$ all vertices in $S^-$ have degree at least $k$ and {\whp} are at distance at least $5$. Therefore {\whp} in $\Gdelta$ no two vertices in $S^-$ are connected by an edge. Moreover they have no common neighbour. Therefore {\whp} $|N_{\Gdelta}(S^-)|\ge k|S^-|$. We are left with the question how much $N_{\Gdelta}(S^-)$ overlaps with $N_\Gdelta(S^+)\cup S^+$. This will give us the bound on the size of $N_{\Gdelta}(S^+\cup S^-)$. If there was a vertex $v$ in $S^+$ and two vertices $v'$ and $v''$ in $S^-$ such that $v'$ is a neighbour of $v$ or its neighbour and $v'$ is a neighbour of $v$ or its neighbour then $v'$ and $v''$ would be connected by a path of length at most $4$. Therefore {\whp} there are no such three vertices, i.e. for each $v\in S^+$ there is at most one vertex $v'\in S^-$ such that $v'$ is a neighbour of $v$ or of its neighbour. This implies that {\whp} at most $|S^+|$ vertices from $S^-$ have neighbours in $N_\Gdelta(S^+)\cup S^+$. Recall that each of the remaining vertices from $S^-$ has $k$ neighbours outside $N_\Gdelta(S^+)\cup S^+$ and their neighbour sets are disjoint. Thus {\whp} $$ \forall_{S\subseteq \V, 1\le |S|\le n^{\gamma}} |N_{\Gdelta}(S)|\ge |N_{\Gdelta}(S^+)|+k\max\{|S^-|-|S^+|,0\}\ge k|S|. $$ If we combine this with Lemma~\ref{LematWlasnosciGsuma}(i) and (ii) we get that {\whp} \begin{align} &|N_{\Gdelta}(S)|\ge k, \hspace{3.3cm} \text{ for all }S\subseteq \V,\ 1\le |S|\le \frac{n}{2}\label{RownanieNCk};\\ &|N_{\rg(n)_{\delta\ge 1}}(S)|\ge \min\{|S|,4n\ln \ln n/\ln n\}\ge \min\{|S|,\alpha(\Gdelta)\},\label{RownanieNPM}\\ &\nonumber \hspace{6.2cm}\text{ for all }S\subseteq \V,\ 1\le |S|\le \frac{2n}{3};\\ &|N_{\rg(n)_{\delta\ge 2}}(S)|\ge 2|S|, \hspace{2.8cm} \text{ for all }S\subseteq \V,\ 1\le |S|\le \frac{n}{4}\label{RownanieNHC}. \end{align} Finally \eqref{RownanieGnCk} follows immediately by \eqref{RownanieNCk}. Moreover if \eqref{RownanieNPM} is fulfilled then $\rg(n)_{\delta\ge 1}$ has a perfect matching (for the proof see for example Lemma~1 in~\cite{UniformMatchings}). Therefore \eqref{RownanieGnPM} follows. \eqref{RownanieNHC} will be used later to establish a threshold function for a Hamilton cycle. \end{proof} \begin{lemma}\label{LematGnHamilton} Let $k$ be a positive integer, $\theta_n$ and $\theta_n'$ be sequences such that $\liminf_{n\to\infty}\theta_n = \theta>\frac{1}{2}$, $\liminf_{n\to\infty}\theta_n' = \theta'\ge \frac{1}{2}$, $\theta, \theta'=O(1)$, and $$ \pdwa+\frac{n}{2}\ptrzy=\frac{\theta_n\ln n}{n},\ \pdwa=\frac{\theta'_n\ln n}{n} \text{ and } \phat_4=\frac{576}{n}. $$ Let moreover $\rg(n)$ be a random graph such that: \begin{itemize} \item[(i)] $ \Gsuma\coup \rg(n); $ \item[(ii)] {\whp} $\delta(\rg(n))\ge 2$; \item[(iii)] in a probability space existing by (i) all vertices of degree at most $21$ in $\Gsuma$ are at distance at least~$5$ in $\rg(n)$. \end{itemize} Then $$ \Pra{\rg(n)\cup\Gn{\phat_4}\in \mathcal{HC}}\to 1\label{RownanieHC}. $$ \end{lemma} \noindent In particular by Lemmas~\ref{LematWlasnosciGsuma}(iv) and \ref{LematMinDegreeGsuma} we get the following simple corollary of Lemma~\ref{LematGnHamilton}. \begin{lemma}\label{LematGsumaHamilton} Let $\pdwa$ and $\ptrzy$ be as in Lemma~\ref{LematGnHamilton}. If moreover $$ \pdwa+\frac{n}{2}\ptrzy=(\ln n + \ln \ln n +c_n)/n \text{ where } c_n\to\infty$$ then \begin{align*} &\Pra{\Gsuma\in \mathcal{HC}}\to 1. \end{align*} \end{lemma} \begin{proof}[Proof of Lemma~\ref{LematGnHamilton}] We will use the ideas from the proof of Theorem~8.9 \cite{KsiazkaBollobas}. Let $t=9n/\ln n$ and $ \phat_{4,0}=64\ln n/n^2. $ Then $ t\phat_{4,0}=\phat_4. $ For any graph $G$ let $l(G)$ be the length of the longest path in $G$ and $l(G)=n$ if $G$ has a Hamilton cycle. We say that $G$ has property $\mathcal{Q}$ if $$ \text{$G$ is connected\quad and }\quad|N_G(S)|\ge 2|S|\text{, for all }S\subseteq\V,|S|\le n/4. $$ In the proof we assume that $\Gsuma$ and $\rg(n)$ are defined on the probability space of the coupling existing by (i). Let $\rg_0=\rg(n)$ and $$ \rg_i=\rg_{i-1}\cup \Gn{\phat_{4,0}},\quad \text{ for }1\le i\le t. $$ By Lemma~\ref{LematGnCkPM}, assumptions (i)--(iii), and \eqref{RownanieNHC} {\whp} $\rg(n)$ has property $\mathcal{Q}$. Moreover by Lemma~\ref{LematWlasnosciGsuma}(v) and the coupling from assumption (i) {\whp} $$l(\rg_0)\ge \left(1-\frac{9\ln 2}{\ln n}\right)n .$$ It may be shown (see (8.7) in \cite{KsiazkaBollobas}) that \begin{multline*} \Pra{l(\rg_i) =n-t+i-1|l(\rg_{i-1})=n-t+i-1 \text{ and } \rg_{i-1} \text{ has $\mathcal{Q}$}}\\ \le(1-\phat_{4,0})^{n^2/32} \le n^{-2}. \end{multline*} Thus $$ \Pra{l(\rg_t)=n}\ge 1-\frac{t}{n^2}-o(1)=1-o(1). $$ Since $$ \rg_t\coupling \rg(n)\cup \Gn{t\phat_{4,0}}, $$ this finishes the proof. \end{proof} \section{Threshold functions}\label{SectionThresholds} \begin{proof}[Proof of Theorems~\ref{TwierdzenieSpojnosc}--\ref{TwierdzenieHamilton}] First let $S_1=n(\ln n + c_n)$ and $\pdwa$ and $\ptrzy$ be given by \eqref{RownanieHatp}. Then by Lemma~\ref{LematStopnie} $$ \lim_{n\to\infty}\Pra{\Gnmp\in\mathcal{C}_1}\le \lim_{n\to\infty}\Pra{\delta(\Gnmp)\ge 1}= f(c_n). $$ \noindent Moreover for $c_n=o(\ln n)$ by \eqref{RownanieHatp} and \eqref{RownanieSrelacje} we have \begin{equation*} \pdwa+\frac{n}{2}\ptrzy=\frac{\theta_n\ln n}{n}\text{ and } \pdwa=\frac{\theta'_n\ln n}{n}\text{ with }\theta_n\to 1\text{ and }\theta'_n\to 1/2. \end{equation*} Therefore by Theorem~\ref{LematCoupling} and Lemma~\ref{LematGsumaCkPM}(i) $$ \lim_{n\to\infty}\Pra{\Gnmp\in\mathcal{C}_1}\ge \lim_{n\to\infty}\Pra{\Gsuma\in\mathcal{C}_1}=f(c_n) $$ In the case $c_n=\Omega(\ln n)$ we may use the couplings described at the beginning of the proof of Lemma~\ref{LematStopnie}. This implies Theorem~\ref{TwierdzenieSpojnosc}(i). Similarly Theorem~\ref{TwierdzenieSpojnosc}(ii) follows by Theorem~\ref{LematCoupling}, Lemma~\ref{LematGsumaCkPM}(ii), and Lemma~\ref{LematStopnie2}; Theorem~\ref{TwierdzeniePM} by Theorem~\ref{LematCoupling}, Lemma~\ref{LematGsumaCkPM}(i), and Lemma~\ref{LematStopnie}; Theorem~\ref{TwierdzenieHamilton} by Theorem~\ref{LematCoupling}, Lemma~\ref{LematGsumaHamilton} and Lemma~\ref{LematStopnie2}. \end{proof} In the following proofs we will assume that $c_n=O(\ln n)$. In the other cases the theorems follow by Lemma~\ref{LematStopnie} or Theorem~\ref{LematCoupling} \eqref{RownanieCoupling1} combined with known results concerning $\Gn{\phat}$. \begin{proof}[Proof of Theorem~\ref{TwierdzenieHamiltonGp}] Let $c_n\to -\infty$, then by Lemma~\ref{LematStopniek} $$ \Pra{\Gnmpp\in\mathcal{HC}}\le \Pra{\delta(\Gnmpp)\ge 2}\to 0. $$ \noindent Let now $c_n\to\infty$. We will consider two cases: \noindent{\bf CASE 1:} $m= \Omega (n/\ln n)$. \noindent Let $$m'=m\left(1+\frac{700}{\ln n}\right)^{-1} \quad\text{and}\quad m''=\frac{700}{\ln n} m'. $$ Then for $p$ given by \eqref{RownanieHamiltonGp} $$ m'p(1-(1-p)^{n-1})= \ln n +\ln \max\left\{1,\frac{ np\ln n}{e^{np}-1}\right\} - 700 + o(1) + c_n $$ and \begin{equation}\label{Rownanienmpkwadrat} nm'p^2= \begin{cases} O(\ln n)&\text{for }np=O(1),\\ \frac{n}{m'}(m'p)^2=O(\ln^3n)&\text{for }np\to\infty. \end{cases} \end{equation} Let $\omega\to \infty$ slowly enough. Define \begin{align*} \pdwa&= \begin{cases}\frac{m'p(1-(1-p)^{n-1})-3m'p\left(\frac{1-(1-2p)^n}{2np}-(1-p)^{n-1}\right)-\omega\sqrt{\frac{\ln n}{n}}}{n}, \\ \hspace{3cm}\text{ for }nm'p\left(\frac{1-(1-2p)^n}{2np}-(1-p)^{n-1}\right)\gg\sqrt{n\ln n};\\ \frac{m'p(1-(1-p)^{n-1})-\omega\sqrt{\frac{\ln n}{n}}}{n}, \quad\text{ otherwise }; \end{cases}\\ \ptrzy&= \begin{cases} \frac{m'p\left(\frac{1-(1-2p)^n}{2np}-(1-p)^{n-1}\right)-\omega\sqrt{\frac{\ln n}{n}}}{\frac{n^2}{6}},\\ \hspace{3cm}\text{ for }nm'p\left(\frac{1-(1-2p)^n}{2np}-(1-p)^{n-1}\right)\gg\sqrt{n\ln n};\\ 0,\hspace{2.7cm}\text{ otherwise }; \end{cases} \\ \phat_4&=\textstyle\frac{m''p\left(1-\frac{1-(1-2p)^n}{2np}\right)-\omega\sqrt{\frac{1}{n}}}{n}. \end{align*} Moreover by \eqref{RownanieS} and \eqref{RownanieSrelacje}, for large $n$, \begin{align*} \phat_4 &=\textstyle\frac{m''p\left(1-\frac{1-(1-2p)^n}{2np}\right)-\omega\sqrt{\frac{1}{n}}}{n} =\textstyle \frac{\frac{700}{\ln n} \left(1+\frac{700}{\ln n}\right)^{-1}S_2-\omega \sqrt{n}}{n^2} = \frac{(1+o(1))700\cdot\frac{5}{6}\cdot S_1}{n^2\ln n}\ge \frac{576}{n}. \end{align*} Let now $\rg(n)=\Gnmprim{m'}$. Then by Theorem~\ref{LematCoupling} \begin{align} \Gsuma&\coup\Gnmprim{m'}=\rg(n)\label{RownanieCoupmprim};\\ \Gn{\phat_4}&\coup\Gnmprim{m''}\nonumber. \end{align} Moreover by Lemma~\ref{LematStopniek} {\whp} $\delta(\rg(n))\ge 2$. Therefore assumptions (i) and (ii) of Lemma~\ref{LematGnHamilton} are satisfied. We are left with proving that assumption (iii) is satisfied. Let $C$ be a positive integer. We will show that in the probability space of the coupling~\eqref{RownanieCoupmprim} {\whp} any two vertices of degree at most $C$ in $\Gsuma$ are at distance at least $5$ in $\Gnmprim{m'}=\rg(n)$. Therefore we need to study the couplings described in the proof of Theorem~\ref{LematCoupling}. If in the definitions of $S_1$, $S_3$, $M_2$ and $M_3$ we replace $m$ by $m'$ then proceeding as in the proof of Theorem~\ref{LematCoupling}, we may show that \begin{align*} &\Gsuma\\ &=\G{2}{\Po{\binom{n}{2}\ln(1-\pdwa)^{-1}}}\cup\G{3}{\Po{\binom{n}{3}\ln (1-\ptrzy)^{-1}}} \\ &\coupling^{(i)} \G{2}{\Po{\frac{S_1-3S_3-5\omega'\sqrt{S_1}}{2}}}\cup\G{3}{\Po{S_3-2\omega'\sqrt{S_1}}}\\ &\coup^{(ii)} \G{2}{\frac{S_1-3S_3-4\omega'\sqrt{S_1}}{2}}\cup\G{3}{S_3-\omega'\sqrt{S_1}}\\ &\coup^{(iii)} \G{2}{M_2} \cup \G{3}{M_3}=\bigcup_{1\le i \le m'}\left(\G{2}{\textstyle{\frac{Y_i-3Z_i}{2}}}\cup \G{3}{Z_i}\right)\\ &\coupling^{(iv)} \Gnmprim{m'} \end{align*} for some $\omega'=\Theta(\omega)$. In the probability space of the above couplings, we will find a relation between the degree of a vertex $v\in\V$ in $\Gsuma$ and the number of these features $w_i\in W(v)$ that are chosen by at least two vertices (i.e. the number of these features that contribute to at least one edge in $\Gnmprim{m'}$). For any $v\in\V$ in $\Gnmprim{m'}$ let $$W'(v)=\{w_i\in W(v): |V'_i|\ge 2\},$$ where $V'_i$ is defined in \eqref{RownanieVprim}. We will find a relation between the degree of a vertex $v$ in $\Gsuma$ and $|W'(v)|$ in $\Gnmprim{m'}$. To this end we will need an insight into the construction of the intermediary couplings (i)--(iv). Recall that in the coupling (iv), the construction of $\G{2}{M_2}\cup \G{3}{M_3}$ proceeds in $m'$ rounds. In the $i$-th round $\G{2}{\textstyle{(Y_i-3Z_i)/2}}\cup \G{3}{Z_i}$ is constructed in $\frac{Y_i-3Z_i}{2}+Z_i$ draws. In each draw a hyperedge of size $2$ or $3$ in $\mathbb{H}_{*2}((Y_i-3Z_i)/2)\cup \mathbb{H}_{*3}(Z_i)$ is chosen. Then $V_i'$ (in $\Gnmprim{m'}$) is formed from non isolated vertices of $\mathbb{H}_{*2}((Y_i-3Z_i)/2)\cup \mathbb{H}_{*3}(Z_i)$ and possibly some extra vertices. The number of extra vertices equals $Y_i$ minus the number of non isolated vertices in $\mathbb{H}_{*2}((Y_i-3Z_i)/2)\cup \mathbb{H}_{*3}(Z_i)$ (i.e. also in $\G{2}{(Y_i-3Z_i)/2}\cup\G{3}{Z_i}$). We will show that {\whp} for each $v\in \V$ there is at most one $w_i\in W'(v)$ such that $v$ is isolated in $\mathbb{H}_{*2}((Y_i-3Z_i)/2)\cup \mathbb{H}_{*3}(Z_i)$. This will prove that {\whp} for each $v\in\V$ the number of draws in which a hyperedge containing $v$ is chosen is at least $|W'(v)|-1$. Given $v\in \V$ and $1\le i\le m'$, denote by $\mathcal{A}_{v,i,1}$ the event that $v$ is an isolated vertex in $\G{2}{(Y_i-3Z_i)/2}\cup\G{3}{Z_i}$ and by $\mathcal{A}_{v,i,2}$ the event that $v\in V_i'$. We will use these events to compare the number of hyperedges in $\bigcup_{i}\mathbb{H}_{*2}((Y_i-3Z_i)/2)\cup \mathbb{H}_{*3}(Z_i)$ containing $v$ with the number of features $w_i$ such that $v\in V_i'$ (i.e. with the number $|W'(v)|$). Denote by $\mathcal{A}_v$ the event that while constructing $\G{2}{M_2} \cup \G{3}{M_3}$ there are less than $|W'(v)|-1$ draws in which a hyperedge containing $v$ is chosen. Then $$\mathcal{A}_v\subseteq \bigcup_{i\neq j} (\mathcal{A}_{v,i,1}\cap\mathcal{A}_{v,i,2}) \cap (\mathcal{A}_{v,j,1}\cap\mathcal{A}_{v,j,2}).$$ For $i\neq j$, $(\mathcal{A}_{v,i,1}\cap\mathcal{A}_{v,i,2})$ and $(\mathcal{A}_{v,j,1}\cap\mathcal{A}_{v,j,2})$ are independent and $$\Pra{\mathcal{A}_{v,i,1}\cup\mathcal{A}_{v,i,2}}=1,$$ thus \begin{align*} \Pra{\mathcal{A}_v} & \le \binom{m'}{2}\left(\Pra{\mathcal{A}_{v,1,1}\cap\mathcal{A}_{v,1,2}}\right)^2\\ & = \binom{m'}{2}\left(\Pra{\mathcal{A}_{v,1,1}}+\Pra{\mathcal{A}_{v,1,2}}-1\right)^2 \\ &\le\binom{m'}{2} \Bigg( (1-p)^{n} +np(1-p)^{n-1} \\ &\hspace{2cm}+\sum_{y=2}^{n-1} \binom{n}{y}p^y(1-p)^{n-y} \left(1-\frac{1}{n}\right)^y +p^{n}\cdot 0\\ &\hspace{2cm} +\sum_{y=2}^{n} \binom{n}{y}p^y(1-p)^{n-y} \frac{y}{n} -1 \Bigg)^2\\ &=\binom{m'}{2} \Bigg( \sum_{y=0}^{n} \binom{n}{y}p^y(1-p)^{n-y} \left(1-\frac{1}{n}\right)^y -p^{n}\\ &\hspace{2cm}+\sum_{y=1}^{n} \binom{n}{y}p^y(1-p)^{n-y} \frac{y}{n} -1 \Bigg)^2\\ &\le\binom{m'}{2} \left( \left(1-\frac{p}{n}\right)^n +p-1 \right)^2 \le (m')^2p^4. \end{align*} Therefore by \eqref{Rownanienmpkwadrat} \begin{equation}\label{RownanieAv} \Pra{\bigcup_{v\in\V}\mathcal{A}_v}\le n(m')^2p^4=O\left(\frac{\ln^6n}{n}\right)=o(1). \end{equation} Thus in the probability space of the couplings, {\whp} for all $v\in\V$ in the construction of $\G{2}{M_2}\cup\G{3}{M_3}$ the number of draws in which a hyperedge containing $v$ is chosen is at least $|W'(v)|-1$. Now we will find a relation between the number of draws in the construction of $\G{2}{M_2}\cup\G{3}{M_3}$ and the number of draws in the construction of \begin{multline*} \Gsuma\\ =\G{2}{\Po{\binom{n}{2}\ln(1-\pdwa)^{-1}}}\cup\G{3}{\Po{\binom{n}{3}\ln (1-\ptrzy)^{-1}}}. \end{multline*} Note that in the couplings (i)--(iii) in order to construct a graph $\G{2}{M_2} \cup \G{3}{M_3}$ from $\Gsuma$ one performs some additional draws of hyperedges in auxiliary hypergraphs $\mathbb{H}_{*2}(n,\cdot)\cup \mathbb{H}_{*3}(n,\cdot)$. By the sharp concentration of the Poisson distribution and \eqref{RownanieYikoncentracja} {\whp} the number of additional draws is at most $K\omega\sqrt{n\ln n}$ for some constant $K$. Under the condition that the number of additional draws is at most $K\omega\sqrt{n\ln n}$, probability that a hyperedge containing $v$ is chosen in at least $3$ of the additional draws is at most $$ \binom{K\omega\sqrt{n\ln n}}{3}\left(\frac{2}{n}\right)^3=o(n^{-1}). $$ Therefore, by the union bound, {\whp} in additional draws for each vertex $v\in\V$ a hyperedge containing $v$ is chosen at most 2 times. Combining this with \eqref{RownanieAv} we obtain that {\whp} for all $v\in\V$ in the construction of $\Gsuma$ the number of draws in which a hyperedge containing $v$ is chosen is at least $|W'(v)|-3$. Now we will show the relation between the number of draws of hyperegdes and the number of edges incident to $v$ in $\Gsuma$. The difference between the numbers is due to the fact that hyperedges containing given pair of vertices (edge) might be drawn several times in the hypergraph $\mathbb{H}_{*2}(n,\cdot)\cup \mathbb{H}_{*3}(n,\cdot)$ but there is only one edge in $\Gsuma$. Therefore the number of draws might exceed the number of edges. Note that the number of draws made in the construction of $\Gsuma$ is a random variable with the expected value at most $S_1=O(n\ln n)$. Therefore by Markov's inequality {\whp} the number of draws made in the construction of $\Gsuma$ is at most $n\ln^2 n$. In addition the probability that a pair $\{v,v'\}$ is contained in a hyperedge chosen in a given draw is at most $6/n(n-1)$. Therefore the probability that there exists an edge in $\Gsuma$ drawn at least $3$ times during the construction is at most $$ \binom{n}{2}\binom{n\ln^2 n}{3}\left(\frac{6}{n(n-1)}\right)^3+o(1)=o(1). $$ In conclusion, {\whp} for all $v\in\V$ the number of edges incident to $v$ in $\Gsuma$ is at least half of the number of drawn hyperedges containing $v$, which is {\whp} at least $(|W'(v)|-3)/2$. Thus in the probability space of the couplings {\whp} for all $v\in\V$ of degree at most $C$ in $\Gsuma$ we have $|W'(v)|\le 2C+3$. Finally, the probability that there are two vertices $v,v'$ such that $|W'(v)|\le 2C+3$ and $|W'(v')|\le 2C+3$ connected by a path of length at most $4$ in $\Gnmprim{m'}$ is at most \begin{align*} &n^2 \sum_{t=1}^{4} (m')^tn^{t-1}p^{2t}\\ &\cdot\left( \sum_{l=0}^{2C+3} \binom{m'-t}{l} (p-p(1-p)^{n-1})^l\left[(1-p)+p(1-p)^{n-1}\right]^{m'-O(1)} \right)^2\\ &=O(1)n(\ln n)^{O(1)} \exp\left(-2m'p(1-(1-p)^{n-1})\right)\\ &=o(1). \end{align*} This shows that assumption (iii) of Lemma~\ref{LematGnHamilton} is fulfilled. Therefore by Lemma~\ref{LematGnHamilton} {\whp} $$ \rg(n)\cup\Gn{\frac{576}{n}}\in \mathcal{HC}. $$ Thus in the case $m = \Omega(n/\ln n)$ the theorem follows by \eqref{RownanieCoupmprim} and a straightforward coupling of random intersection graphs. $$ \rg(n)\cup\Gn{\frac{576}{n}} \coup \Gnmprim{m'}\cup\Gnmprim{m''} \coupling \Gnmpp. $$ \noindent{\bf CASE 2:} $m = o (n/\ln n)$.\\ Note that in this case \eqref{RownanieHamiltonGp} and $c_n=O(\ln n)$ imply that $$ p=\frac{\ln n + c'_n}{m} $$ for some $c'_n\to\infty$. Let $m'$ be such that $m$ divides $m'$ and $m'\sim n/\ln n$. Take an instance of $\mathcal{G}(n,m',p')$ with the set of features $\W'$ of size $m'$ and $$ p'=\frac{\ln n + c'_n}{m'}. $$ Divide $\W'$ into $m$ groups of $m'/m$ features. Denote by $A_i$ the set of vertices which have chosen features from the $i$--th, $1\le i \le m$, group in $\mathcal{G}(n,m',p')$. $|A_i|$ has binomial distribution $\Bin{n}{p''}$ for some $p''\le \frac{m'}{m}p'=p$. Now take an instance of $\mathcal{G}(n,m',p')$ and construct the sets $V_i$, $1\le i \le m$, in $\Gnmpp$ by taking $A_i$ and additionally adding to $V_i$ each vertex from $\V\setminus A_i$ independently with probability $(p-p'')/(1-p'')$. This coupling implies $$ \mathcal{G}(n,m',p')\coupling \Gnmpp. $$ From the considerations concerning the first case we have that {\whp} $\mathcal{G}(n,m',p')\in\mathcal{HC}$. Therefore also $\Gnmpp\in\mathcal{HC}$ {\whp} . \end{proof} \begin{proof}[Proof of Theorem~\ref{TwierdzenieSpojnosckGp}] The technique of the proof is analogous to the technique of the proof of Theorem~\ref{TwierdzenieHamiltonGp}. We consider two cases $m=\Omega(n/\ln n)$ and $m=o(n/\ln n)$. In the first case the proof relies on Lemma~\ref{LematStopniek} and Lemma~\ref{LematGnCkPM}. Moreover we have to use the fact shown in the proof of Theorem~\ref{TwierdzenieHamiltonGp}, that in the coupling constructed in the proof of Theorem~\ref{LematCoupling} {\whp} the vertices of degree bounded by a constant in $\Gsuma$ are at distance at least $5$ in $\Gnmpp$. The proof of the case $m=o(n/\ln n)$ is the same as in the proof of Theorem~\ref{TwierdzenieHamiltonGp}. \end{proof} \section*{Appendix} \appendix \section{Proof of \eqref{RownanieSrelacje}} For $0 q_+$, similarly, we first choose with repetition $q_+$ edges and add them to the both graphs. Then we choose $q-q_+$ additional edges and add them only to $\G{2}{Q_2}$. By \eqref{RownanieMtkoncentracja} {\whp} $Q_2\le q_+$ thus the coupling described above implies $\Gnm{2}{\overline{p}}=\G{2}{Q_2}\coup \G{2}{q_+}$. Moreover $q_+$ is a number (not a random variable) and choices of edges in $\G{2}{q_+}$ are independent of choices of edges in $\Gnm{\neq 2}{\overline{p}}$. Therefore $\G{2}{q_+}$ and $\Gnm{\neq 2}{\overline{p}}$ are independent. The coupling $(**)$ is analogous to the one constructed in \eqref{RownanieCoupligPrzezPoisson}. Namely, we use the coupling $\G{2}{q_+}\coup \G{2}{\Po{(S_{1,2}+2\omega\sqrt{S_{1,2}})/2}}\coupling\Gn{\phat_{2+}}$ (the last coupling follows by \eqref{RownanieGstarPoisson} and inequality $1-e^{-x}\le x$). Now we will study properties of $\Gn{\phat_{+2}}\cup \Gnm{\neq 2}{\overline{p}}$. We will show that {\whp} there exists a vertex which is isolated in $\Gnm{\neq 2}{\overline{p}}$ and has degree at most $k-1$ in $\Gn{\phat_{+2}}$. The construction of $\Gnm{\neq 2}{\overline{p}}$ may be coupled with the vertex collector process described in the proof of Lemma~\ref{LematStopnie}. This coupling proceeds in the same way as the coupling of the construction of $\Gnmp$ and the vertex collector process, with one change: one omits the phases with $Y_i=2$. By \eqref{RownanieTY} and \eqref{RownanieMtbrakkoncentracja}, in the coupling {\whp} the construction of $\Gnm{\neq 2}{\overline{p}}$ is finished before $$ T_{2+}=S_1-S_{1,2}+2\omega\sqrt{S_1}+\frac{S_1}{\omega \ln n} $$ draws, for $\omega\to\infty$. Moreover, in the coupling, every vertex which has not been collected by the end of the process, is isolated in $\Gnm{\neq 2}{\overline{p}}$. Therefore we need to show that {\whp} there exists a vertex of degree $k-1$ in $\Gn{\phat_{+2}}$ and is not collected in $T_+$ draws of the vertex collector process independent of $\Gn{\phat_{+2}}$. Take any probability space on which we define the vertex collector process on $\V$ and $\Gn{\phat_{2+}}$, in such a manner that they are independent. Let $X_{+}$ be a random variable counting vertices which have not been collected during the vertex collector process in $T_{2+}$ draws and have degree $k-1$ in $\Gn{\phat_{2+}}$. If $$S_1=n(\ln n + (k-1)\ln (a_n\ln n) + c_n)$$ then for $\omega$ tending to infinity slowly enough \begin{align*} \frac{1}{n}T_{2+} + (n-k)\phat_{2+} &=\frac{1}{n}\left( S_1+O\left(\omega\sqrt{S_1}+\frac{S_1}{\omega\ln n}\right)\right)\\ &=\ln n + (k-1)\ln(a_n\ln n) + c_n + o(1) \end{align*} and \begin{align*} \phat_{2+} \sim \frac{S_{1,2}}{n^2}=a_n\frac{S_1}{n^2} \sim \frac{a_n \ln n}{n}. \end{align*} Therefore \begin{align*} \EE X_+ %\label{RownananieXpm1} =& n\left(1-\frac{1}{n}\right)^{T_{2+}} \binom{n-1}{k-1}\phat_{2+}^{k-1}(1-\phat_{2+})^{n-k} \\ \nonumber \sim& n\frac{1}{(k-1)!}(a_n\ln n)^{k-1} \exp(-\ln n - (k-1)\ln(a_n\ln n) - c_n)\\ \sim& \frac{e^{-c_n}}{(k-1)!}\\ \intertext{and (as $n\phat_{2+}\sim a_n\ln n\to \infty$)} \EE X_+(X_+-1) %\label{RownanieXpm2} \sim& n^2\left(1-\frac{2}{n}\right)^{T_{2+}}(1-\phat_{2+}) \left(\binom{n-2}{k-1}\phat_{2+}^{k-1}(1-\phat_{2+})^{n-k-1}\right)^2 \\ \nonumber&\ +n^2\left(1-\frac{2}{n}\right)^{T_{2+}} \phat_{2+}\left(\binom{n-2}{k-2}\phat_{2+}^{k-2}(1-\phat_{2+})^{n-k}\right)^2\\ \nonumber \sim& \left(\frac{e^{-c_n}}{(k-1)!}\right)^2. \end{align*} Thus by the second moment method {\whp} $X_+>0$ as $c_n\to -\infty$. By \eqref{RownanieTY}, \eqref{RownanieMtbrakkoncentracja}, and the coupling of $\Gnm{\neq 2}{\overline{p}}$ with the vertex collector process we have that {\whp} there is a vertex which is isolated in $\Gnm{\neq 2}{\overline{p}}$ and has degree at most $k-1$ in $\Gn{\phat_{2+}}$. Thus by coupling \eqref{RownanieStopnieCoupling} {\whp} there is a vertex of degree at most $k-1$ in $\Gnmp$, i.e. $$ \lim_{n\to\infty}\Pra{\delta(\Gnmp)\ge k}=0. $$ \end{proof} \begin{proof}[Proof of Lemma~\ref{LematStopnie2} (ii)] Let $$ S_1-\sum_{t=3}^{k}S_{1,t}=n\left(\ln n+(k-1)\ln \left(\max\left\{1, \left(\frac{S_{1,2}}{S_1}\ln n\right)\right\}\right) + c_n\right) \text{ with }c_n\to \infty. $$ If $S_1\gg n\ln n$ then by Theorem~\ref{LematCoupling} and the classical results concerning $\Gn{\phat}$ with $\phat\gg \ln n/n$ we have $$ 1=\lim_{n\to\infty}\Pra{\delta(\Gn{\phat})\ge k}\le \lim_{n\to\infty}\Pra{\delta(\Gnmp)\ge k}. $$ Now let $S_1 = O(n\ln n)$. If $S_{1,2}/S_1=O(1/\ln n)$ and $S_1 = O(n\ln n)$ then $S_1-\sum_{t=3}^{k}S_{1,t} = n(\ln n + O(1) + c_n)$. In this case we use the same reasoning as in the proof of Lemma~\ref{LematStopnie}. We construct a coupling of the vertex collector process and the construction of $\Gnm{\ge k+1}{\overline{p}}$. By \eqref{RownanieTY} and \eqref{RownanieM3koncentracja} the construction of $\Gnm{\ge k+1}{\overline{p}}$ does not finish before $$T_-=S_1-\sum_{t=3}^{k}S_{1,t}-k\sqrt{S_1}= n(\ln n + O(1) + c_n)$$ draws (recall that $\sqrt{S_1}=O(\sqrt{n\ln n})$). Therefore by the coupling and the classical results on the vertex collector process \cite{CouponCollector} {\whp} there is no isolated vertex in $\Gnm{\ge k+1}{\overline{p}}$. Thus $$ \lim_{n\to\infty}\Pra{\delta(\Gnmp)\ge k}=1. $$ We are left with the case $S_1 = O(n\ln n)$ (which implies $c_n=O(\ln n)$) and $a_n=S_{1,2}/S_1\gg 1/\ln n$ (which implies $S_{1,2}\to\infty$ and $a_n\ln n\to\infty$). The proof uses the same techniques as the proof of Lemma~\ref{LematStopnie2}(i). As in \eqref{RownanieStopnieCoupling} we may construct couplings \begin{equation}\label{RownanieStopnieCoupling2} \Gn{\phat_{2-}}\cup \Gnm{\ge k+1}{\overline{p}} \coup \Gnm{2}{\overline{p}}\cup \Gnm{\ge k+1}{\overline{p}}\coupling \Gnmp, \end{equation} where $\phat_{2-} = (S_{1,2}-2\omega\sqrt{S_{1,2}})/2\binom{n}{2}$ and graphs $\Gn{\phat_{2-}}$ and $\Gnm{\ge k+1}{\overline{p}}$ are independent. Moreover we may couple a construction of $\Gnm{\ge k+1}{\overline{p}}$ with the vertex collector process in such a manner that {\whp} $\Gnm{\ge k+1}{\overline{p}}$ is constructed in at least $$T_-=S_1-\sum_{t=3}^{k}S_{1,t}-k\sqrt{S_1}= n(\ln n + \ln \left(\max\{1,a_n\ln n\}\right) + c_n + o(1))$$ draws. Consider any probability space on which we define the vertex collector process on $\V$ and $\Gn{\phat_{2-}}$, in such a manner that they are independent. Let $X_{-}$ be a random variable defined on this probability space equal to the number of vertices which have not been collected during the vertex collector process with $T_-$ draws and have degree at most $k-1$ in $\Gn{\phat_{2-}}$. If $S_1-\sum_{t=3}^{k}S_{1,t}=n(\ln n + (k-1)\ln (a_n\ln n) + c_n)$ then for $\omega$ tending to infinity slowly enough \begin{align*} \frac{1}{n}T_- + (n-k)\phat_{2-} &\ge\frac{1}{n}\left( S_1-\sum_{t=3}^{k-1}S_{1,t}+O\left(\omega\sqrt{S_1}+S_{1}^2n^{-2}\right)\right)\\ &=\ln n + (k-1)\ln(a_n\ln n) + c_n + o(1). \end{align*} Moreover \begin{align*} \phat_{2-} \sim \frac{S_{1,2}}{n^2}=a_n\frac{S_1}{n^2} =\Theta\left( \frac{a_n \ln n}{n}\right) \end{align*} and $ n\phat_{2-}=\Theta(a_n\ln n) $ tends to infinity. Thus \begin{align*} \EE X_- %\label{RownananieXpm1} &= n\left(1-\frac{1}{n}\right)^{T_{-}} \left(\sum_{i=0}^{k-1}\binom{n-1}{i}\phat_{2-}^{i}(1-\phat_{2-})^{k-1-i}\right) (1-\phat_{2-})^{n-k}\\ \nonumber &= O(1) n\frac{1}{(k-1)!}(a_n\ln n)^{k-1} \exp(-\ln n - (k-1)\ln(a_n\ln n) - c_n)\\ &= O(1) \frac{e^{-c_n}}{(k-1)!} \end{align*} Therefore {\whp} $X_-=0$, i.e. {\whp} each vertex is collected in $T_-$ draws or has degree at least $k$ in $\Gn{\phat_{2-}}$. Note that if each vertex is non-isolated in $\Gnm{k+1}{\overline{p}}$ or has degree at least $k$ in $\Gnm{2}{\overline{p}}$, then $\delta(\Gnmp)\ge k$. Therefore coupling \eqref{RownanieStopnieCoupling2} implies that {\whp} $\delta(\Gnmp)\ge k$. \end{proof} Before we proceed with the proof of Lemma~\ref{LematStopniek} we start with discussion on the structure of $\Gnmpp$. From now on for $\overline{p}=(p,\ldots,p)$ we replace $\overline{p}$ by $p$ in notations $\Gnm{t}{\overline{p}}$, $\Gnm{\ge k+1}{\overline{p}}$, $\Gnm{\neq t}{\overline{p}}$. Note that if $np\gg \ln m$ then {\whp} $\bigcup_{t=2}^{k} \Gnm{t}{p}$ is empty. Therefore the number of vertices of degree at most $k-1$ is the number of isolated vertices in $\Gnm{\ge k+1}{p}$ (i.e. it might be approximated by the number of non--collected vertices in the vertex collector process). On the other hand if $np=o(m^{-1/3})$) then {\whp} $\Gnmp=\Gnm{2}{p}$ and the number of vertices of degree at most $k-1$ may be counted in the same manner as in a graph with independent edges. The proof of Lemma~\ref{LematStopniek} provides the discussion about what happens for $np$ in between. \begin{proof}[Proof of Lemma~\ref{LematStopniek}] Let $$ a_n=a_n(p)= (np)^{k-1} \left( \left(\frac{\ln n}{e^{np}-1}\right)^{k-1}+\frac{\ln n}{e^{np}-1}\right). $$ First we will prove that we may restrict our attention to the case $S_1\sim n\ln n$ (i.e. $c_n=o(\ln n)$). Recall that $p(1-(1-p)^{n-1})=S_1/nm$. Moreover, note that $0\le \ln \max\{1,a_n\}\le (k-1) \ln \ln n + O(1)=o(\ln n)$. Therefore, by monotonicity and continuity of $f(x)=x(1-(1-x)^{n-1})$, for any $p$ with $c_n=\Omega(\ln n)$, $c_n\to-\infty$, there exists $p'$, $p\le p'$, with $c'_n=o(\ln n)$, $c_n'\to-\infty$, such that \begin{multline*} p(1-(1-p)^{n-1}) =\frac{\ln n + \ln \max\{1,a_n(p)\} + c_n}{m} \le\\ \frac{\ln n + \ln \max\{1,a_n(p')\} + c'_n}{m} = p'(1-(1-p')^{n-1}). \end{multline*} Thus $$ \Pra{\Gnmpp\in {\cal C}_k}\le \Pra{\Gnm{}{p'}\in {\cal C}_k}. $$ An analogous statement is true for $p$ with $c_n\to \infty$ and $p'\le p$ with $c_n'=o(\ln n)$ and $c_n'\to\infty$. From now on we assume that $c_n=o(\ln n)$. Note that if $m\gg \ln^2 n$ then $p = O\left(p(1-(1-p)^{n-1})\right) = O\left(\ln n/ m\right)=o\left(1/\ln n\right)$. This will allow us to use Lemmas~\ref{LematStopnie} and~\ref{LematStopnie2}. We will also use some relations between $a_n$ and values $S_{1,t}$, $t=2,k$. By \eqref{RownanieS} \begin{equation*} S_{1,t}\sim m\frac{(np)^{t}}{(t-1)!}(1-p)^{n-t} = ((t-1)!)^{-1}\frac{(np)^{t-1}(1-p)^{n-t}}{1-(1-p)^{n-1}}S_1, \quad\text{for }t=2,\ldots,k, \end{equation*} where $S_1$ and $S_{1,t}$ are defined by \eqref{RownanieS}. Therefore for $p=o(1)$ \begin{equation}\label{RownanieS1tS1} S_{1,t}\sim ((t-1)!)^{-1}\frac{(np)^{t-1}}{(1-p)^{-n}-1}S_1, \quad\text{for }t=2,\ldots,k. \end{equation} Moreover if $np^2=o(1)$ then \begin{equation}\label{RownanieS1tan} \left(\frac{S_{1,2}}{S_1}\ln n\right)^{k-1} + (k-1)!\frac{S_{1,k}}{S_1}\ln n \sim a_n. \end{equation} We will divide the proof into cases depending on the value $a_n$ (or equivalently $np$). \bigskip \noindent {\bf CASE 1.} $a_n=O(1)$ (i.e. $np\ge \ln\ln n + (k-1)\ln\ln\ln n + d$, for some $d\in\mathbb{R}$). \smallskip \noindent In this case $S_{1,t}/S_1=O(1/\ln n)$ for $2\le t\le k$. Moreover $\ln (\max\{1,a_n\})=O(1)$. Therefore $S_1=n(\ln n + O(1) + c_n)$ and $S_1-\sum_{t=3}^{k}S_{1,t}=n(\ln n + O(1) + c_n)$. Thus the result follows by Lemma~\ref{LematStopnie2}. \bigskip \noindent {\bf CASE 2.} $a_n\to \infty$ (i.e. $np\le \ln\ln n + (k-1)\ln\ln\ln n - \omega$, for some $\omega\to \infty$). \smallskip \noindent First let $c_n\to -\infty$. \smallskip Here we distinguish between $a_n\sim ((k-1)! S_{1,k}\ln n)/S_1$ (i.e. $\ln \ln n + \omega \le np\le \ln\ln n + (k-1)\ln\ln\ln n - \omega$, for some $\omega\to \infty$) and $a_n = \Theta((S_{1,2}\ln n/S_1)^{k-1})$ (i.e. $np\le \ln \ln n + d$ for some $d\in{ \mathbb R}$). For $a_n\sim (k-1)! S_{1,k}\ln n/S_1$ and $a_n\to\infty$ we use the following division and couplings. \begin{multline}\label{RownanieStopnieCoupling3} \Gnmpp=\Gnm{k}{p}\cup \Gnm{\neq k}{p} \coup\\ \G{k}{\frac{S_{1,k}+\omega\sqrt{S_{1,k}}}{k}}\cup \Gnm{\neq k}{p} \coup G_k(n,{\phat_{k+}})\cup \Gnm{\neq k}{p}, \end{multline} where $\phat_{k+}=(S_{1,k}+2\sqrt{S_{1,k}})/k\binom{n}{k}$ (for more details on the construction of the couplings see \eqref{RownanieStopnieCoupling}). As in the proof of Lemma~\ref{LematStopnie2} the construction of $\Gnm{\neq k}{p}$ in $G_k(n,{\phat_{+k}})\cup \Gnm{\neq k}{p}$ may be coupled with the vertex collector process on $\V$. Moreover by \eqref{RownanieMtbrakkoncentracja} and \eqref{RownanieTY} {\whp} the construction of $\Gnm{\neq k}{p}$ is finished in at most $$ T_{k+}=S_1-S_{1,k}+2\omega\sqrt{S_1}+\frac{S_1}{\omega\ln n} $$ draws, for $\omega\to\infty$. Take any probability space on which we define independent: the vertex collector process on $\V$ and $G_{k}(n,\phat_{k+})$. Let $X_{+}$ be a random variable equal to the number of vertices which have not been collected during the vertex collector process in $T_{k+}$ draws and have degree $k-1$ in $G_k(n,\phat_{k+})$. For $\omega$ tending to infinity slowly enough \begin{align*} \frac{1}{n}T_{k+} + \binom{n-1}{k-1}\phat_{k+} &=\frac{1}{n}\left( S_1+O\left(\omega\sqrt{S_1}+\frac{S_1}{\omega\ln n}\right)\right)\\ &=\ln n + \ln a_n + c_n + o(1). \end{align*} and by \eqref{RownanieS1tan} $$ p_{k+}\sim \frac{S_{1,k}}{k\binom{n}{k}} \sim \frac{\frac{a_n S_1}{(k-1)!\ln n}}{n\binom{n-1}{k-1}} \sim \frac{a_n}{(k-1)!\binom{n-1}{k-1}} $$ Thus \begin{align*} \EE X_+ %\label{RownananieXpm1} =& n\left(1-\frac{1}{n}\right)^{T_{k+}} \binom{n-1}{k-1}\phat_{k+}(1-\phat_{k+})^{\binom{n-1}{k-1}-1} \\ \sim& n\cdot\binom{n-1}{k-1}\cdot\frac{a_n}{(k-1)!\binom{n-1}{k-1}} \cdot\exp\left(-\frac{T_{k+}}{n}-\binom{n-1}{k-1}p_{k+}\right) \\ \sim& n\frac{1}{(k-1)!}a_n \exp(-\ln n - \ln a_n - c_n)\\ \sim& \frac{e^{-c_n}}{(k-1)!}\\ \intertext{and similarly} \EE X_+(X_+-1) \sim& n^2 \left(1-\frac{2}{n}\right)^{T_{k+}}\\ &\cdot\Big[ \left( \binom{n-2}{k-1}\phat_{k+} \right)^2 (1-\phat_{k+})^{2\binom{n-1}{k-1}-\binom{n-2}{k-2}-2}\\ & + \binom{n-2}{k-2}\phat_{k+} (1-\phat_{k+})^{2\binom{n-1}{k-1}-\binom{n-2}{k-2}-1} \Big]\\ \sim& \left(\frac{e^{-c_n}}{(k-1)!}\right)^2. \end{align*} Thus by the second moment method {\whp} $X_+>0$ as $c_n\to -\infty$ (i.e. {\whp} there exists a vertex, which has degree at most $k-1$ in $G_k(n,\phat_{k+})$ or has not been collected in $T_{k+}$ draws). Thus by \eqref{RownanieTY}, \eqref{RownanieMtbrakkoncentracja}, \eqref{RownanieStopnieCoupling3}, and the coupling of $\Gnm{\neq k}{p}$ with the vertex collector process {\whp} $$ \lim_{n\to\infty}\Pra{\delta(\Gnmpp)\ge k}= 0. $$ We are left with $a_n = \Theta((S_{1,2}\ln n/S_1)^{k-1})$. Then $$ S_1=n(\ln n + (k-1)\ln \left(\max\left\{1,\frac{S_{1,2}\ln n}{S_1}\right\}\right) + O(1) + c_n). $$ Therefore the result follows by Lemma~\ref{LematStopnie2}(i) \bigskip \noindent Now assume that $c_n\to \infty$. \smallskip Here we use the couplings \begin{equation}\label{RownanieStopnieCoupling4} \begin{split} &\bigcup_{t=2}^{k}G_t(n,{\hat{q}_{t}}) \cup \Gnm{\geq k+1}{p} \\ &\coup \bigcup_{t=2}^{k}\G{t}{ \max\left\{0,\frac{S_{1,t}-\omega\sqrt{S_{1,t}}}{t}\right\} }\cup \Gnm{\geq k+1}{p} \\ &\coup \bigcup_{t=2}^{k}\Gnm{t}{p}\cup \Gnm{\geq k+1}{p}\\ &=\Gnmpp \end{split} \end{equation} where $$ \hat{q}_{t} = \begin{cases} 0,&\text{for } S_{1,t}=O(\omega\sqrt{S_{1}});\\ \frac{S_{1,t}-2\omega\sqrt{S_{1}}-t!S_{1,t}^2n^{-2}}{t\binom{n}{t}},&\text{otherwise}. \end{cases} $$ Therefore \begin{equation}\label{Rownanieqminus} \binom{n-1}{t-1}\hat{q}_{t}\ge S_{1,t}-O(\omega\sqrt{S_{1}}) \end{equation} and by \eqref{RownanieS} $$ \hat{q}_{t}\le \frac{S_{1,t}}{t\binom{n}{t}}= O\left(mp^{t}e^{-np}\right). $$ Take any probability space on which we may define independent: the vertex collector process and $\bigcup_{t=2}^{k}G_{t}(n,\hat{q}_{t})$. Let $X_{-}$ be a random variable equal to the number of vertices which have not been collected during the vertex collector process in \begin{equation}\label{RownanieTminus} T_-=S_1-\sum_{t=3}^{k}S_{1,t}-k\sqrt{S_1} \end{equation} draws and have degree at most $k-1$ in $\bigcup_{t=2}^{k}G_t(n,\hat{q}_{t})$. Note that if $v$ has degree at most $k-1$ in $\bigcup_{t=2}^{k}G_t(n,\hat{q}_{t})$, then for some $0\le k_0\le k-1$ and some sequence of integers $r_2,\ldots,r_t$ such that $\sum_{t=2}^{k}(t-1)r_t=k_0$ \begin{itemize} \item[(i)] there is a set $\V'\subseteq \V\setminus\{v\}$ of $k_0$ vertices such that for each $t$ there are $r_t$ hyperedges in $H_t(n,\hat{q}_{t})$ (generating $G_t(n,\hat{q}_{t})$) containing $v$ and contained in $\V'\cup\{v\}$. \item[(ii)] and all hyperedges in $\bigcup_{t=2}^{k}H_t(n,\hat{q}_{t})$ containing $v$ are subsets of $\V'\cup\{v\}$. \end{itemize} Let $r=\sum_{t=2}^{k}r_t$. Given a sequence $r_2,\ldots,r_t$ such that $\sum_{t=2}^{k}(t-1)r_t=k_0$, if $c_n=O(\ln n)$ then event (i) occurs with probability at most \begin{align*} & \binom{n-1}{k_0}\prod_{t=2}^{k}\binom{k_0-1}{t-1}^{r_t}\left(O(1)(mp^{t})e^{-np}\right)^{r_t}\\ &=O(1)n^{k_0}m^{r}p^{k_0+r}\left(e^{-np}\right)^{r}\\ &=O(1)(np)^{k_0}(mpe^{-np})^{r}\\ &=O(1)(np)^{k_0}\left(\frac{\ln n}{(1-e^{-np})}e^{-np}\right)^r\\ &=O(a_n). \end{align*} In the penultimate equality we have used the fact that $mp(1-e^{-np}) \sim \ln n$. There are $O(1)$ sequences of integers $r_2,\ldots,r_t$ such that $\sum_{t=2}^{k}(t-1)r_t\le k-1$, thus the probability that there exists such sequence $r_2,\ldots,r_t$ that (i) and (ii) occur is at most $$ O(a_n)\prod_{t=2}^{k}(1-\hat{q}_{t})^{\binom{n-1}{t-1}-\binom{k-1}{t-1}}. $$ Moreover by \eqref{Rownanieqminus} and \eqref{RownanieTminus} \begin{align*} \frac{1}{n}T_- + \sum_{t=2}^{k}\binom{n-1}{t-1}\hat{q}_{t} &\ge\frac{1}{n}\left( S_1-O\left(\omega\sqrt{S_1}+S_{1}^2n^{-2}\right)\right)\\ &=\ln n + \ln a_n + c_n + o(1). \end{align*} Therefore finally \begin{align*} \EE X_- %\label{RownananieXpm1} &= n\left(1-\frac{1}{n}\right)^{T_{-}} O(a_n)\prod_{t=2}^{k}(1-\hat{q}_{t})^{\binom{n-1}{t-1}-\binom{k-1}{t-1}}=o(1). \end{align*} Hence {\whp} $X_-=0$. Thus by \eqref{RownanieMtkoncentracja}, \eqref{RownanieStopnieCoupling4} and the coupling of the construction of $\Gnm{\ge k+1}{p}$ with the vertex collector process {\whp} $\delta(\Gnmpp)\ge k$. \end{proof} \section*{Acknowledgements} I would like to thank Jerzy Jaworski for fruitful discussions and his help in improving the presentation of the article. I am also grateful to the reviewers for their thoroughness and their invaluable comments. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \bibliographystyle{plain} \bibliography{RIGCoupling2short} \end{document}