## Is the Laplacian on a manifold the limit of graph Laplacians?

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!

-
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 2011 at 14:03
Does this paper help? arxiv.org/pdf/math/0609599 – Alain Valette Jun 4 2011 at 14:07
And the abstract of the paper Alain linked to: arxiv.org/abs/math/0609599 – Didier Piau Jun 5 2011 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 2011 at 11:57

Yves Colin de Verdiere'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.

-

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

http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.lnms/1196284116

-

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.

[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

-

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)

-