Eigenvalues of the adjacency matrix of a random cubic graph

Let XN be a random cubic graph on N vertices, i.e., 3 edges emanate from each vertex. Let A be the adjacency matrix for XN, i.e., avw = 1 if v is joined to w and 0 otherwise. A is symmetric and its eigenvalues all lie in [-3,3]. The largest eigenvalue $\lambda _0 (X)$ is equal to 3. Denote by $\lambda_1(X)$the next to largest eigenvalue of A. In the construction of highly connected sparse graphs (``expanders''), it is desirable to have $\lambda_1(X)$ as small as possible. It is known that for any sequence of XN's

\begin{displaymath}\liminf _{N\to \infty} \lambda_1(X_N) \ge 2\sqrt{2}
\end{displaymath}
 

The question is whether, with probability 1, $\lambda_1(X) \to 2\sqrt{2}$ as $N\to \infty$. If the answer to the above question is yes, then the random graph would be as good (for this purpose) as the arithmetically constructed Ramanujan graph.

 

PETER  RICHTER'S  INVESTIGATIONS

KEVIN  CHANG'S  INVESTIGATIONS