For a graph $G$, let its Laplacian be $\Delta = I – D^{-1/2}AD^{-1/2}$, where $A$ is the adjacency matrix, $I$ is the identity matrix and $D$ is the diagonal matrix with vertex degrees. I'm interested in the spectral gap of $G$, i.e. the first nonzero eigenvalue of $\Delta$, denoted by $\lambda_{1}(G)$.
Is it true that a randomly chosen (with uniform distribution) $d$-regular bipartite graph on $(n, n)$ vertices (with multiple edges allowed) has, with probability approaching $1$ as $n \to \infty$, $\lambda_1$ arbitrarily close to $1$ (i.e. we can make arbitrarily close by taking $d$ large enough)?
If yes, is there a reference for this fact?
Proofs of expanding properties for random regular graphs which I have found in the literature usually give the probability only bounded from below by a constant, i. e. $1/2$, although I imagine that actually almost all random graphs have good spectral gap.
Note: by $d$-regular bipartite graph I mean a graph in which each vertex (on the left and on the right) has degree $d$.
Best Answer
Check out the new paper http://arxiv.org/abs/1212.5216 (Cor 1.6).
It is proven there that a random d-regular bipartite graph has its largest non-trivial eigenvalue at most 2\sqrt(d-1)+0.84.