|
Loop-erased walks and total positivity
Author:
Sergey Fomin
Journal:
Trans. Amer. Math. Soc. 353 (2001), 3563-3583
MSC (2000):
Primary 15A48; Secondary 05C50, 31C20, 60J65
Posted:
April 9, 2001
MathSciNet review:
1837248
Full-text PDF Free Access
Abstract |
References |
Similar Articles |
Additional Information
Abstract: We consider matrices whose elements enumerate weights of walks in planar directed weighted graphs (not necessarily acyclic). These matrices are totally nonnegative; more precisely, all their minors are formal power series in edge weights with nonnegative coefficients. A combinatorial explanation of this phenomenon involves loop-erased walks. Applications include total positivity of hitting matrices of Brownian motion in planar domains.
- 1.
I. Benjamini, R. Lyons, Y. Peres, and O. Schramm, Uniform spanning forests, Ann. Probab., to appear.
- 2.
W.
Böhm and S.
G. Mohanty, On the Karlin-McGregor theorem and applications,
Ann. Appl. Probab. 7 (1997), no. 2, 314–325. MR 1442315
(98g:60131), http://dx.doi.org/10.1214/aoap/1034625333
- 3.
Béla
Bollobás, Modern graph theory, Graduate Texts in
Mathematics, vol. 184, Springer-Verlag, New York, 1998. MR 1633290
(99h:05001)
- 4.
J. M. Borwein, D. M. Bradley, D. J. Broadhurst, and P. Lisonek, Special values of multiple polylogarithms, Trans. Amer. Math. Soc., to appear.
- 5.
Y. Colin de Verdière, Réseaux électriques planaires, Prépublications de l'Institut Fourier 225 (1992), 1-20.
- 6.
E.
B. Curtis, D.
Ingerman, and J.
A. Morrow, Circular planar graphs and resistor networks,
Linear Algebra Appl. 283 (1998), no. 1-3,
115–150. MR 1657214
(99k:05096), http://dx.doi.org/10.1016/S0024-3795(98)10087-3
- 7.
E.
Curtis, E.
Mooers, and J.
Morrow, Finding the conductors in circular networks from boundary
measurements, RAIRO Modél. Math. Anal. Numér.
28 (1994), no. 7, 781–814 (English, with
English and French summaries). MR 1309415
(96i:65110)
- 8.
Peter
G. Doyle and J.
Laurie Snell, Random walks and electric networks, Carus
Mathematical Monographs, vol. 22, Mathematical Association of America,
Washington, DC, 1984. MR 920811
(89a:94023)
- 9.
Richard
Durrett, Brownian motion and martingales in analysis,
Wadsworth Mathematics Series, Wadsworth International Group, Belmont, CA,
1984. MR
750829 (87a:60054)
- 10.
Sergey
Fomin and Andrei
Zelevinsky, Totally nonnegative and oscillatory
elements in semisimple groups, Proc. Amer.
Math. Soc. 128 (2000), no. 12, 3749–3759. MR 1694341
(2001b:22014), http://dx.doi.org/10.1090/S0002-9939-00-05487-3
- 11.
F.
R. Gantmacher and M.
G. Kreĭn, Oszillationsmatrizen, Oszillationskerne und kleine
Schwingungen mechanischer Systeme, Wissenschaftliche Bearbeitung der
deutschen Ausgabe: Alfred Stöhr. Mathematische Lehrbücher und
Monographien, I. Abteilung, Bd. V, Akademie-Verlag, Berlin, 1960 (German).
MR
0114338 (22 #5161)
Z.
I. Halilov, Cauchy’s problem for an infinite system of
partial differential equations, Doklady Akad. Nauk SSSR (N.S.)
84 (1952), 229–232 (Russian). MR 0049461
(14,178d)
O.
G. Owens, Homogeneous Dirichlet problem for inhomogeneous
ultrahyperbolic equation, Amer. J. Math. 74 (1952),
307–316. MR 0049460
(14,178c)
Chieh-Chien
Chang and Jack
Werner, A solution of the telegraph equation with application to
two dimensional supersonic shear flow, J. Math. Physics
31 (1952), 91–101. MR 0049458
(14,178a)
Roberto
Conti, Determinazione in grande delle soluzioni di
un’equazione di tipo misto della dinamica dei gas in funzione dei
valori assunti sulla linea parabolica, Ann. Mat. Pura Appl. (4)
32 (1951), 235–248 (Italian). MR 0049459
(14,178b)
F.
R. Gantmaher and M.
G. Kreĭn, Oscillyacionye matricy i yadra i malye kolebaniya
mehaničeskih sistem, Gosudarstv. Isdat. Tehn.-Teor. Lit.,
Moscow-Leningrad, 1950 (Russian). 2d ed. MR 0049462
(14,178e)
- 12.
D. V. Ingerman, Discrete and continuous inverse boundary problems on a disk, Ph.D. thesis, University of Washington, 1997.
- 13.
Samuel
Karlin, Total positivity. Vol. I, Stanford University Press,
Stanford, Calif, 1968. MR 0230102
(37 #5667)
- 14.
Samuel
Karlin and James
McGregor, Coincidence probabilities, Pacific J. Math.
9 (1959), 1141–1164. MR 0114248
(22 #5072)
- 15.
Gregory
F. Lawler, Intersections of random walks, Probability and its
Applications, Birkhäuser Boston Inc., Boston, MA, 1991. MR 1117680
(92f:60122)
- 16.
Bernt
Lindström, On the vector representations of induced
matroids, Bull. London Math. Soc. 5 (1973),
85–90. MR
0335313 (49 #95)
- 17.
A. A. Milne, The house at Pooh corner, E. P. Dutton & Co., 1928 ff.
- 18.
Robin
Pemantle, Choosing a spanning tree for the integer lattice
uniformly, Ann. Probab. 19 (1991), no. 4,
1559–1574. MR 1127715
(92g:60014)
- 19.
James
Gary Propp and David
Bruce Wilson, How to get a perfectly random sample from a generic
Markov chain and generate a random spanning tree of a directed graph,
J. Algorithms 27 (1998), no. 2, 170–217. 7th
Annual ACM-SIAM Symposium on Discrete Algorithms (Atlanta, GA, 1996). MR 1622393
(99g:60116), http://dx.doi.org/10.1006/jagm.1997.0917
- 20.
Frank
Spitzer, Principles of random walk, The University Series in
Higher Mathematics, D. Van Nostrand Co., Inc., Princeton,
N.J.-Toronto-London, 1964. MR 0171290
(30 #1521)
- 21.
Richard
P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge
Studies in Advanced Mathematics, vol. 49, Cambridge University Press,
Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of
the 1986 original. MR 1442260
(98a:05001)
- 22.
Proceedings of the Twenty-eighth Annual ACM Symposium on the Theory of
Computing, ACM Press, New York, 1996. Held in Philadelphia, PA, May
22–24, 1996. MR 1427491
(97g:68005)
- 1.
- I. Benjamini, R. Lyons, Y. Peres, and O. Schramm, Uniform spanning forests, Ann. Probab., to appear.
- 2.
- W. Böhm and S. G. Mohanty, On the Karlin-McGregor theorem and applications, Ann. Appl. Probab. 7 (1997), 314-325. MR 98g:60131
- 3.
- B. Bollobás, Modern graph theory, Springer-Verlag, New York, 1998. MR 99h:05001
- 4.
- J. M. Borwein, D. M. Bradley, D. J. Broadhurst, and P. Lisonek, Special values of multiple polylogarithms, Trans. Amer. Math. Soc., to appear.
- 5.
- Y. Colin de Verdière, Réseaux électriques planaires, Prépublications de l'Institut Fourier 225 (1992), 1-20.
- 6.
- E. Curtis, D. V. Ingerman, and J. Morrow. Circular planar graphs and resistor networks, Linear Algebra Appl. 283 (1998), 115-150. MR 99k:05096
- 7.
- E. Curtis, E. Mooers, and J. Morrow, Finding the conductors in circular networks from boundary measurements, RAIRO Modél. Math. Anal. Numér. 28 (1994), 781-814. MR 96i:65110
- 8.
- P. G. Doyle and J. L. Snell, Random walks and electric networks, Math. Assoc. of America, 1984. MR 89a:94023
- 9.
- R. Durrett, Brownian motion and martingales in analysis, Wadsworth, 1984. MR 87a:60054
- 10.
- S. Fomin and A. Zelevinsky, Total positivity: tests and parametrizations, Math. Intelligencer 22 (2000), no. 1, 23-33. MR 2001b:22014
- 11.
- F. R. Gantmacher and M. G. Krein, Oszillationsmatrizen, Oszillationskerne und kleine Schwingungen mechanischer Systeme, Akademie-Verlag, Berlin, 1960. MR 22:5161 (Russian edition: Moscow-Leningrad, 1950. MR 14:178)
- 12.
- D. V. Ingerman, Discrete and continuous inverse boundary problems on a disk, Ph.D. thesis, University of Washington, 1997.
- 13.
- S. Karlin, Total positivity, Stanford University Press, 1968. MR 37:5667
- 14.
- S. Karlin and G. McGregor, Coincidence probabilities, Pacific J. Math. 9 (1959), 1141-1164. MR 22:5072
- 15.
- G. Lawler, Intersections of random walks, Birkhäuser, 1991. MR 92f:60122
- 16.
- B. Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85-90. MR 49:95
- 17.
- A. A. Milne, The house at Pooh corner, E. P. Dutton & Co., 1928 ff.
- 18.
- R. Pemantle, Choosing a spanning tree for the integer lattice uniformly, Ann. Probab. 19 (1991), 1559-1574. MR 92g:60014
- 19.
- J. G. Propp and D. B. Wilson, How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph, J. Algorithms 27 (1998), 170-217. MR 99g:60116
- 20.
- F. Spitzer, Principles of random walk, Van Nostrand, 1964. MR 30:1521
- 21.
- R. P. Stanley, Enumerative combinatorics, vol. 1, 2d ed., Cambridge Univ. Press, 1997. MR 98a:05001
- 22.
- D B. Wilson, Generating random spanning trees more quickly than the cover time, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 296-303, 1996. MR 97g:68005
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (2000):
15A48,
05C50,
31C20,
60J65
Retrieve articles in all journals
with MSC (2000):
15A48,
05C50,
31C20,
60J65
Additional Information
Sergey Fomin
Affiliation:
Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109
Email:
fomin@math.lsa.umich.edu
DOI:
http://dx.doi.org/10.1090/S0002-9947-01-02824-0
PII:
S 0002-9947(01)02824-0
Keywords:
Total positivity,
loop-erased walk,
hitting probability,
resistor network
Received by editor(s):
July 27, 2000
Received by editor(s) in revised form:
January 19, 2001
Posted:
April 9, 2001
Additional Notes:
Supported in part by NSF grant #DMS-9700927
Article copyright:
© Copyright 2001 by Sergey Fomin
|
