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_2(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_2$ arbitrarily close to $1$ (i.e. $d$ is fixed and we may take it large enough so that asymptotically most graphs will have $\lambda_2 > 1 - \epsilon$, where $\epsilon$ depends on $d$)?

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 bipartite 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$.

  • 2
    $\begingroup$ Also crosspost on MathOverflow. $\endgroup$ May 18, 2011 at 1:18
  • $\begingroup$ if you allow multiple edges, then there are infinitely many $d$-regular bipartite graphs on $(n,n)$ vertices, so you cannot use the uniform distribution. $\endgroup$ May 25, 2011 at 19:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.