% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.6}{23(4)}{2016}
% 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}
\usepackage{tikz}
\usetikzlibrary{arrows}
% 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
% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\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}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
\newcommand{\cK}{\mathcal{K}}
\newcommand{\ccK}{\cK(n, \mathbf{P})}
\newcommand{\cH}{\mathcal{H}}
\newcommand{\wH}{H}
\newcommand{\Aut}{\textrm{Aut}}
\newcommand{\zzz}{\{0,1\}^n}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% if needed include a line break (\\) at an appropriate place in the title
\title{\bf On matchings in stochastic Kronecker 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{Justyna Banaszak\thanks{Partially supported by grant NCN Maestro 2012/06/A/ST1/00261.}\\
\small Faculty of Mathematics and Computer Science\\[-0.8ex]
\small Adam Mickiewicz University\\[-0.8ex]
\small Pozna\'{n}, Poland\\
\small\tt just.banaszak@gmail.com\\
%\and
%Forgotten Second Author \qquad Forgotten Third Author\\
%\small School of Hard Knocks\\[-0.8ex]
%\small University of Western Nowhere\\[-0.8ex]
%\small Nowhere, Australasiaopia\\
%\small\tt \{fsa,fta\}@uwn.edu.ao
}
% \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{Nov 5, 2015}{Sep 29, 2016}{Oct 14, 2016}\\
\small Mathematics Subject Classifications: 05C80; 05C70; 05C40}
\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}
The stochastic Kronecker graph is a random structure whose vertex set is a hypercube and the probability of an edge depends on the structure of its ends. We prove that when a.a.s.~the stochastic Kronecker graph becomes connected it a.a.s.~contains a perfect matching.
\end{abstract}
Let $n\in\mathbb{N}$, $N=2^n$, and let $0\le\alpha, \beta, \gamma \le 1$, where $\gamma\le\alpha$ be some constants. Denote by~$\mathbf{P}$ a symmetric matrix
$$
\mathbf{P}=\bordermatrix{&1&0\cr
1&\alpha & \beta\cr
0&\beta & \gamma},
$$
where 0's and 1's are labels of rows and columns of $\mathbf{P}$.
A stochastic Kronecker graph $\cK(n, \mathbf{P})$ is a random graph with vertex set $V=\zzz$, the set of all binary sequences of length $n$, where the probability that two vertices $u=(u_{1},\ldots,u_{n}), v=(v_{1},\ldots,v_{n})\in V$ are adjacent is given by
\begin{equation}
\nonumber
p_{u,v}=\prod\limits_{i=1}^n \mathbf{P}[u_{i},v_{i}].
\end{equation}
This model was introduced by Leskovec, Chakrabarti, Kleinberg and Faloutsos in \cite{Leskovec2005}. They showed empirically that the desired graph properties of real world networks hold in this model (see \cite{Leskovec2010}, \cite{Kolda}).
In \cite{MahdianXu} Mahdian and Xu showed that the threshold for connectivity of stochastic Kronecker graph is $\beta+\gamma=1$.
They also proved that if $\alpha, \beta, \gamma$ are such that $\cK(n, \mathbf{P})$ is asymptotically almost surely (a.a.s.)
connected,
and moreover $\gamma\leq\beta\leq\alpha$, then the graph has a.a.s.~a constant diameter.
Horn and Radcliffe~\cite{HornRadcliffe} studied the emergence of the giant component
and verified that a.a.s.~it appears in $\ccK$ as soon as $(\alpha+\beta)(\beta+\gamma)>1$. Kang, Karo\'nski, Koch and Makai~\cite{Karonski} showed that the degree distribution of $K(n,\mathbf{P})$ does not obey a
power-law and determined the threshold for the existence of some small subgraphs.
In this paper we denote by ${d}(v,u)$ the Hamming distance between two vertices $v$ and $u$ and by $w(v)$ the weight of a vertex $v=(v_{1},\ldots,v_{n})$ the number of 1's in its label
$$
w(v)=\sum\limits_{i=1}^nv_i.
$$
Note that the expected degree of a vertex $v$ with weight $w=w(v)$ is
\begin{equation}
\mathbb{E}(\textnormal{deg}(v))=\sum\limits_{i=0}^{w}{w\choose i}\alpha^i\beta^{w-i}\sum\limits_{j=0}^{n-w}{n-w \choose j}\gamma^j\beta^{n-w-j}
=(\alpha+\beta)^w(\beta+\gamma)^{n-w}.
\label{eq:degree}
\end{equation}
We start with stating the connectivity result. As we have already mentioned Mahdian and Xu \cite{MahdianXu} showed that if $\beta+\gamma>1$,
then a.a.s.~$\ccK$ is connected while for $\beta+\gamma<1$ a.a.s.~it contains
isolated vertices. Later their result was supplemented (in much larger generality by Radcliffe and Young \cite{YoungRadcliffe}). From their result we can derive the following observation concerning the connectivity of $\ccK$ at the threshold, i.e. when $\beta+\gamma=1$.
\begin{theorem}
$$
\lim_{n\to\infty}\mathbb{P}(\ccK \mbox{ is connected})=\left\{
\begin{array}{ll}
0&\mbox{if }\beta+\gamma=1,\: \beta\neq1\mbox{ or }\beta=1,\:\alpha=\gamma=0\\
1&\mbox{if }\beta=1,\;\alpha>0\mbox{ and }\gamma=0.
\end{array}
\right.
$$
\label{thm:con}
\end{theorem}
We shall show that the threshold for the emergence of a perfect matching in
$\ccK$ is basically the same as the connectivity threshold. Our main result
can be stated as follows.
\begin{theorem}
$$
\lim_{n\to\infty} \mathbb{P}(\ccK \mbox{ contains a perfect matching})=\left\{
\begin{array}{ll}
0&\mbox{if }\beta+\gamma\leq1\mbox{ and }\beta\neq1\\
1&\mbox{if }\beta+\gamma>1\mbox{ or }\beta=1.
\end{array}
\right.
$$
\label{thm}
\end{theorem}
\begin{proof}
Let $\beta+\gamma\le 1$ and $\beta\neq 1$. In the proof of Theorem \ref{thm:con}, Radcliffe and Young have
shown that a.a.s.~$\ccK$ contains an isolated vertex and so a.a.s.~
it does not contain a perfect matching.
Let $\beta=1$. Then every vertex $v=(v_1,\ldots,v_n)\in V(\ccK)$ is with probability $\beta^n=1$ connected to $\bar{v}=(1-v_1,\ldots,1-v_n)$. Thus, with probability 1, $\ccK$ contains a perfect matching.
Now let us consider the most interesting case, $\beta+\gamma>1$.
The main idea of our argument is the following. We shall choose a dense
bipartite subgraph
$\cH$ of $\ccK$ and show that it contains a perfect matching by verifying
Hall's condition.
To this end for a given odd number $t$ let $\wH=\wH(n,t) $ denote a graph with a vertex set $\zzz$, and edges between the pairs of vertices of Hamming distance $d(u,v)=t$.
Denote by $V_1$ and $V_2$ the subsets of vertices of $H$ of odd and even weights respectively. Since $t$ is odd, all the edges in $\wH$ must have one end in $V_1$ and the other in $V_2$,
i.e. $\wH$ is bipartite. Now let $\cH=\cH(t,n,\mathbf{P})$ be a subgraph of $\ccK$,
which contains only the edges between the vertices of Hamming distance $t$, i.e.
$\cH$ contains only those edges of $\ccK$ which belong to $\wH$. Clearly, $\cH$
is bipartite. We shall show that for
$$
t=2\left\lceil\frac{\beta}{2(\beta+\gamma)}n\right\rceil+1,
$$
which is basically the value of $t$ which maximizes the expected number of edges in $\cH$,
the random bipartite graph $\cH$ a.a.s.~fulfills Hall's condition, and so a.a.s.~it contains a perfect matching.
In order to do that we show first that the underlying bipartite graph $\wH$ has good expanding
properties. Let us first introduce some notation.
For two subsets $W$ and $U$ of the vertex set of $\wH $, let $e_{\wH}(W,U)$ denote the number of edges with one end in $W$ and another in $U$. Let $\overline{W}$ denote the complement of $W$ in the vertex set of $\wH $. By $\textnormal{Vol}(W)$
we denote the sum of vertex degrees of $W$.
Let us recall that a graph $G$ is edge-transitive, if for any two edges $e^1,e^2\in E(G)$ there exists a graph automorphism $F:V(G)\rightarrow V(G)$, which transforms $e^1$ into $e^2$.
The following result of Chung \cite{Chung} (Theorem 7.1) is crucial for our argument.
\begin{theorem}
Let $G$ be an edge-transitive graph with diameter $D$. Then for every $W\subseteq V(G)$, such that $\textnormal{Vol}(W)\leq \frac{\textnormal{Vol}(V(G))}{2}$,
$$
\frac{e_G(W,\overline{W})}{\textnormal{Vol}(W)}\geq\frac{1}{2D}.
$$
\label{lem:Chung}
\end{theorem}
In order to apply this result we need to check if $\wH $ is edge transitive and
has small diameter.
\begin{lemma}
$\wH\left(n,2\left\lceil\frac{\beta}{2(\beta+\gamma)}n\right\rceil+1\right) $ is edge-transitive and its diameter can be bounded from above by a constant $D$
which depends only on constants $\beta$ and $\gamma$
but not on $n$.
\label{lem:edgeTransitive}
\end{lemma}
\begin{proof}
Clearly, for $i\in [n]$ the function
$\tau_i:\zzz\to \zzz$ that maps $(v_1,\dots, v_i,\dots, v_n)$
to $(v_1,\dots, 1-v_i,\dots, v_n)$ is an automorphism of $\wH$. Also, for
any permutation $\sigma:[n]\to[n]$, the map $\Aut(\sigma):\zzz\to \zzz$
that maps the vertex $(v_1,\dots, v_i,\dots, v_n)$
to $(v_{\sigma(1)},\dots, v_{\sigma(i)},\dots, v_{\sigma(n)})$ is an automorphism of $\wH$.
We show that the group generated by all automorphisms of the above two kinds acts transitively
on edges of $\wH$.
Although it is a rather easy observation let us prove it more formally.
Let $e^{1}=\{u^{1},v^{1}\}$, $e^{2}=\{u^{2},v^{2}\}$
be two edges of $\wH $.
For $i\in\{1,2\}$, there exist precisely $t$ positions $j$ such that $u^i_{j}\neq v^i_j$. Let $I_{i}\subseteq [n]$ be the set of those positions (for $i\in\{1,2\}$). Let $\phi$ be a permutation of $[n]$ such that $\phi(I_{1})=I_{2}$ and $\phi^{\ast}=\Aut(\phi)$ be the
automorphism of $\wH$ induced by $\phi$. This automorphism is uniquely defined for fixed permutation $\phi$. Note that
the pairs $\{\phi^{\ast}(u^{1}),\phi^{\ast}(v^{1})\}$ and $\{u^2,v^2\}$ differ on the same positions, i.e. $\phi^{\ast}(u^1)_j\neq \phi^{\ast}(v^1)_j$ if and only if $u^2_j\neq v^2_j$. Define $\psi:\zzz\rightarrow \zzz$ by putting
$$
\psi(x)_j=\left\{
\begin{array}{ll}
x_j&\mbox{if }\phi^{\ast}(u^1)_j=u^2_j\\
1-x_j&\mbox{otherwise}.
\end{array}
\right.
$$
Clearly $\psi\left(\phi^{\ast}(u^1)\right)=u^2$. Moreover $\psi(x)_j=x_j$ iff $\phi^{\ast}(u^1)_j=u^2_j$ and it happens iff $\phi^{\ast}(v^1)_j=v^2_j$. Thus $\psi\left(\phi^{\ast}(v^1)\right)=v^2$ so $\psi\circ\phi^{\ast}$ is an automorphism of $\wH$ which maps $e^1$ into $e^2$. Hence $\wH $ is edge-transitive.
It remains to find an upper bound for the diameter of $\wH $.
Let $v$, $v'$ be two vertices of $\wH $ such that $d(v,v')$ is even.
We show that they are connected by a short path. We split our argument into several cases.
\medskip
{\it Case 1.} $d(v,v')\le\min\{2t,2n-2t\}$.
In this case there exists a vertex $v''$ which is adjacent to both $v$ and $ v'$.
Indeed, to find $v''$ it is enough to change $v$ on $d(v,v')/2$ positions on which $v$ and $v'$ differ and $t-d(v,v')/2$ positions on which they coincide.
\smallskip
{\it Case 2.} $d(v,v')>2t$ (which is possible only if $\gamma>\beta$).
\smallskip
For each pair of such vertices $v$ and $v'$ there exists a vertex $v''$ adjacent to $v$ such that $d(v'',v')=d(v,v')-t$.
To get $v''$ we only need to change $v$ on $t$ positions on which $v$ and $v'$ differ.
Applying this observation $2r$ times, where
$$2r\leq\left\lceil\frac{n-2t}{t}\right\rceil+1
=\left\lceil\frac{n}{t}-2\right\rceil+1
\leq\frac{n}{\frac{\beta}{\beta+\gamma}n}=\frac{\beta+\gamma}{\beta}$$
one can construct a path $vv_{1}\cdots v_{2r}$
in $\wH$ such that for every $1\leq i\leq 2r$, we have $d(v_{i},v')=d(v_{i-1},v')-t$ and $d(v_{2r},v')\le 2t$. Notice that in this case $2t\gamma$).
\smallskip
For each such $v$ and $v'$ there exist a path $vv_1v_2$ such that $d(v_2,v')=d(v,v')-2(n-t)$. To obtain $v_1$ from $v$, we need to change all $n-d(v,v')$ positions on which $v,v'$ do not differ and $t-n+d(v,v')$ among other positions. Then, $d(v,v_1)=n-d(v,v')+t-n+d(v,v')=t$. To obtain $v_2$ from $v_1$, we need to change all $n-d(v,v')$ positions on which $v,v'$ do not differ, all $n-t$ positions on which $v$ and $v_1$ are the same and $2t-2n+d(v,v')>0$ other positions. Then, indeed $d(v_1,v_2)=n-d(v,v')+n-t+2t-2n+d(v,v')=t$ and $d(v_2,v')=2t-2n+d(v,v')$.
Arguing in the same way we find a path $vv_1\cdots v_{2s}$ of length
$$2s\leq\left\lceil\frac{n-(2n-2t)}{n-t}\right\rceil+1
=\left\lceil\frac{n}{n-t}-2\right\rceil+1
\leq\frac{n}{\frac{\gamma}{\beta+\gamma}n-2}
\leq\frac{2(\beta+\gamma)}{\gamma}\,$$
such that for every $i\leq s$, $d(v_{2i},v')=d(v_{2i-2},v')-2(n-t)$ and $d(v_{2s},v')\leq 2n-2t$. Now, since $d(v_{2s},v')\le \min\{2t,2n-2t\},$ and $d(v_{2s},v')$ is even, we can apply Case 1 to connect $v_{2s}$ and $v'$ by a path of length two.
\medskip
Consequently, we have shown that the diameter $D$ of $\wH$ is bounded from above by
$$D\le 2\frac{\beta+\gamma}{\gamma}+3\qedhere$$
\end{proof}
As a direct consequence of Theorem \ref{lem:Chung} and Lemma \ref{lem:edgeTransitive}
we get the following result on expansion properties of $\wH$.
\begin{lemma}
Let $W$ be a subset of the vertex set of $\wH $ such that $$|W|\leq|V(\wH)|/2=2^{n-1}.$$
Then there exists a constant $c=c(\beta,\gamma)>0$ such that
$$
e_{\wH}(W,\overline{W})\ge c|W|{n\choose t}.
$$
\label{lem:pomocniczy}
\end{lemma}
\begin{proof}
Let $W$, $|W|\le 2^{n-1}$, be a set of vertices of $\wH$.
Since $\wH $ is an ${n\choose t}$-regular graph,
$$
\textnormal{Vol}(W)={n\choose t}|W|\leq{n\choose t}\frac{|V(H)|}{2}=\frac{\textnormal{Vol}(V(H))}{2}.
$$
Since $\wH $ is edge transitive, by Theorem \ref{lem:Chung} we get
$$
\frac{e_{\wH}(W,\overline{W})}{\textnormal{Vol}(W)}\geq\frac{1}{2D},
$$
where $D$ is the diameter of $\wH $. By Lemma \ref{lem:edgeTransitive}, $D$ is
bounded above by a constant, so for some positive constant $c$ we have
$$
e_{\wH}(W,\overline{W})\geq \frac{1}{2D} \textnormal{Vol}(W)\ge c|W|{n\choose t}\qedhere
$$
\end{proof}
Let us return to the random graph $\cH$. Recall that $\cH$ is a bipartite graph
with a bipartition $(V_1, V_2)$, where $|V_1|=|V_2|=2^{n-1}$. We will use the Hall's condition, which states that a bipartite graph $G(V,U)$, $|V|=|U|$ does not have a perfect matching iff there exists a set $R\subseteq V$ or $R\subseteq U$ such that
\begin{equation}
|N_{G}(R)|<|R|,
\label{Hall}
\end{equation}
where $N_{G}(R)$ is the set of all vertices adjacent in $G$ to the vertices from $R$. Suppose $G$ does not have a perfect matching. Let $S$ be the smallest set $S\subseteq V$ or $S\subseteq U$ which satisfies \eqref{Hall}. Without loss of generality, suppose $S\subseteq V$. Assume $|N_G(S)|<|S|-1$. Then we can delete any $|S|-|N_G(S)|-1$ vertices from $S$ to obtain a set smaller than $S$ which also satisfies \eqref{Hall}. Since $S$ is the smallest set satisfying \eqref{Hall} this situation is impossible, so $|N_G(S)|=|S|-1$. Moreover the set $S'=U\setminus N_G(S)$ does not have neighbours in $S$, i.e. $N_G(S')\subseteq V\setminus S$, so $|N_G(S')|\le |V|-|S|$, while $|S'|=|U|-|S|+1>|N_G(S')|$. Hence $|S'|$ also satisfies \eqref{Hall}. $|S'|+|S|=|U|+1$, so as $S$ is the smallest set which satisfies \eqref{Hall}, $|S|\le |U|/2$.
Therefore if $\cH$ does not have a perfect matching, there exists a set $S\subseteq V_1$ or $S\subseteq V_2$ such that $|N_{\cH}(S)|=|S|-1$ and $|S|\le|V_1|/2=2^{n-2}$.
Let $\mathcal{A}$ be the event that such a subset $S$ exists in $\cH$. Let $\mathcal{A}_1$ be the event that such a subset $S\subseteq V_1$ exists. Let $\mathcal{A}_2$ be the event that such a subset $S\subseteq V_2$ exists.
Then $\mathbb{P}(\mathcal{A}_1)=\mathbb{P}(\mathcal{A}_2)$, hence
$$
\mathbb{P}(\cH\mbox{ does not contain a perfect matching})=\mathbb{P}(\mathcal{A})\le 2\mathbb{P}(\mathcal{A}_1).
$$
For two fixed sets $S\subseteq V_1$, $|S|\le 2^{n-2}=N/4$ and $T\subseteq V_2$, $|T|=|S|-1$, let $\mathcal{A}_{S,T}$ denote the event that $T$ is the neighbourhood of $S$ in the random graph $\cH$.
In order to estimate the probability of $\mathcal{A}_{S,T}$ we
apply Lemma \ref{lem:pomocniczy} to the set $W=S\cup T$. Clearly $|W|=2|S|-10$.
Thus if $\mathcal{A}_{S,T}$ occurs, $c'{n\choose t}|S|$ fixed pairs of vertices which are adjacent in $\wH$ are not adjacent in $\cH$.
Observe that for each pair $u,v$ of vertices with Hamming distance $t$, the probability that there exists an edge $\{u,v\}$ is at least $\beta^t\gamma^{n-t}$.
Thus, the probability of $\mathcal{A}$ that Hall's condition fails
for some set $S$, $|S|\le 2^{n-2}=N/4$, is bounded from above by
\begin{equation*}
\begin{split}
\mathbb{P}(\mathcal{A})&
\le 2\sum\limits_{S\subseteq V_1\atop |S|\le N/4}\sum\limits_{T\subseteq V_2\atop |T|=|S|-1}\mathbb{P}(\mathcal{A}_{S,T})\\&
\le 2\sum\limits_{s=1}^{N/4}{N/2 \choose s}{N/2 \choose s-1}(1-\beta^t\gamma^{n-t})^{c's{n\choose t}}\\&
\le 2\sum\limits_{s=1}^{N/4}N^{2s}\exp\left(-c' s{n\choose t}\beta^t\gamma^{n-t}\right)\,.
\end{split}
\end{equation*}
Since
$$\sum_{i=0}^n \binom {n}{i} \beta^i\gamma^{n-i}=(\beta+\gamma)^n$$
and $t$ was chosen to correspond the largest term
in the sum,
so for $n$ large enough
$$ \binom {n}{t} \beta^t\gamma^{n-t}\ge(\beta+\gamma)^n/n\;.$$
Hence
\begin{equation*}
\begin{split}
\mathbb{P}(\mathcal{A})&
\leq
2\sum\limits_{s=1}^{N/4}\left(2^{2n}\exp\left(-c'(\beta+\gamma)^n/n\right)\right)^s
\end{split}
\end{equation*}
and since the term in brackets is exponentially small, it is maximal when $s=1$ that is
\begin{equation*}
\begin{split}
\mathbb{P}(\mathcal{A})&
\leq
2\sum\limits_{s=1}^{N/4}\left(2^{2n}\exp\left(-c'(\beta+\gamma)^n/n\right)\right)^s
\leq 2^n 2^{2n}\exp\left(-c'(\beta+\gamma)^n/n\right)
=o(1).
\end{split}
\end{equation*}
Consequently, a.a.s.~
$\cH$, and thus also $\ccK$, contains a perfect matching.
\end{proof}
In the proof we have found a perfect matching in a bipartite subgraph $\cH$ of $\ccK$,
containing only the edges joining vertices which are at Hamming distance
\begin{equation*}
t=2\left\lceil\frac{\beta}{2(\beta+\gamma)}n\right\rceil+1
\end{equation*}
in the hypercube.
Note however that if we take $k$ edge-disjoint subgraphs $\cH_\ell$, for $\ell\in\left[k\right]$,
containing the edges of $\ccK$ joining vertices at Hamming distance
\begin{equation*}
t=t(\ell)=2\left\lceil\frac{\beta}{2(\beta+\gamma)}n\right\rceil+2\ell+1.
\end{equation*}
respectively, we can mimic our argument to construct
$k$ edge-disjoint perfect matchings.
Thus, let $k$-PM denote the property, that a graph contains $k$ edge-disjoint perfect matchings.
\begin{theorem}
Let $k\in\mathbb{N}$, $k\geq 2$ be a constant.
$$
\lim_{n\to\infty}\mathbb{P}(\ccK \mbox{ has $k$-PM property})=\left\{
\begin{array}{lcl}
0&\mbox{if}&\beta+\gamma\leq1\\
1&\mbox{if}&\beta+\gamma>1.
\end{array}
\right.
$$
In particular
$$
\lim_{n\to\infty}\mathbb{P}(\ccK \mbox{ contains $k$-factor})=\left\{
\begin{array}{lcl}
0&\mbox{if}&\beta+\gamma\leq1\\
1&\mbox{if}&\beta+\gamma>1.
\end{array}
\right.
$$
\end{theorem}
Note the difference between the cases $k=1$ and $k\ge 2$ for $\beta=1$ and $\gamma=0$
when, as we have already observed,
a.a.s.~the minimum degree of $\ccK$ is one.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
I would like to thank Professor Tomasz \L{}uczak for stimulating discussion and valuable comments.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \bibliographystyle{plain}
% \bibliography{myBibFile}
% If you use BibTeX to create a bibliography
% then copy and paste the contents of your .bbl file into your .tex file
\begin{thebibliography}{99}
\bibitem{Chung} F.~Chung. \newblock {\em Spectral Graph Theory}. \newblock CBMS Conference on Recent Advances
in Spectral Graph Theory Vol. 92, AMS Publications, 1997.
\bibitem{MahdianXu} M.~Mahdian and Y.~Xu. \newblock Stochastic Kronecker Graphs. \newblock {\em Random Structures and Algorithms}, 38(4): 453--466, 2011.
\bibitem{Stanica} P.~Stanica. \newblock Good lower and upper bounds on binomial coefficients. \newblock {\em JIPAM. Journal of Inequalities in Pure and Applied Mathematics}, 2(3): 1--4, 2001.
\bibitem{Leskovec2005} D.~Chakrabarti, C.~Faloutsos, J.~Kleinberg and J.~Leskovec. \newblock Realistic, mathematically tractable graph generation and evolution, using Kronecker multiplication.
\newblock {\em Proceedings of the European Conference on Principles and Practice of Knowledge Discovery in Databases}: 133--145, 2005.
\bibitem{Leskovec2010} D.~Chakrabarti, C.~Faloutsos, Z.~Ghahramani, J.~Kleinberg and J.~Leskovec. \newblock Kronecker graphs: an approach to modeling networks. \newblock {\em Journal of Machine Learning Research},
11: 985--1042, 2010.
\bibitem{Kolda} T.~Kolda, A.~Pinar and C.~Seshadhri. \newblock An in-depth analysis of stochastic Kronecker graphs. \newblock {\em Journal of the ACM},
60(2): 1--32, 2013.
\bibitem{HornRadcliffe} P.~Horn and M.~Radcliffe. \newblock Giant components in Kronecker graphs. \newblock{\em Random Structures and Algorithms}, 40(3): 385--397, 2012.
\bibitem{Karonski} M.~Kang, M.~Karo\'nski, Ch.Koch and T.Makai. \newblock Properties of stochastic Kronecker graphs. \newblock{\em Journal of Combinatorics}, 4(6): 395--432, 2015.
\bibitem{YoungRadcliffe} M.~Radcliffe, S.~Young. \newblock Connectivity and giant components of Stochastic Kronecker Graphs. \newblock {\em Journal of Combinatorics}, 6(4): 457--482, 2015.
\end{thebibliography}
\end{document}