3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ The definition of "Laplacian" in this OP seems very unusual to me; also, since diagonal matrices of course commute with any other matrix, we can simplify the definition in the OP: $I-D^{-1/2}AD^{-1/2}=I-D^{-1/2}D^{-1/2}A=I-D^{-1}A$. Hence, the OP has $D\cdot\Delta = D - A$, whereas the most usual definition is $\mathrm{Laplacian}(G)=D-A$, cf. e.g. Zoran Stanić: Inequalities for Graph Eigenvalues. LMS LNS 423, p. 12. The definition in the OP seems to be misleading. I won't touch it, out of respect and doubt. Would you please say if and why you intend to use this definition? $\endgroup$
    – Peter Heinig
    Commented Oct 10, 2017 at 17:54
  • 1
    $\begingroup$ In general, diagonal matrices don't commute with any other matrix $\endgroup$
    – Karagounis Z
    Commented Jan 5, 2022 at 7:03

4 Answers 4

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .