\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{The edge theorem}

\begin{theorem}
\label{edges}
Fix $p\in (0,1)$,
$\rho(t)=\lfloor \alpha t^s \rfloor$ with $\alpha$ and $s$ real
numbers with $\alpha >0 $ and $s\in [0,1]$, and $H$ a finite
graph. Let $e_t$ be the expected number of edges in $G_t$. Then, if
$s<1$,
\[
e_t=\left\{
\begin{array}{ll}
\theta(t^{s+1})&\mbox{if $s+1>2p$},\\
\theta(t^{2p}\log t)&\mbox{if $s+1=2p$},\\
\theta(t^{2p})&\mbox{if $s+1<2p$}
\end{array}\right..
\]
and when $s=1$, then $e_t\in\theta(t^2)$, and more precisely,
\[
e_t=
\frac{\alpha}{1-p(1-\alpha)}{t\choose 2}(1+o(1)).
\]
\end{theorem}

\begin{proof}
We will derive our results from a recurrence relation for $e_t$.
Let $\epsilon_t=|\mathbb{E}(G_t)|$. Then
$\epsilon_t=\epsilon_{t-1}+\rho(t)+n_t$, where $n_t$ equals the number
of neighbours $w$ of the copying node $u$ so that the link $uw$ is
copied into a link $v_tw$ in step $t$, but $w$ does {\em not}
receive a random link from $v_t$. 

{\tt jj: I considered your suggestion that the graph should not be made
  simple, since this makes the calculations easier. However, in this
  case the copying step should be adjusted so that for every EDGE
  incident with the copy node, the destination is copied with
  probability p. But this makes the calculations in the rest of the
  paper not completely correct, since a neighbour of the copy node
  that is connected by a multiple edge has a larger chance of
  becoming a neighbour of $v_t$. Simple graphs still may be simplest..}

The probability that this happens
for a particular neighbour $w$ equals $p(1-q_\rho(1,t))$, so 
\[
\mathbb{E}(n_t\,|\, G_{t-1})=deg_{G_{t-1}}(u)(1-q_\rho(t))p.
\]

Since the copying node $u$ is chosen u.a.r., the expected degree of
$u$ equals the average degree of $G_{t-1}$, which equals
$2\epsilon_{t-1}/t$. Therefore,
\[
\mathbb{E}(n_t|G_{t-1})=2\epsilon_{t-1}p(1-q_\rho(t))/t.
\]
Taking the expected value of the above gives
the following recursion for $e_t$:
\begin{eqnarray}
\label{recursion}
e_{t}&=&e_{t-1}+\lfloor \alpha
t^s\rfloor+2e_{t-1}p(1-q_{\rho}(t)/t\nonumber 
\end{eqnarray}


Therefore, using bound (\ref{bound-q}) on $q_\rho$,
\begin{equation}
\label{lbound}
e_{t}\leq 
e_{t-1}(1+\frac{2p}{t}(1-\alpha t^{-(1-s)}+t^{-1})+\alpha t^s.
\end{equation}

and
\begin{equation}
\label{ubound}
e_{t}\geq 
e_{t-1}(1+\frac{2p}{t}(1-\alpha t^{-(1-s)})+\alpha t^s-1.
\end{equation}

In this proof, we will repeatedly use the result that for all
$\gamma>1$, and for all $t>0$, the following inequalities hold. The
inequalities can be easily obtained by considering the area under the
curve of the function $f(t)=t^\gamma$ between $t$ and $t+1$.
\begin{equation}
\label{power}
\gamma t^{\gamma-1}\leq (t+1)^\gamma-t^\gamma\leq \gamma(t+1)^{\gamma -1}.
\end{equation}

We will prove the results by induction on $t$. 

\subsection{$s<1$, $2p<s+1$}

Choose $t_0$ sufficiently large so that 
\[
\alpha t_0^{s}\geq 1.
\] 
and let $c$  be a
constant so that $e_t\leq c t^{1+s}$ for $t=t_0$, and 
\[ 2pc+\alpha\leq c(s+1).\]
(Note that such a choice of $c$ exists since $2p<s+1$.) 

Fix $t>t_0$, and suppose that the bound holds for all values less than $t$
and at least $t_0$. 
Using the lower bound on the recursion from (\ref{lbound}),
\begin{eqnarray*}
e_t&\leq& e_{t-1}(1+\frac{2p}{t}(1-\alpha t^{-(1-s)}+t^{-1})+\alpha
t^s\\
&\leq& e_{t-1}(1+\frac{2p}{t})+\alpha t^s\\
&\leq& (1+\frac{2p}{t})ct^{1+s}+\alpha t^s\\
&=& ct^{1+s}+(2pc+\alpha)t^s\\
&\leq& c(t^{1+s}+(s+1)t^s)\\
&\leq& c(t+1)^{s+1}.
\end{eqnarray*}
The second inequality follows from the choice of $t_0$, the third from
the induction hypothesis, the fourth from the choice of $c$, and the
last inequality from (\ref{power}). This shows that $e_t\in
O(t^{s+1})$. 

Next, consider the induction statement $e_t\geq c_1t^{s+1}-c_2t^a$,
where $a$ is such that $s+1>a>\max\{ 1,2p\}$. Let
$c_1$, $c_2$ and $t_0$ be positive constants, chosen so that 
\[
(2pc_1+\alpha)(\frac{t_0}{t_0+1})^s\geq c_1(s+1),
\]
and
\[
2p\alpha c_1+1+2pc_2\leq ac_2, 
\]
and \[\frac{2p}{t_0}\leq 1,\] 
and so that the statement holds for $t=t_0$. Fix
$t>t_0$, and suppose
the statement holds for all values less than $t$ and at least $t_0$. 

Using ({\ref{ubound}), we obtain:
\begin{eqnarray*}
e_t&\geq& e_{t-1}(1+\frac{2p}{t}(1-\alpha t^{-(1-s)})+\alpha
t^s-1\\
&\geq& (c_1t^{1+s}-c_2t^a)(1+\frac{2p}{t}(1-\alpha t^{-(1-s)})+\alpha t^s-1\\
&=& c_1t^{1+s}+(2pc_1+\alpha)(\frac{t}{t+1})^s (t+1)^s-(\alpha
c_1\frac{2p}{t}+1)-c_2t^a-(2pc_2)t^{a-1}+2p\alpha c_2t^{a-2+s}\\
&\geq & c_1 (t^{1+s}+(s+1)(t+1)^s)-(c_2t^a+(2p\alpha
c_1+1+2pc_2)t^{a-1})\\
&\geq & c_1 (t^{1+s}+(s+1)(t+1)^s)-c_2(t^a+at^{a-1})\\
&\geq& c_1(t+1)^{s+1}-c_2(t+1)^a.
\end{eqnarray*}
This proves that $e_t\in\theta(t^{s+1})$.

\subsection{$s<1$, $2p=s+1$}

fix $t>t_0$, and suppose that $e_t\leq ct^{2p}\ln(t)$ 
for all values less than $t$
and at least $t_0$. Constant $c$ is chosen so that the inequality
holds for $t=t_0$, and so that $c\geq \alpha$. Note that the condition
on $p$ and $s$ implies that $p>1/2$.

By (\ref{recursion}),
\begin{eqnarray*}
e_t&\leq& e_{t-1}(1+\frac{2p}{t})+\alpha t^s\\
&\leq& (1+\frac{2p}{t})ct^{2p}\ln(t)+\alpha t^{2p-1}\\
&\leq& c(t+1)^{2p}\ln(t)+\alpha (t+1)^{2p-1}\\
&\leq & c(t+1)^{2p}(\ln(t)+\frac{\alpha/c}{t+1})\\
&\leq & c(t+1)^{2p}\ln(t+1).
\end{eqnarray*}

Next, consider the induction statement $e_t\geq c_1t^{2p}\ln{t}-c_2t^{2p})$.
Let $c_1$, $c_2$ and $t_0$ be positive constants, chosen so that 
\[
\frac{\alpha}{3} t^{2p-1}\geq 1+2p\alpha c_1t^{4p-3}\ln{t}\mbox{ for
all $t\geq t_0$},
\]
and
\[
(2p+\frac{\alpha}{3c_1\ln{t}})t^{2p-1}\geq 2p(t+1)^{2p-1}\mbox{ for
all $t\geq t_0$},
\]
and so that the statement holds for $t=t_0$. (Note that values
satisfying the first condition
can be found because $2p-1>4p-3$, and values satisfying the second
inequality can be found because there $t$ can always be chosen large
so that
$(\frac{t+1}{t})^{2p-1}=(1+\frac{1}{t})^{2p-1}\leq 1+\frac{a}{\ln{t}$,
  for any positive constant $c$.

Fix
$t>t_0$, and suppose
the statement holds for all values less than $t$ and at least $t_0$. 

Using ({\ref{ubound}), we obtain:
\begin{eqnarray*}
e_t&\geq& e_{t-1}(1+\frac{2p}{t}(1-\alpha t^{2p-2)})+\alpha
t^{2p-1}-1\\
&\geq& (c_1t^{2p}\ln{t}-c_2t^{2p})(1+\frac{2p}{t}(1-\alpha
t^{2p-2})+\alpha t^{2p-1}-1\\ 
&=& c_1t^{2p}\ln{t}+2pc_1 t^{2p-1}\ln{t}-2p\alpha
c_1t^{4p-3}\ln{t}-(c_2t^{2p}+2pt^{2p-1})+2p\alpha c_2 t^{4p-3}+\alpha
t^{2p-1}-1\\ 
&\geq & c_1 (t^{2p}+(2p+
+\frac{\alpha}{3c_1\ln{t}})t^{2p-1})\ln{t}-(c_2t^{2p}+(2pt^{2p-1})+
(\frac{\alpha}{3}t^{2p-1}-1-2p\alpha c_1 t^{4p-3})+\frac{\alpha}{3}t^{2p-1}\\ 
&\geq & c_1 (t^{2p}+2p(t+1)^{2p-1})\ln{t}-c_2 (t+1)^{2p}  
+\frac{\alpha}{3}t^{2p-1}\\ 
&\geq & c_1 (t+1)^{2p}\ln{t}-c_2 (t+1)^{2p}+\frac{\alpha}{3}t^{2p-1}\\   
...
\end{eqnarray*}
This proves that $e_t\in\theta(t^{2p}\ln(t))$.

\subsection{$s<1$, $2p<s+1$}

For an upper bound, the induction hypothesis is that  
$e_t\leq c_1t^{s+1}+c_2 t^{a}$, where $a$ is such that
$s+1>a>\max{2p,1}$. 
Fix $t_0$, and let $c_1$ and $c_2$ be
such that the bound holds for $t=t+0$, and 
\[
2p+\alpha/c_1\leq s+1.
\] 
By (\ref{recursion}),
\begin{eqnarray*}
e_t&\leq & e_{t-1}(1+\frac{2p}{t})+\alpha t^s\\
&\leq& c_1(t^{s+1}+(2p+\alpha/c_1)t^{s})+c_2(t^a+2pt^{a-1})\\
&\leq& c_1(t^{s+1}+(s+1)t^{s})+c_2(t^a+at^{a-1})\\
&\leq &c_1(t+1)^{s+1}+c_2(t+1)^{a}.
\end{eqnarray*}

Consider next the induction statement $e_t\geq c_1t^{s+1}-c_2t^a$,
where $a=\max\{ 1,s+2p-2\}$, and
$c_1$, $c_2$ and $t_0$ are positive constants, chosen so that 
\[
(2pc_1+\alpha)(\frac{t_0}{t_0+1})^{2p-1}\geq 2pc_1,
\]
and
\[
2p\alpha c_1+1+2pc_2\leq ac_2, 
\]
and so that the statement holds for $t=t_0$. Fix
$t>t_0$, and suppose
the statement holds for all values less than $t$ and at least $t_0$. 


\begin{eqnarray*}
e_t&\geq& e_{t-1}(1+\frac{2p}{t}(1-\alpha t^{-(1-s)})+\alpha
t^s-1\\
&\geq& (c_1t^{2p}-c_2t^a)(1+\frac{2p}{t}(1-\alpha t^{-(1-s)})+\alpha t^s -1\\
&=& c_1t^{2p}+2pc_1t^{2p-1}+\alpha t^s -  2pc_1\alpha t^{s+2p-2}
-c_2t^a-2pc_2t^a+2p\alpha c_2 t^{a+s-2}-1\\ 
&\geq & c_1t^{2p}+ (2pc_1+\alpha)t^{2p-1}-(c_2t^a+(2pc_1\alpha+2pc_2+1)t^{a-1}\\
&= & c_1t^{2p}+ (2pc_1+\alpha)(\frac{t}{t+1})^{2p-1}(t+1)^{2p-1}-(c_2t^a+(2pc_1\alpha+2pc_2+1)t^{a-1}\\
&\geq& c_1(t^{2p}+2p(t+1)^{2p-1})-c_2(t^a+at^{a-1})\\
&\geq& c_1(t+1)^{2p}-c_2 (t+1)^a.
\end{eqnarray*}

\subsection{$s=1$}

Note that, in this case, $\alpha$ must be
smaller than 1. Let 
\[
c_{\alpha,p}=\frac{\alpha}{1-p(1-\alpha)}.
\]
Note that $\alpha +p(1-\alpha)\leq 1$, so $c_{\alpha,p}\leq 1$ for all
choices of $p$ and $\alpha$.
In this case, we have the recurrence relation:
\begin{eqnarray}
\label{recursion2}
e_{t}&\leq & e_{t-1}(1+\frac{2p}{t}(1-\alpha))+\alpha t.
\end{eqnarray}


We prove first that $e_t\leq c_{\alpha,p}t^{2}+c_2t^a$, where $2>a>
\max\{1,2p(1-\alpha)\}$. Fix $t_0$, and
choose $c_2$ so that the inequality holds for $t=t_0$. By (\ref{recursion2}),
\begin{eqnarray*}
e_t&\leq & e_{t-1}(1+\frac{2p(1-\alpha)}{t})+\alpha t\\
&\leq& (1+\frac{2p(1-\alpha)}{t})(c_{\alpha,p}t^{2}+c_2t^a)+\alpha t\\
&\leq& c_{\alpha,p}(t^{2}+(2p(1-\alpha)+\alpha)t)+c_2(t^a+2p(1-\alpha)t^{a-1})\\
&\leq& c_{\alpha,p}(t^{2}+2t)+c_2(t^a+at^{a-1})\\
&\leq& c_{\alpha,p}(t+1)^{2}+c_2(t+1)^a\\
\end{eqnarray*}

{\tt lower bound missing}

\end{proof}

\end{document}