Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

4 Answers 4

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.

share|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.