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

Here's the sort of thing I have in mind. Let $M$ be a Riemannian manifold, compact if it helps, and let $\Delta_M$ be the Laplace-Beltrami operator. Choose a sequence of triangulations of $M$ so that the triangles in the $n$th triangulation all have diameter smaller than $1/n$, and let $\Delta_n$ denote the corresponding graph Laplacian - that is, the operator which sends a function $f$ on the vertices of a graph to the function whose value at a vertex is the average of $f$ on all neighboring vertices.

Is there a precise sense in which $\Delta_n$ converges to $\Delta_M$? If not, can we at least calculate spectral invariants for $\Delta_M$ using spectral invariants for $\Delta_n$?

The question is a little strange since the graph Laplacian acts on a finite dimensional space (for a finite graph) while the ordinary Laplacian is an unbounded operator on infinite dimensional Hilbert space. It is also not clear that the two operators capture the same kind of geometric information; for example, the dimension of $M$ can be recovered from $\Delta_M$, but it is not obvious to me how to calculate the dimension of $M$ from the $\Delta_n$'s. Nevertheless, my intuition tells me that there's something out there.

Added: Thanks everyone for all the links / references - I'll need a few more days to chase them down. I'm glad there is so much literature on this question!

share|improve this question
The space on which the graph Laplacian acts ought to be embeddable into the space on which the ordinary Laplacian acts, say by using smooth bump functions around each vertex. Also, I assume you have to do some kind of rescaling by the lengths of the edges based on the motivating example of $\mathbb{R}$. –  Qiaochu Yuan Jun 4 '11 at 14:03
Does this paper help? arxiv.org/pdf/math/0609599 –  Alain Valette Jun 4 '11 at 14:07
And the abstract of the paper Alain linked to: arxiv.org/abs/math/0609599 –  Did Jun 5 '11 at 10:06
you should basically look at the 1-skelaton of the CW structure of the manifold. In any reasonable situation, you can define the homology using Hodge decomposition by harmonic forms, and the discrete laplacian on the 1-skeleton would be "compatible" with the usual laplacian. if you take more refined skelatons. See this draft of book by Lubotzky - citeseerx.ist.psu.edu/viewdoc/… , around page 34. –  Asaf Jun 6 '11 at 11:57
add comment

5 Answers

If laplacian $\Delta_n$ is defined just as $\[\Delta_n f\](u)=\sum_v (f(v)-f(u))$, where the sum is over all neighbors v of the vertex u, then the answer is NO. Informal reason is that such $\Delta_n$ does not feel the embedding of the graph into the manifold $M$ at all.

More promising approach is to define $\Delta_n$ as $\[\Delta_n f\](u)=\sum_v c(uv)(f(v)-f(u))/m(u)$ with some edge weights $c(uv)$ and vertex weights $m(u)$ depending on the embedding of the graph into $M$. For right choice of weights the answer is positive in some particular cases: e.g., square lattice in the plane, isoradial triangulation of the plane, regular triangulation of the plane. In general there is no ``natural'' laplacian $\Delta_n$ such that convergence holds.

Here are some references, see also references therein:

[1] M. Wardetzky, S. Mathur, F. Kaberer, E. Grinspun, Discrete Laplace operators: no free lunch, Eurographics Symp. Geom. Processing, A.~Belyaev, M.~Garland (eds.), 2007.

[2] D. Chelkak and S. Smirnov, Discrete complex analysis on isoradial graphs, Adv. Math., to appear, http://arxiv.org/abs/0810.2188v2.

[3] R. Courant, K. Friedrichs, H. Lewy, Uber die partiellen Differenzengleichungen der mathematischen Physik, Math. Ann. 100, (1928), 32--74. English transl.: IBM Journal (1967), 215--234. Russian transl.: Russ. Math. Surveys 8 (1941), 125--160. http://www.stanford.edu/class/cme324/classics/courant-friedrichs-lewy.pdf

share|improve this answer
add comment

A paper that seems to give a high-level overview and useful references is Singer, A. "From graph to manifold Laplacian: The convergence rate". Appl. Comput. Harmon. Anal. 21, 128 (2006). (link)

share|improve this answer
add comment

Yves Colin de Verdi`ere's work non the $\mu-$invariant of graphs was motivated by discretizing Schr\"odinger operators on surfaces (endowed with Riemannian metrics). His papers (mainly in French but probably largely readable by somebody speaking English) on the subject might therefore be interesting to you, see for example his book "Spectres de graphe", Cours Spécialisés, 4. Société Mathématique de France, Paris, 1998. viii+114 pp.

share|improve this answer
add comment

Koltchinskii an Gine study how discrete Laplacians constructed for randomly sampled points on a manifold approximate the true Laplacian:


share|improve this answer
add comment

For some reasons, this is a question much studied in the community of theoretical computer scientists. Some relevant (and rather interesting) papers have been written by Belkin and Niyogi; and by Audibert, Hein and von Luxburg.

share|improve this answer
add comment

Your Answer


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.