Diffusions on graphs, Poisson problems and spectral geometry
Authors:
Patrick McDonald and Robert Meyers
Journal:
Trans. Amer. Math. Soc. 354 (2002), 51115136
MSC (2000):
Primary 58J65, 58J50
Published electronically:
August 1, 2002
MathSciNet review:
1926852
Fulltext 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.
 [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), 1226. MR 93g:60145
 [B]
N. Biggs, Algebraic potential theory on graphs, Bull. London Math. Soc. 29 (1998), 641682. 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), 4871. 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. 1226. MR 97k:58183
 [DS]
P. Diaconis and D. Stroock, Geometric bounds for the eigenvalues of Markov chains, Ann. Applied Prob. 1 (1991), 3661. MR 92h:60103
 [Do]
J. Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans AMS 284 (1984), 787794. 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), 233251. MR 16:1119d
 [F1]
R. Forman, Difference operators, covering spaces and determinants, Topology 28 (1989), 413438. MR 91a:57012
 [F2]
R. Forman, Determinants and Laplacians on graphs, Topology 32 (1993), 3546. MR 94g:58247
 [Ge]
P. Gerl, Random walks on graphs with a strong isoperimetric inequality, J. Theor. Prob. 1 (1988), 171188. MR 89g:60216
 [H]
R. Has'minskii, Probabilistic representations of the solutions of some differential equations, In: Proc. 6th AllUnion 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), 495508.
 [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), 27672772. 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), 469487. MR 99h:60151
 [M]
P. McDonald, Isoperimetric conditions, Poisson problems and diffusions in Riemannian manifolds, Potential Analysis 16 (2002), 115138.
 [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), 215239. MR 87e:60124
 [V2]
N. Varopoulos, Brownian motion and random walks on manifolds, Ann. Inst. Fourier 34 (1984), 243269. MR 85m:58186
 [Z]
D. Zwillinger et al., eds., CRC Standard Mathematical Tables and Formulae, 30th Edition, CRC, New York, 1996.
 [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), 1226. MR 93g:60145
 [B]
 N. Biggs, Algebraic potential theory on graphs, Bull. London Math. Soc. 29 (1998), 641682. 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), 4871. 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. 1226. MR 97k:58183
 [DS]
 P. Diaconis and D. Stroock, Geometric bounds for the eigenvalues of Markov chains, Ann. Applied Prob. 1 (1991), 3661. MR 92h:60103
 [Do]
 J. Dodziuk, Difference equations, isoperimetric inequality and transience of certain random walks, Trans AMS 284 (1984), 787794. 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), 233251. MR 16:1119d
 [F1]
 R. Forman, Difference operators, covering spaces and determinants, Topology 28 (1989), 413438. MR 91a:57012
 [F2]
 R. Forman, Determinants and Laplacians on graphs, Topology 32 (1993), 3546. MR 94g:58247
 [Ge]
 P. Gerl, Random walks on graphs with a strong isoperimetric inequality, J. Theor. Prob. 1 (1988), 171188. MR 89g:60216
 [H]
 R. Has'minskii, Probabilistic representations of the solutions of some differential equations, In: Proc. 6th AllUnion 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), 495508.
 [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), 27672772. 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), 469487. MR 99h:60151
 [M]
 P. McDonald, Isoperimetric conditions, Poisson problems and diffusions in Riemannian manifolds, Potential Analysis 16 (2002), 115138.
 [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), 215239. MR 87e:60124
 [V2]
 N. Varopoulos, Brownian motion and random walks on manifolds, Ann. Inst. Fourier 34 (1984), 243269. 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 100121110
Email:
meyersr@cims.nyu.edu
DOI:
http://dx.doi.org/10.1090/S0002994702029732
PII:
S 00029947(02)029732
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
