Difference equations, isoperimetric inequality and transience of certain random walks
Author:
Jozef Dodziuk
Journal:
Trans. Amer. Math. Soc. 284 (1984), 787794
MSC:
Primary 58G32; Secondary 35J05, 39A12, 53C99
MathSciNet review:
743744
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The difference Laplacian on a square lattice in has been studied by many authors. In this paper an analogous difference operator is studied for an arbitrary graph. It is shown that many properties of the Laplacian in the continuous setting (e.g. the maximum principle, the Harnack inequality, and Cheeger's bound for the lowest eigenvalue) hold for this difference operator. The difference Laplacian governs the random walk on a graph, just as the Laplace operator governs the Brownian motion. As an application of the theory of the difference Laplacian, it is shown that the random walk on a class of graphs is transient.
 [AhS]
Lars
V. Ahlfors and Leo
Sario, Riemann surfaces, Princeton Mathematical Series, No.
26, Princeton University Press, Princeton, N.J., 1960. MR 0114911
(22 #5729)
 [C]
J. Cheeger, A lower bound for the lowest eigenvalue of the Laplacian, Problems in Analysis, A Symposium in honor of S. Bochner, Princeton Univ. Press, Princeton, N.J., 1970, pp. 195199.
 [CFL]
R. Courant, K. Friedrichs and H. Lewy, Über die partiellen Differenzengleichungen der mathematischen Physik, Math. Ann. 100 (1928), 3274.
 [DB]
David
R. DeBaun, 𝐿²cohomology of
noncompact surfaces, Trans. Amer. Math.
Soc. 284 (1984), no. 2, 543–565. MR 743732
(85h:58011), http://dx.doi.org/10.1090/S00029947198407437323
 [Do]
Jozef
Dodziuk, Every covering of a compact Riemann surface of genus
greater than one carries a nontrivial 𝐿² harmonic
differential, Acta Math. 152 (1984), no. 12,
49–56. MR
736211 (85j:30090), http://dx.doi.org/10.1007/BF02392190
 [Du]
R.
J. Duffin, Discrete potential theory, Duke Math. J.
20 (1953), 233–251. MR 0070031
(16,1119d)
 [KSK]
John
G. Kemeny, J.
Laurie Snell, and Anthony
W. Knapp, Denumerable Markov chains, 2nd ed., SpringerVerlag,
New YorkHeidelbergBerlin, 1976. With a chapter on Markov random fields,
by David Griffeath; Graduate Texts in Mathematics, No. 40. MR 0407981
(53 #11748)
 [AhS]
 L. V. Ahlfors and L. Sario, Riemann surfaces, Princeton Univ. Press, Princeton, N.J., 1974. MR 0114911 (22:5729)
 [C]
 J. Cheeger, A lower bound for the lowest eigenvalue of the Laplacian, Problems in Analysis, A Symposium in honor of S. Bochner, Princeton Univ. Press, Princeton, N.J., 1970, pp. 195199.
 [CFL]
 R. Courant, K. Friedrichs and H. Lewy, Über die partiellen Differenzengleichungen der mathematischen Physik, Math. Ann. 100 (1928), 3274.
 [DB]
 D. DeBaun, cohomology of noncompact surfaces, Trans. Amer. Math. Soc. (to appear). MR 743732 (85h:58011)
 [Do]
 J. Dodziuk, Every covering of a compact Riemann surface of genus greater than one carries a nontrivial harmonic differential, Acta Math, (to appear). MR 736211 (85j:30090)
 [Du]
 R. Duffin, Discrete potential theory, Duke Math. J. 20 (1953), 233251. MR 0070031 (16:1119d)
 [KSK]
 J. G. Kemeny, J. L. Snell and A. W. Knapp, Denumerable Markov chains, 2nd ed., SpringerVerlag, New York, 1976. MR 0407981 (53:11748)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC:
58G32,
35J05,
39A12,
53C99
Retrieve articles in all journals
with MSC:
58G32,
35J05,
39A12,
53C99
Additional Information
DOI:
http://dx.doi.org/10.1090/S0002994719840743744X
PII:
S 00029947(1984)0743744X
Article copyright:
© Copyright 1984
American Mathematical Society
