# What does the minimal eigenvalue of a graph say about the graph's connectivity?

I'm reading Fan Chung's Spectral Graph Theory, and I'm now in chapter 2. There, Chung proves Cheeger's inequality, which is that $2h_G \geq \lambda_1 > h_G^2/2$ for any graph $G$. To me, this inequality raises the question of a physical interpretation of $\lambda_1$ and I'm wondering if such an interpretation exists. Below, I'll explain this terminology and ask my question a little more precisely.

Let $G$ be a graph with vertex set $V$, with $\#V =n$. The Laplacian of $G$ is the $n\times n$ matrix $\mathcal{L}$ whose $(u,v)^{\text{th}}$ entry is $\text{deg}(v)$ if $u=v$, $-(\text{deg}(u)\text{deg}(v))^{-1/2}$ if $u$ and $v$ are adjacent vertices, and $0$ otherwise. The eigenvalues of $\mathcal{L}$ are called the eigenvalues of $G$ and are denoted by $\lambda_0 \leq \lambda_1 \leq \dots \leq \lambda_{n-1}$. It's not too hard to show that $\lambda_0$ is always $0$, so we normally refer to $\lambda_1$ as the minimal eigenvalue of $G$.

If $S\subset V$ (with $S\neq V$) then we define $\overline{S} := V-S$ and $E(S,\overline{S})$ to be the set of edges of $G$ with one vertex in $S$ and the other in $\overline{S}$. Also, let the volume of $S$ be defined as $\text{vol}(S) := \sum_{v \in S} \text{deg}(v)$. We then define $$h_G(S) := \frac{\# E(S,\overline{S})}{\text{min}(\text{vol}(S),\text{vol}(\overline{S}))}.$$ The Cheeger constant of $G$ is defined to be $h_G := \min_{S \subset V} h_G(S)$.

It's clear from the definition that the Cheeger constant measures how much the graph "bottlenecks" somewhere (to borrow Wikipedia's apt description). Loosely speaking, if Cheeger's constant is small then there's a small set of edges that you can remove from the graph to disconnect it into two relatively large and relatively connected subgraphs.

Now, it doesn't seem like $\lambda_1$ (which equals the minimal Rayleigh quotient over the space of harmonic eigenfunctions) would have much of a physical interpretation. However, Cheeger's inequality traps $\lambda_1$ fairly close to $h_G$, so it is some loose measure of bottlenecking. Also, there are other little hints in the text I've read so far that $\lambda_1$ might be related to the graph's connectedness. For instance, she proves $\lambda_1 = 0$ if and only if $G$ is disconnected and that $\lambda_1 \geq 1/D\text{vol}(G)$, where $D$ is the length of the maximal-length path in $G$.

So I'm wondering if there is a meaningful physical interpretation of $\lambda_1$ that is more precise than "it's bounded near something that is meaningful."

-
Can you explain what you denote by $\lambda_1$? There are quite a few choices for us: (a.) maximum vs. minimum, and (b.) adjacency vs. Laplacian matrices... – Srivatsan Nov 28 '11 at 23:14
@Srivatsan: My notation is consistent with Chung's book. However, to make the post self-contained, I've just edited it. Hopefully it's clearer now. – Dimitrije Kostic Nov 29 '11 at 5:01

The smallest (in absolute value) eigenvalue $\lambda_1$ of the Laplacian (I don't know if this agrees with your definition of $\lambda_1$; I recall not liking Chung's definitions) measures how fast heat dissipates on the graph.
More precisely, for a (finite, for simplicity) graph $G = (V, E)$ with Laplacian $\Delta$ (regarded as an operator acting on functions $V \to \mathbb{R}$), the heat equation for a function $u(v, t) : V \times \mathbb{R} \to \mathbb{R}$ $$\Delta u = \frac{\partial u}{\partial t}$$
has general solution $$u(v, t) = \sum_{k=0}^{n-1} e^{\lambda_i t} f_i(v)$$
where $f_i : V \to \mathbb{R}$ is the eigenvector of $\Delta$ with eigenvalue $\lambda_i$ (and recall that $\lambda_0 = 0$). As a function of $t$, the dominant term above is the term $e^{\lambda_1 t} f_1(v)$, which controls the decay of the heat distribution $u$ as $t \to \infty$. Intuitively you should think of the heat equation as describing a "continuous-time random walk" on the graph. If such a random walk mixes quickly (so $\lambda_1$ is large in absolute value), then the graph is highly connected; if not, then perhaps the graph has bottlenecks of some kind. Cheeger's inequality makes this intuition precise.
First, thanks for your thoughtful reply. I was hoping for an explanation like that (and a little skeptical that I'd get one). But I'm a little puzzled; since $\lambda_{n-1}$ is the largest eigenvalue, isn't $e^{\lambda_{n-1}t}f_{n-1}(v)$ the dominant term of the sum? Chung discusses material similar to this in chapter 10. There, she gives the heat equation as $-\Delta u = \frac{\delta u}{\delta t}$ and her solution has $e^{-\lambda_i t}$'s. In that sum, the $\lambda_1$ term is the dominant one. Did you mean to define things this way? – Dimitrije Kostic Nov 29 '11 at 5:49
@Dimitrije: in my preferred convention, the Laplacian is negative-semidefinite, so its nonzero eigenvalues are negative (for better agreement with the Laplacian on, say, $\mathbb{R}^n$). $\lambda_1$ is the smallest eigenvalue in absolute value, so it is the least negative. Chung's Laplacian might be positive-definite. – Qiaochu Yuan Nov 29 '11 at 14:08