\documentclass[12pt]{amsart}
\usepackage{amssymb,amsfonts,latexsym,amstext,epsfig}

\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{lemma}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}
\newtheorem{remark}{Remark}

\newcommand{\Nnn}{{\mathbb N}}

\begin{document}

\section{Isomorphism classes}

{\tt (intro needed)}

\begin{theorem}
Fix $p\in (0,1)$, $H$, and $\rho=\lfloor \alpha t^s\rfloor$, where
$\alpha>0$ and $s\in [0,1)$. Let $G=\lim_{t\rightarrow\infty} G_t$
be generated according to the model $G(p,\rho,H)$. Then, with
probability 1,
\[
\omega(G)\geq \lfloor\frac{2}{1-s}\rfloor+1.
\]
Moreover,$G$ contains infinitely many cliques of size $k_{H,s}$, where
$k_{H,s}=\max\{\lfloor\frac{2}{1-s}\rfloor+1,\omega(H)\}$, but only
finitely many cliques of size $k$ for any $k>k_{H,s}$.
\label{clique}
\end{theorem}

\begin{corollary}
For any $p\in (0,1)$, and $\rho=\lfloor \alpha t^s\rfloor$, where
$\alpha>0$ and $s\in [0,1)$, there are infinitely many infinite graphs
that can occur with positive probability as a limit of graphs
generated according to model $G(p,\rho,H)$.
\end{corollary}

The proof of Theorem \ref{clique} uses the following lemma.

\begin{lemma}
Fix $p\in (0,1)$, $H$, and $\rho=\lfloor \alpha t^s\rfloor$, where
$\alpha>0$ and $s\in [0,1)$. Let $(G_t:t\in\Nnn )$
be a sequence of graphs
generated according to the model $G(p,\rho,H)$, and $\omega(H)=1$. 
Let $C(k,t)$ be the
expected number of cliques in $G_t$, and let
$k_0=\lfloor\frac{2}{1-s}\rfloor +1$. 
Then for all $k\leq k_0$,
\[
C(k,t)\in O(t^{k-{k\choose 2}(1-s)}).
\]
Moreover, when $k> k_0$, $C(k,t)\in O(1)$.
\label{cliquelemma}
\end{lemma}

\begin{proof}
Let $p,\rho,H$ be as in the statement of the theorem, and let
$G_t$ be a sequence of graphs generated according to model
$G(p,\rho,H)$. 

Let $C(k,t)$ denote the expected number of cliques in $G_t$. Then,
using Lemma \ref{claim}, we obtain the following recursive bound for
all $k\geq 1$:
\begin{eqnarray}
\label{cliquerecursion}
C(k+1,t+1)&=&C(k+1,t)+ \sum_{S\in \mathcal{C}_{k,t}} p_{S,t}\nonumber\\
&\leq& C(k+1,t) + c_2^{k}(t-1)^{(s-1)(k)}C(k,t)\\
\end{eqnarray}

The proof of the lemma follows by induction on $k$.
The number of cliques of size 1 equals the number of nodes, so 
\[
C(1,t)=|V(t)|=t+|V(H)|\in O(t).
\]

Assume then that $C(k,t)\in O(t^{k-{k\choose 2}(1-s)})$, and
$k<k_0$. 
Choose
positive time $t_0$ and constant 
$c'$ so that
$C(k,t)\leq c't^{k-{k\choose 2}(1-s)}$ for all $t\geq t_0$. 
Choose $c$ so that 
\[
c\geq \frac{c'c_2^k}{k+1-{k+1\choose 2}(1-s)},
\]
and
$C(k+1,t_0)\leq ct_0^{k+1-{{k+1}\choose 2}(1-s)}$.
Fix $t>t_0$, and assume the bound holds for $t$.
By the recursion \ref{cliquerecursion},
\begin{eqnarray*}
C(k+1,t+1)
&\leq& C(k+1,t) + c_2^{k}(t-1)^{(s-1)(k)}C(k,t)\\
&\leq& ct^{k+1-{{k+1}\choose 2}(1-s)} + 
c(k+1-{k+1\choose 2}(1-s)) t^{(s-1)k} t^{k-{k\choose 2}(1-s)}\\
&=& ct^{k+1-{k+1\choose 2}(1-s)}(1+\frac{k+1-{k+1\choose 2}(1-s)}{t})\\
&\leq & c(t+1)^{k+1+{k+1\choose 2}(1-s)}.
\end{eqnarray*}
 
Note that $k_0$ is chosen so that $k-{k\choose 2}(1-s)$ is negative
  precisely when $k>k_0$.
Using the same recursion for $k=k_0+1$ as used above, and the bound
  for $C(k_0,t)$ as stated in the lemma, we obtain the following:
\begin{eqnarray*}
C(k,t+1)
&\leq& C(k,t) + c_2^{k}(t-1)^{-(1-s)(k-1)}C(k-1,t)\\
&\leq& C(k,t) + 
c_2^{k} t^{-(k-1)(1-s)+k-1-{k-1\choose 2}(1-s)}\\
&=& C(k,t) + 
c_2^{k} t^{-1+k-{k\choose 2}(1-s)}\\
&=& C(k,t)+ct^{-1-\epsilon},
\end{eqnarray*}
where $c>0$ and $\epsilon>0$ are constants. Hence 
\[
C(k,t)\leq c\sum_{\tau=1}^t \tau^{-1-\epsilon},
\]
which is bounded by a constant.

This implies that $C(k,t)$ is constant for $k=k_0+1$, and hence for
all $k>k_0$.

\end{proof}

\begin{lemma}
\label{omega(H)}
The limit contains infinitely many cliques of size $\omega(H)$
\end{lemma}

\begin{proof}
Let $c=\omega(H)$, and let $C$ be a maximum clique in $H$. For each
$t>t_0$, let $A_t$ be the event that $v_t$ creates a new clique of
size $c$ in $G_t$. Then 
\[
Pr(A_t)\geq c/tp^{c-1},
\]
since a new clique is created if a node from $C$ is chosen as the copy
node, and all its neighbours in $C$ are copied. 

Hence the expected number of cliques of size $c$ in $G_t$ is at least
\[
cp^{c-1}\sum_{\tau=1}^t \frac{1}{\tau}.
\]
This sum goes to infinity as $t\rightarrow \infty$, so the result
follows.
\end{proof}

\begin{proof}[Proof of Theorem \ref{clique}]
%Let $c=\omega(G)$, and let $t_0$ be smallest so
%that $\omega(G_{t_0})=c$. If $c\leq\lfloor\frac{1}{1-s}\rfloor$,
%then by Lemma \ref{claim}, with probability 1 there exists a node
%$v_t$ ($t>t_0$) which extends the clique of size $c$ in $G_{t_0}$,
%contradicting the assumption. Hence $\omega (G)\geq
%\lfloor\frac{1}{1-s}\rfloor +1$.
\end{proof}

\end{document}