% 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<n$, so $2t<2n-2t$ and thus $d(v_{2r},v')\le\min\{2t,2n-2t\}.$ As $d(v_{2r},v')$ is even, one can connect vertices  $v_{2r}$ and $v'$ by a path 
			of length two using the argument 
			from Case 1.
			
			\smallskip
			
			{\it Case 3.}   $2n-2t<d(v,v')\leq 2t$ (which is possible only if $\beta>\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|-1<N/2$. 
		
		For deterministic $\wH $ we have
		\begin{equation}
		e_{\wH}(S,V_2\setminus T)+e_{\wH}(T,V_1\setminus S) = e_{\wH}(W,\overline{W})\ge c{n\choose t}|W| = c{n\choose t}(2|S|-1),
		\label{eq:PM1}
		\end{equation}
		while from the regularity of $\wH$ we get 
		\begin{equation}
		e_{\wH}(S,\overline{S})=e_{\wH}(S,V_2\setminus T)+e_{\wH}(S,T)={n\choose t}|S|,
		\label{eq:PM2}
		\end{equation}
		and
		\begin{equation}
		e_{\wH}(T,\overline{T})=e_{\wH}(T,V_1\setminus S)+e_{\wH}(T,S)={n\choose t}|T|={n\choose t}(|S|-1).
		\label{eq:PM3}
		\end{equation}
		Adding (\ref{eq:PM1}) and (\ref{eq:PM2}) and subtracting (\ref{eq:PM3}), we obtain that in $\wH $, 
		$$
		e_{\wH}(S,V_2\setminus T)\ge \frac{1}{2}{n\choose t}\left(|S|+2c|S|-c-|S|+1\right)\geq c'{n\choose t}|S|\,,
		$$ 
		for some constant $c'>0$.
		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}

