Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T05:50:05Z http://mathoverflow.net/feeds/question/86346 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/86346/laplacians-on-graphs-vs-laplacians-on-riemannian-manifolds-lambda-2 Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$? Joseph O'Rourke 2012-01-22T02:01:24Z 2012-08-06T23:58:44Z <p>A graph $G$ is connected if and only if the second-largest eigenvalue $\lambda_2$ of the <a href="http://en.wikipedia.org/wiki/Laplacian_matrix" rel="nofollow">Laplacian</a> of $G$ is greater than zero. (See, e.g., the <a href="http://en.wikipedia.org/wiki/Algebraic_connectivity" rel="nofollow">Wikipedia article on algebraic connectivity</a>.)</p> <blockquote> <p>Is there an analogous statement for the eigenvalue $\lambda_2(M)$ of the <a href="http://en.wikipedia.org/wiki/Laplace_operator" rel="nofollow">Laplacian operator</a> $\Delta$ for an $n$-dimensional <strike>connected,</strike> closed Riemannian manifold $M$?</p> </blockquote> <p>($\Delta(f) = \nabla^2(f) = −\mathrm{div}(\mathrm{grad}(f))$.)</p> <p>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!</p> <p><b>Addendum</b>. See Richard Montgomery's interesting new comment on the Laplacian on the integer lattice.</p> http://mathoverflow.net/questions/86346/laplacians-on-graphs-vs-laplacians-on-riemannian-manifolds-lambda-2/86369#86369 Answer by Liviu Nicolaescu for Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$? Liviu Nicolaescu 2012-01-22T12:43:35Z 2012-01-22T12:49:41Z <p>In my opinion, Colin de Verdiere's book <a href="http://www-fourier.ujf-grenoble.fr/~ycolver/All-Articles/98a.pdf" rel="nofollow">"Spectre de Graphes"</a> is the best place to start investigating the connection between the discrete Laplacian and the manifold Laplacian.</p> <p>Recently, investigations in computer science (machine learning) lead to considerable progress. </p> <p>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.</p> <p>I know I skipped many details, but you can get precise statements in this nice paper by M. Belkin and P. Niyogi:</p> <p><a href="http://www.cse.ohio-state.edu/~mbelkin/papers/TT_JCSS_08.pdf" rel="nofollow">Towards a Theoretical Foundation for Laplacian-Based Manifold Methods</a></p> <p>M. <a href="http://www.cse.ohio-state.edu/~mbelkin/" rel="nofollow">Belkin's webpage</a> has additional info.</p> http://mathoverflow.net/questions/86346/laplacians-on-graphs-vs-laplacians-on-riemannian-manifolds-lambda-2/86411#86411 Answer by Alain Valette for Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$? Alain Valette 2012-01-22T23:09:24Z 2012-01-22T23:09:24Z <p>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 <a href="http://arxiv.org/pdf/math/0609599.pdf" rel="nofollow">http://arxiv.org/pdf/math/0609599.pdf</a> 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</p> http://mathoverflow.net/questions/86346/laplacians-on-graphs-vs-laplacians-on-riemannian-manifolds-lambda-2/92930#92930 Answer by Highwind for Laplacians on graphs vs. Laplacians on Riemannian manifolds: $\lambda_2$? Highwind 2012-04-02T21:47:47Z 2012-04-02T21:47:47Z <p>Hi,</p> <ol> <li><p>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.</p></li> <li><p>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.</p></li> <li><p>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.</p></li> </ol> <p>There may be easier ways of testing connectedness (e.g. using the mesh representation, Euler characteristic or flooding algorithms).</p>