5
$\begingroup$

In Chung and Yau's paper: "A combinatorial trace formula" (MSN), they proved a combinatorial version of Selberg's trace formula for lattice graphs. I learned also in the setup that it makes sense to define Laplacian, its eigenvalues, and heat kernel of a graph (could be infinite and with loops). It showed a strong analogue to Riemannian geometry!

On both sides, we can extract useful information from the objects' spectra. This was not overwhelmingly surprising to me, however, in the geometric case because I can sort of feel the picture of a laplacian and heat kernel based on my experience.

Questions

What's curious to me are the following:

  1. Having zero experience with graph theory, is there a better way to appreciate/interpret what those eigenvalues, heat kernel, … mean?
  2. There must be much more behind it. What are some updated important results? Do people understand this much better than they did 23 years ago?
  3. Most interestingly (to me), is there a way to extract a graph $G$ from a given Riemannian manifold $M$, so that the spectral theory on both sides agree?

Any pointers to related work will be highly appreciated.

$\endgroup$
2
  • 1
    $\begingroup$ The paper "Discrete Laplace operators: no free lunch" by Wardetzky, Mathur, K{\"a}lberer, and Grinspun (cs.columbia.edu/cg/pdfs/1180993110-laplacian.pdf) discusses several nice properties of the Laplacian (symmetry, positive semi-definiteness, maximum principle, kernel containing the constant functions, and two others) and shows that no linear operator on functions defined on a triangular mesh can have all of these properties. (continued) $\endgroup$
    – Sophie M
    Oct 31, 2019 at 17:18
  • 1
    $\begingroup$ As they say in the abstract, this retroactively explains the diversity of discrete Laplacians in the literature. I don't know to what extent this result applies to Chung and Yau's setup. $\endgroup$
    – Sophie M
    Oct 31, 2019 at 17:18

1 Answer 1

6
$\begingroup$

For construction of a sequence of discrete Laplacians whose spectrum converges to that of a given Riemannian manifold, see

Dodziuk, Jozef, Finite-difference approach to the Hodge theory of harmonic forms, Am. J. Math. 98, 79-104 (1976). ZBL0324.58001.

A good survey on spectral graph theory is

Colin de Verdière, Yves, Spectres de graphes, Cours Spécialisés. 4. Paris: Société Mathématique de France. vi, 114 p. (1998). ZBL0913.05071.

(There are surely more recent surveys or lecture notes, maybe somebody else can point at them.)

Eigenvalues of the graph Laplacian carry interesting combinatorial information, such as the expansion parameter and the number of spanning trees, see Wikipedia articles Expander graphs and Kirchhoff's theorem. In order to approximate the geometry of a manifold, it is appropriate to use weights on the edges. The so-called cotangent Laplacian (well-known in dimension 2 and having an analog in higher dimensions) is a good choice.

$\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.