MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

Check out the new paper (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.

share|cite|improve this answer

I assume you mean to fix $d$ and let $n$ grow. When $d \gt 3$ the graph (at least in the case that all vertices have degree $r$) will likely be connected and even $d$-connected. But in case $d=2$ one has a disjoint union of cycles. Then it seems likely that for fixed $m$ there is, with probability approaching 1, a cycle of size over $m$ as $n$ grows. That would give the result in that case.

share|cite|improve this answer

For $d$ fixed and $n$ goes to infinity, the neighborhood of each vertex looks like a tree, with high probability, and I guess you can use the traditional trace method.

share|cite|improve this answer

In the paper "On the second eigenvalue and random walks in random d-regular graphs" (Combinatorica 11 (1991), no. 4, 331–362), Joel Friedman considers a model of $2d$-regular random graphs on $n$ vertices, by selecting randomly and uniformly $d$ permutations from the symmetric group $S_n$, and looking at the undirected Schreier graph associated with these permutations and their inverses. He proves (using the trace method) that random graphs are close to being Ramanujan. Now his model naturally gives random $d$-regular bipartite graphs on $(n,n)$ vertices. Maybe his method can be adapted to that situation?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.