<p>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)$.</p>

<p>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 &gt; 1 - \epsilon$, where $\epsilon$ depends on $d$)?</p>

<p>If yes, is there a reference for this fact?</p>

<p>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.</p>

<p>Note: by $d$-regular bipartite graph I mean a graph in which each vertex (on the left and on the right) has degree $d$.</p>

CC BY-SA 3.0
2011-05-18T01:18:04.487Z
Also [crosspost on MathOverflow](http://mathoverflow.net/questions/65166/spectral-gap-for-random-bipartite-regular-graphs).
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-05-25T19:31:26.667Z
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.
Tyson Williams
<reference-request><graph-theory><co.combinatorics><spectral-graph-theory>
Spectral gap for random bipartite regular graphs
Marcin Kotowski
# Spectral gap for random bipartite regular graphs

(Asked by: username_0 on 2011-05-17)

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

**Tags:** reference-request, graph-theory, co.combinatorics, spectral-graph-theory
> **Comments:**
> **username_1**: Also [crosspost on MathOverflow](http://mathoverflow.net/questions/65166/spectral-gap-for-random-bipartite-regular-graphs).  
> **username_2**: 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.  

---

## 0 answers

