17
$\begingroup$

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.

$\endgroup$
10
  • 1
    $\begingroup$ 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? $\endgroup$ Jan 22, 2012 at 2:15
  • 4
    $\begingroup$ 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 $\endgroup$
    – Asaf
    Jan 22, 2012 at 7:45
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 22, 2012 at 13:10
  • 1
    $\begingroup$ 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/… $\endgroup$ Jan 22, 2012 at 23:42
  • 1
    $\begingroup$ Thanks Asaf, Valerio, and Paul--All very useful comments! $\endgroup$ Jan 23, 2012 at 0:25

3 Answers 3

12
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ @Liviu: Very nice re cloud converging to manifold Laplacian! Thanks! $\endgroup$ Jan 22, 2012 at 13:24
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 22, 2012 at 13:30
7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ @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! $\endgroup$ Jan 23, 2012 at 0:24
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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