Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Remote Access
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

 

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
Published electronically: August 1, 2002
MathSciNet review: 1926852
Full-text PDF Free Access

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.


References [Enhancements On Off] (What's this?)

  • [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., 18, Inst. Math. Statist., Hayward, CA (1991), 12-26. MR 93g:60145
  • [B] N. Biggs, Algebraic potential theory on graphs, Bull. London Math. Soc. 29 (1998), 641-682. MR 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 92, Providence, RI, 1997, pp. 12-26. MR 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 284 (1984), 787-794. MR 85m:58185
  • [DSn] P. G. Doyle and J. L. Snell, Random walks and electrical networks, MAA Carus Monographs 22, Washington, D.C., 1984. MR 89a:94023
  • [Du] R. Duffin, Discrete potential theory, Duke Math. J. 20 (1953), 233-251. MR 16:1119d
  • [F1] R. Forman, Difference operators, covering spaces and determinants, Topology 28 (1989), 413-438. MR 91a:57012
  • [F2] R. Forman, Determinants and Laplacians on graphs, Topology 32 (1993), 35-46. MR 94g:58247
  • [Ge] P. Gerl, Random walks on graphs with a strong isoperimetric inequality, J. Theor. Prob. 1 (1988), 171-188. MR 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 72 (1847), 495-508.
  • [KM] K. K. J. Kinateder and P. McDonald, Variational principles for average exit time moments for diffusions in Euclidean space, Proc. Amer. Math. Soc. 127 (1999), 2767-2772. MR 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. 63 (1985), 215-239. MR 87e:60124
  • [V2] N. Varopoulos, Brownian motion and random walks on manifolds, Ann. Inst. Fourier 34 (1984), 243-269. MR 85m:58186
  • [Z] D. Zwillinger et al., eds., CRC Standard Mathematical Tables and Formulae, 30th Edition, CRC, New York, 1996.

Similar Articles

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: http://dx.doi.org/10.1090/S0002-9947-02-02973-2
PII: S 0002-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