Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
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
    
Yes, Chung's Laplacian is a positive semidefinite matrix. I think that explains things. Thanks again for your help! :-) –  Dimitrije Kostic Nov 29 '11 at 17:29

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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