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
is equal
to 3. Denote by
the next to
largest eigenvalue of *A*. In the construction of highly connected sparse
graphs (``expanders''), it is desirable to have
as small as
possible. It is known that for any sequence of *X*_{N}'s

The question is whether, with probability 1, as . 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.