Eigenvalues of the adjacency matrix of a random cubic graph

Let X_N be a random cubic graph on N vertices, i.e., 3 edges emanate from each vertex. Let A be the adjacency matrix for X_N, i.e., a_vw = 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 X_N's

$$\liminf _{N\to \infty} \lambda_1(X_N) \ge 2\sqrt{2}$$

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.

Proposed by: Peter Sarnak.
Assigned to: