Diffusions on graphs, Poisson problems and spectral geometry

Authors:
Patrick McDonald and Robert Meyers

Journal:
Trans. Amer. Math. Soc. **354** (2002), 5111-5136

MSC (2000):
Primary 58J65, 58J50

DOI:
https://doi.org/10.1090/S0002-9947-02-02973-2

Published electronically:
August 1, 2002

MathSciNet review:
1926852

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study diffusions, variational principles and associated boundary value problems on directed graphs with natural weightings. We associate to certain subgraphs (domains) a pair of sequences, each of which is invariant under the action of the automorphism group of the underlying graph. We prove that these invariants differ by an explicit combinatorial factor given by Stirling numbers of the first and second kind. We prove that for any domain with a natural weighting, these invariants determine the eigenvalues of the Laplace operator corresponding to eigenvectors with nonzero mean. As a specific example, we investigate the relationship between our invariants and heat content asymptotics, expressing both as special values of an analog of a spectral zeta function.

**[A]**D. Aldous,*Applications of random walks on finite graphs*, Selected Proceedings of the Sheffield Symposium on Applied Probability (Sheffield, 1989) IMS Lecture Notes Monograph Ser.,, Inst. Math. Statist., Hayward, CA (1991), 12-26. MR**18****93g:60145****[B]**N. Biggs,*Algebraic potential theory on graphs*, Bull. London Math. Soc.(1998), 641-682. MR**29****98m:05120****[BG]**M. van den Berg and P. Gilkey,*Heat content asymptotics of a Riemannian manifold with boundary*, J. Funct. Anal.,**120**(1994), 48-71. MR**94m:58215****[C]**F. R. K. Chung,*Spectral Graph Theory*, Amer. Math. Soc. CBMS Regional Conference Series in Mathematics, Providence, RI, 1997, pp. 12-26. MR**92****97k:58183****[DS]**P. Diaconis and D. Stroock,*Geometric bounds for the eigenvalues of Markov chains*, Ann. Applied Prob.*1*(1991), 36-61. MR**92h:60103****[Do]**J. Dodziuk,*Difference equations, isoperimetric inequality and transience of certain random walks*, Trans AMS(1984), 787-794. MR**284****85m:58185****[DSn]**P. G. Doyle and J. L. Snell,*Random walks and electrical networks*, MAA Carus Monographs, Washington, D.C., 1984. MR**22****89a:94023****[Du]**R. Duffin,*Discrete potential theory*, Duke Math. J.(1953), 233-251. MR**20****16:1119d****[F1]**R. Forman,*Difference operators, covering spaces and determinants*, Topology(1989), 413-438. MR**28****91a:57012****[F2]**R. Forman,*Determinants and Laplacians on graphs*, Topology(1993), 35-46. MR**32****94g:58247****[Ge]**P. Gerl,*Random walks on graphs with a strong isoperimetric inequality*, J. Theor. Prob.(1988), 171-188. MR**1****89g:60216****[H]**R. Has'minskii,*Probabilistic representations of the solutions of some differential equations*, In: Proc. 6th All-Union Conf. On Theor. Prob. and Math. Stat. (Vilnius 1960) (1960). (Russian)**[K]**G. Kirchhoff,*Über die Auflösung der Gleichungen auf Welche man beider Untersuchen der linearen Vertheilung galvanischer Ströme gefüft wird*, Annalen der Physik und Chemie(1847), 495-508.**72****[KM]**K. K. J. Kinateder and P. McDonald,*Variational principles for average exit time moments for diffusions in Euclidean space*, Proc. Amer. Math. Soc.(1999), 2767-2772. MR**127****99m:60121****[KMM]**K. K. J. Kinateder, P. McDonald and D. Miller,*Exit time moments, boundary value problems, and the geometry of domains in Euclidean space*, Probab. Theory Related Fields**111**(1998), 469-487. MR**99h:60151****[M]**P. McDonald,*Isoperimetric conditions, Poisson problems and diffusions in Riemannian manifolds*, Potential Analysis**16**(2002), 115-138.**[SH]**J. A. Shohat and J. D. Tamarkin,*The Problem of Moments*, Amer. Math. Soc., New York, 1943. MR**5:5c****[Sp]**F. Spitzer,*Principles of Random Walk*, Springer Verlag, New York, NY, 1976. MR**53:9383****[V1]**N. Varopoulos,*Isoperimetric inequalities and Markov chains*, J. Funct. Anal.(1985), 215-239. MR**63****87e:60124****[V2]**N. Varopoulos,*Brownian motion and random walks on manifolds*, Ann. Inst. Fourier(1984), 243-269. MR**34****85m:58186****[Z]**D. Zwillinger et al., eds.,*CRC Standard Mathematical Tables and Formulae, 30th Edition*, CRC, New York, 1996.

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC (2000):
58J65,
58J50

Retrieve articles in all journals with MSC (2000): 58J65, 58J50

Additional Information

**Patrick McDonald**

Affiliation:
New College of Florida, 5700 N. Tamiani Trail, Sarasota, Florida 34243

Email:
ptm@virtu.sar.usf.edu

**Robert Meyers**

Affiliation:
The Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012-1110

Email:
meyersr@cims.nyu.edu

DOI:
https://doi.org/10.1090/S0002-9947-02-02973-2

Keywords:
Poisson problem,
random walk,
variational principles,
spectral graph theory,
Stirling numbers,
zeta functions

Received by editor(s):
July 1, 2001

Received by editor(s) in revised form:
October 26, 2001

Published electronically:
August 1, 2002

Article copyright:
© Copyright 2002
American Mathematical Society