\section{Analysis of Erdos-Renyi Random Graphs}

\begin{definition}
An Erdos-Renyi (ER) random graph, denoted $\mathcal{G}(n,p)$, is a graph on $n$ nodes where each possible edge between two distinct vertices is present independently with probability $p$ (which could be a function of $n$).  Equivalently, an ER random graph can be viewed as a probability space $(\Omega_n, \mathcal{F}_n, \mathbb{P}_n)$, where the sample space $\Omega_n$ consists of all possible graphs on $n$ nodes, the $\sigma$-algebra $\mathcal{F}_n$ is the power set of $\Omega_n$, and the probability measure $\mathbb{P}_n$ assigns a probability of $p^{|\mathcal{E}|}(1-p)^{\binom{n}{2}-|\mathcal{E}|}$ to each graph with $|\mathcal{E}|$ edges. 
\end{definition}

\begin{definition}
For an ER random graph, we say that a property holds {\it asymptotically almost surely} if the probability  of the set of graphs with that property (over the probability space $(\Omega_n, \mathcal{F}_n, \mathbb{P}_n)$) goes to $1$ as $n \rightarrow \infty$.  For a given graph function $f: \Omega_n \rightarrow \mathbb{R}_{\ge 0}$ and another function $g: \mathbb{N} \rightarrow \mathbb{R}_{\ge 0}$, we say $f(\mathcal{G}(n,p)) \le (1+o(1))g(n)$ asymptotically almost surely if there exists some function $h(n) \in o(1)$ such that $f(\mathcal{G}(n,p)) \le (1+h(n))g(n)$ with probability tending to $1$ as $n \rightarrow \infty$.  
\end{definition}

We start by showing the following bounds on the degrees and isoperimetric constants of such graphs; while there exist bounds on these quantities for specific forms of $p$ (e.g., \cite{Perez,Benjamini,Ganesh,Cooper2007cover}), they do not cover the full range of probability functions considered by the following lemma.   The proof of this result is provided in the Appendix.  


\begin{lemma}
Consider the Erdos-Renyi random graph $\mathcal{G}(n,p)$, where the edge probability $p$ satisfies 
$\limsup_{n \rightarrow \infty} \frac{\ln{n}}{np} < 1$.  Fix any $\epsilon \in (0, \frac{1}{2}]$.  There exists a positive constant $\alpha$ (that depends on $p$) such that the minimum degree $d_{min}$, maximum degree $d_{max}$ and isoperimetric constant $i(\mathcal{G})$ satisfy
$$
\alpha{np} \le i(\mathcal{G}) \le d_{min} \le d_{max} \le {np}\left(1 + \sqrt{3}\left(\frac{\ln n}{np}\right)^{\frac{1}{2}-\epsilon}\right).
$$
asymptotically almost surely.
\label{lem:degree_iso_bounds}
\end{lemma}


\begin{remark}
Note that the probability functions captured by the above lemma include the special cases where $p$ is a constant and where $p(n) = \frac{c\ln{n}}{n}$ for constant $c > 1$.  The above results generalize the bounds on the degrees and the isoperimetric constant in \cite{Perez,Benjamini,Cooper2007cover} where probability functions of the form $\frac{c\ln{n}}{n}$ were studied, although the bounding constants provided in those works will be generally tighter than the ones provided above due to the special case analysis. Further note that when $\ln{n} = o(np)$, the upper bound on the maximum degree becomes $np(1+o(1))$.
\end{remark}

Lemma~\ref{lem:degree_iso_bounds} and the lower bound \eqref{eqn:lower_bound_lambda_2_iso} immediately lead to the following corollary.

\begin{corollary}
Consider the Erdos-Renyi random graph $\mathcal{G}(n,p)$, where the edge probability $p$ satisfies
$\limsup_{n \rightarrow \infty} \frac{\ln{n}}{np} < 1$.  Then there exists a positive constant $\gamma$ (that depends on $p$) such that the algebraic connectivity $\lambda_2(\mathcal{G})$ satisfies $\lambda_2(L) \ge \gamma{np}$ asymptotically almost surely.
\label{cor:algebraic_connectivity_bound}
\end{corollary}


