Lower bound for spectral gap for graph on $n$ vertices

695 Views Asked by At

Let $G = (V,E)$ be a graph on the vertex set $V$ with edges $E$. Let $A$ be the adjacency matrix for $G$ (so $A_{ij} = 1$ if vertices $v_i$ and $v_j$ are connected by an edge), and $D$ be the diagonal degree matrix ($D_{ii}$ is the degree of $v_i$). Define the graph Laplacian to be the matrix $$ L = D - A. $$ Here I'm using the conventions and normalizations of the wikipedia article on the graph Laplacian. This Laplacian is symmetric and positive definite, with eigenvalues $0 = \lambda_1\le \lambda_2\le \cdots \le \lambda_n$. Assuming that $G$ is connected, $\lambda_2 > 0$. This is the quantity I would like to know more about.

First, I would like to know what bounds are available for $\lambda_2$ for a graph on $n$ vertices. The spectral gap $\lambda_2$ measures connectivity, so it seems that the "least connected" graph on $n$ vertices would be the linear one, since its diameter is the largest possible. This graph has spectral gap $$ \lambda_2 = \frac{\pi^2+o_n(1)}{n^2}. $$

Question 1: Is it true that for any connected graph $G$ on $n$ vertices, $n^2 \lambda_2 \ge \pi^2+o_n(1)$?

The second question is what happens when $\lambda_2$ is close to $\pi^2/n^2$.

Question 2: Suppose $G$ is a graph on $n$ vertices with spectral gap $\lambda_2 = (\pi^2+\varepsilon)/n^2$ for some small $\varepsilon>0$. In what sense is $G$ close to a linear graph?

Any references on this topic would be appreciated.