\section{Random $d$-Regular Graphs}
  \label{sec:random_d_regular}
  We now consider random $d$-regular graphs, defined as follows, and characterize the smallest eigenvalue of the grounded Laplacian for such graphs.

\begin{definition}
For any $n \in \mathbb{N}$, let $d \in \mathbb{N}$ be such that $3\leq d<n$ and $dn$ is an even number. Define $\Omega_{n,d}$ to be the set of all $d$-regular graphs on $n$ nodes. Define the probability space $(\Omega_{n,d}, \mathcal{F}_{n,d}, \mathbb{P}_{n,d})$, where the $\sigma$-algebra $\mathcal{F}_{n,d}$ is the power set of $\Omega_{n,d}$, and $\mathbb{P}_{n,d}$ is a probability measure assigning equal probability to every element of $\Omega_{n,d}$.  An element of $\Omega_{n,d}$ drawn according to $\mathbb{P}_{n,d}$ is called a random $d$-regular graph, and denoted by $\mathcal{G}_{n,d}$ \cite{Bollobas}.
\end{definition}
  
Let $\lambda'_1(A)\leq \lambda'_2(A)\leq ... \leq \lambda'_n(A)$ be the eigenvalues of the adjacency matrix of any given graph $\mathcal{G}$; note that $\lambda'_n(A)=d$ for $d$-regular graphs. Define $\lambda'(\mathcal{G})=\max \{|\lambda'_1(A)|,|\lambda'_{n-1}(A)|\}$.  It was shown in \cite{Friedman} that for any $\epsilon > 0$, 
\begin{equation}
  \lambda'(\mathcal{G}_{n,d})\leq 2\sqrt{d-1}+\epsilon
  \label{eqn:raman}
  \end{equation}
asymptotically almost surely.  As the Laplacian for the graph is given by $L = D - A = dI - A$, for any $\epsilon > 0$, the algebraic connectivity of a random $d$-regular graph satisfies
\begin{equation*}
\lambda_2(L) \geq d-2\sqrt{d-1}-\epsilon,
\end{equation*}
asymptotically almost surely.  
On the other hand we know that $\lambda_2(\bar{L})\geq \lambda_2(L)-|S|$ \cite{Fiedler}. Thus for a random $d$-regular graph with a single grounded node, we have
  \begin{equation*}
    \frac{2\sqrt{|S||\partial S|}}{\lambda_2(\bar{L})} =\frac{2\sqrt{d}}{\lambda_2(\bar{L})}\leq  \frac{2\sqrt{d}}{d-2\sqrt{d-1}-\epsilon-1}< 1
  \end{equation*}
  asymptotically almost surely for sufficiently large $d$ and sufficiently small $\epsilon$.   Lemma~\ref{lem:mainlem} and Theorem~\ref{thm:main} then yield the following result.
  
\begin{theorem}
Let $\mathcal{G}$ be a random $d$-regular graph on $n$ vertices with a single grounded node.  Then for sufficiently large $d$, the smallest eigenvalue of the grounded Laplacian satisfies $\lambda = \Theta\left(\frac{d}{n}\right)$ asymptotically almost surely.
\end{theorem}
{"config": "arxiv", "file": "1406.2271/Ramanujan.tex"}