|
Loop-erased walks and total positivity
Author(s):
Sergey
Fomin
Journal:
Trans. Amer. Math. Soc.
353
(2001),
3563-3583.
MSC (2000):
Primary 15A48;
Secondary 05C50, 31C20, 60J65
Posted:
April 9, 2001
Retrieve article in:
PDF DVI PostScript
This article is available free of charge
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.
References:
-
- 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:
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
Copyright of article:
Copyright
2001,
by Sergey Fomin
|
Comments: webmaster@ams.org