With the above results in hand, we are now in place to prove the following fact about the smallest eigenvalue of the grounded Laplacian matrix for Erdos-Renyi random graphs.  We omit the dependence of $S$ and $\lambda$ on $n$ for notational convenience.

\begin{theorem}
Consider the Erdos-Renyi random graph $\mathcal{G}(n,p)$, where the edge probability $p$ satisfies
$\limsup_{n \rightarrow \infty} \frac{\ln{n}}{np} < 1$.  Let $S$ be a set of grounded nodes chosen uniformly at random with $|S| = o(\sqrt{np})$.  Then the smallest eigenvalue $\lambda$ of the grounded Laplacian satisfies
$$
(1-o(1))|S|p \le \lambda \le (1+o(1))|S|p
$$
asymptotically almost surely.
\label{thm:erdos1}
\end{theorem}

\begin{IEEEproof}
For probability functions satisfying the conditions in the theorem, Lemma~\ref{lem:degree_iso_bounds} indicates for any set $S$ of grounded nodes,  $|\partial S| \le |S|d_{max} \le \beta|S|np$ asymptotically almost surely for some positive constant $\beta$.  Let $\bar{L}$ be the Laplacian matrix for the graph induced by the non-grounded nodes (i.e., the graph obtained by removing all grounded nodes and their incident edges).  From \cite{Fiedler}, we have $\lambda_2(\bar{L}) \ge \lambda_2(L) - |S|$.  Combining this with Corollary~\ref{cor:algebraic_connectivity_bound}, we obtain
$$
\frac{\sqrt{|S||\partial S|}}{\lambda_2(\bar{L})} \le \frac{|S|\sqrt{\beta{np}}}{\gamma{np} - |S|} = o(1)
$$
asymptotically almost surely when $|S| = o(\sqrt{np})$.  From Lemma~\ref{lem:mainlem} and Theorem~\ref{thm:main}, we have $(1-o(1))\frac{|\partial S|}{n-|S|} \le \lambda \le \frac{|\partial S|}{n-|S|}$ asymptotically almost surely.

Next, consider the random variable $|\partial S|$; there are $|S|(n-|S|)$ possible edges between $S$ and $\mathcal{V}\setminus S$, each appearing independently with probability $p$, and thus $|\partial S|$ is a Binomial random variable with $|S|(n-|S|)$ trials.  For all $0<\alpha<1$ we have the concentration inequalities \cite{Mitzenmacher}
\begin{equation}
\begin{split}
\mathbf{Pr}(|\partial S| &\geq (1+\alpha)\mathbb{E}[|\partial S|])\leq e^{\frac{-\mathbb{E}[|\partial S|] \alpha^2}{3}}\\
\mathbf{Pr}(|\partial S| &\leq (1-\alpha)\mathbb{E}[|\partial S|])\leq e^{\frac{-\mathbb{E}[|\partial S|] \alpha^2}{2}}.
\end{split}
\label{eqn:2ineq}
\end{equation}
We know that $\mathbb{E}[|\partial S|]= |S|(n-|S|)p$. Consider $\alpha=\frac{1}{\sqrt[4]{\ln{n}}}$ which causes the upper bound in the first expression to become $\exp(-\frac{|S|(n-|S|)p}{3\sqrt{\ln{n}}})$.  Since $|S|(n-|S|)$ is lower bounded by $n-1$ and $np > \ln{n}$ for sufficiently large $n$, the bounds in \eqref{eqn:2ineq} asymptotically go to zero. Thus,
\begin{equation*}
(1 - o(1))|S|(n-|S|)p \le |\partial S| \le (1 + o(1))|S|(n-|S|)p,
\end{equation*}
asymptotically almost surely. Substituting into  the bounds for $\lambda$, we obtain the desired result.
\end{IEEEproof}
{"config": "arxiv", "file": "1406.2271/erdos_renyi.tex"}