Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A graph $G$ is connected if and only if the second-largest eigenvalue $\lambda_2$ of the Laplacian of $G$ is greater than zero. (See, e.g., the Wikipedia article on algebraic connectivity.)

Is there an analogous statement for the eigenvalue $\lambda_2(M)$ of the Laplacian operator $\Delta$ for an $n$-dimensional connected, closed Riemannian manifold $M$?

($\Delta(f) = \nabla^2(f) = −\mathrm{div}(\mathrm{grad}(f))$.)

I am trying to understand the relationship between Laplacians on graphs and Laplacians on Riemannian manifolds. Pointers to help elucidate the connection would be greatly appreciated!

Addendum. See Richard Montgomery's interesting new comment on the Laplacian on the integer lattice.

share|improve this question
1  
I don't understand why you require that $M$ is connected. Isn't it true in both cases that the space of harmonic functions is precisely the space of locally constant functions, so its dimension is the number of connected components? –  Qiaochu Yuan Jan 22 '12 at 2:15
4  
If the manifold has finitely many connected components, then L^2(M) decomposes as direct sum over the L^2 spaces of the separate connected components. Every connected component contribute the constant space $$\mathbb{C}\cdot 1$$ to be an eigenvector of eigenvalue $0$, hence the multiplicity of the the eigenvalue $0$ equals to the number of connected components. The connection between graphs and manifolds is more explicit by approximating the manifold with its 1 skeleton structure see in the book by Lubotzky - ma.huji.ac.il/~alexlub/BOOKS/On%20property/On%20property.pdf , p.34 –  Asaf Jan 22 '12 at 7:45
1  
This is a general comment about the relation between the laplacian graph and the one on Riemannian manifold. Suppose $M$ compact and let $T$ be a triangulation of $M$. Given $n\in\mathbb N$ denote by $T_n$ the triangulation of $M$ obtained by $T$ doing $n$-times a barycentric subdivision of $T$. Denote by $\Delta_n$ the discrete Laplacian of the natural connected graph constructed on the 1-skeleton of $T_n$. It is possible that $\Delta_n$ converges in some suitable sense to $\Delta$ and this should give some transference principle. –  Valerio Capraro Jan 22 '12 at 13:10
1  
This probably won't answer your question directly, but I got a lot of useful references in the responses to this question: mathoverflow.net/questions/66892/… –  Paul Siegel Jan 22 '12 at 23:42
1  
Thanks Asaf, Valerio, and Paul--All very useful comments! –  Joseph O'Rourke Jan 23 '12 at 0:25

3 Answers 3

Hi,

  1. Note that in either case (graph or manifold) several Laplace Operator discrtizations exists (with different properties). Some of these do not converge to the true (continuous) operator when mesh size is reduced. Higher order FEM approaches can yield fast convergence. Most operators are linear approximations.

  2. On the manifold discretization (usually triangles for surfaces), you have geometric information, e.g. the angles between edges, which does not necessarily exist in the graph case.

  3. For any operator on a manifold (mesh) that discretizes the contniuous Laplacian this holds: the eigenvalues are a diverging sequence of real positive numbers (including zero, and of course the number of eigenvalues is limited by the discretization). The first eigenvalue is zero if the manifold is closed, or if the Neumann boundary condition is applied at the boundary. It is larger zero for Dirichlet boundary condition. Iff you have n eigenvalues that are zero, you have n connected components.

There may be easier ways of testing connectedness (e.g. using the mesh representation, Euler characteristic or flooding algorithms).

share|improve this answer

Take a finite cover $\cal{U}$ of $M$ by open subsets, and view the nerve $N({\cal U})$ of this cover as a finite simplicial complex, carrying a combinatorial Laplace operator in each degree. By choosing $\cal{U}$ carefully, with a small enough mesh, in all degree $p$ you may approximate the $k$ first eigenvalues of the Laplace-Beltrami operator on $p$-forms of $M$, by the corresponding eigenvalues of the combinatorial Laplace operator in degree $p$ on $N({\cal U})$. Here $k=s_p({\cal U})-b_p(M)$, where $s_p({\cal U})$ is the number of $p$-simplices. See Theorem 3.1 in a paper by T. Mantuano http://arxiv.org/pdf/math/0609599.pdf Reference: Discretization of Riemannian manifolds applied to the Hodge Laplacian, Tatiana Mantuano, Source American Journal of Mathematics, Volume 130, Number 6, December 2008, pp. 1477-1508

share|improve this answer
    
@Alain: Your reference is precisely on point. That paper's introduction gives a useful summary of discretizing a manifold to study the spectrum of its Laplacian. Thanks! –  Joseph O'Rourke Jan 23 '12 at 0:24

In my opinion, Colin de Verdiere's book "Spectre de Graphes" is the best place to start investigating the connection between the discrete Laplacian and the manifold Laplacian.

Recently, investigations in computer science (machine learning) lead to considerable progress.

Pick a "cloud" of points in a Riemann manifold. Consider the complete graph with vertices on these points. Next add weights to the edges that correlate with the geodesic distance between the corresponding points on the manifold. Then form a certain weighted Laplacian associated to this weighted graph. This operator converges with probability one to the the manifold Laplacian as the cloud is bigger and bigger and is chosen randomly with respect to the metric volume measure on the manifold.

I know I skipped many details, but you can get precise statements in this nice paper by M. Belkin and P. Niyogi:

Towards a Theoretical Foundation for Laplacian-Based Manifold Methods

M. Belkin's webpage has additional info.

share|improve this answer
    
@Liviu: Very nice re cloud converging to manifold Laplacian! Thanks! –  Joseph O'Rourke Jan 22 '12 at 13:24
1  
Belkin and Niyogi have a paper called "Convergence of Laplacian Eigenmaps" where they show that the spectrum of the above weighetd discrete Laplacian converges to the spectrum of the manifold Laplacian. –  Liviu Nicolaescu Jan 22 '12 at 13:30

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.