3
$\begingroup$

Let $G$ be an undirected simple graph on $n$ vertices, with self-loops allowed, and with arbitrary positive edge weights $w_{u,v}$ (which is $0$ if there is no edge between $u$ and $v$).

Let $A$ be the adjacency matrix of $G$, i.e. the rows and columns are indexed by vertices of $G$ and $A_{u,v} = w_{u,v}$. Let $D$ be the diagonal degree matrix: $D_{u,u} = \deg(u) = \sum_v w_{u,v}$ and $D_{u,v} = 0$ for $u \neq v$. Let $L = D - A$ be the Laplacian matrix of the graph.

Both $A$ and $L$ are self-adjoint. Let $\mu_1 \leq \mu_2 \dotsb \leq \mu_n$ be the eigenvalues of $A$, and let $0 = \lambda_1 \leq \lambda_2 \leq \dotsb \leq \lambda_n$ be the eigenvalues of $L$.

I have run many tests, and it looks like the (top) spectral gap $\mu_n - \mu_{n-1}$ of $A$ is always at least as large as the (bottom) spectral gap $\lambda_2 - \lambda_1 = \lambda_2$ of $L$.

The two quantities are equal if $G$ is regular, i.e. all vertices have the same degree, because then $D = \deg(u) I$ for any vertex $u$ of $G$, and so the spectrum of $L$ is a shift and reflection of the spectrum of $A$. In my tests, as the difference between the maximum and minimum degrees of $G$ gets larger (i.e. as $G$ becomes "less regular"), the difference $(\mu_n - \mu_{n-1}) - \lambda_2$ gets larger as well (on average). The relationship seems to be rougly linear.

It seems to me like this should be a known phenomenon (if indeed it is true), but I haven't been able to find it anywhere in the literature. If anyone has seen this before, please let me know. Otherwise I'll just try to prove it myself.

$\endgroup$
2
  • $\begingroup$ Update: the relationship which I said "seems to be roughly linear" is actually not linear in general. The sequence of star graphs has (min degree - max degree) ~ n, but the difference between the spectral gaps is ~ sqrt(n). $\endgroup$ Jul 11 at 7:49
  • $\begingroup$ Another update: there is actually no correlation (in general) with (max degree - min degree). Let G be the graph on three vertices, where two of them have self-loops of weight n and the other one has degree 0. Then (max degree - min degree) = n, but the spectral gaps of A and L are both 0. $\endgroup$ Jul 12 at 15:00
1
$\begingroup$

Well, I found a counterexample (actually, many) to this claim. In fact, it only has 7 vertices: it is given by the graph6 string "F{O_w". Here's a picture:

enter image description here

Now the question becomes whether there is a sequence of graphs with Laplacian spectral gap bounded away from 0 and Adjacency spectral gap approaching 0. So far, I have not found any such sequence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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