Loop-erased walks and total positivity

Fomin, Sergey

doi:10.1090/S0002-9947-01-02824-0

Loop-erased walks and total positivity
HTML articles powered by AMS MathViewer

by Sergey Fomin

Trans. Amer. Math. Soc. 353 (2001), 3563-3583

DOI: https://doi.org/10.1090/S0002-9947-01-02824-0

Published electronically: April 9, 2001

PDF

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

I. Benjamini, R. Lyons, Y. Peres, and O. Schramm, Uniform spanning forests, Ann. Probab., to appear.
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, DOI 10.1214/aoap/1034625333
Béla Bollobás, Modern graph theory, Graduate Texts in Mathematics, vol. 184, Springer-Verlag, New York, 1998. MR 1633290, DOI 10.1007/978-1-4612-0619-4
J. M. Borwein, D. M. Bradley, D. J. Broadhurst, and P. Lisoněk, Special values of multiple polylogarithms, Trans. Amer. Math. Soc., to appear.
Y. Colin de Verdière, Réseaux électriques planaires, Prépublications de l’Institut Fourier 225 (1992), 1–20.
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, DOI 10.1016/S0024-3795(98)10087-3
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, DOI 10.1051/m2an/1994280707811
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
Richard Durrett, Brownian motion and martingales in analysis, Wadsworth Mathematics Series, Wadsworth International Group, Belmont, CA, 1984. MR 750829
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, DOI 10.1090/S0002-9939-00-05487-3
P. Erdös, Note on products of consecutive integers, J. London Math. Soc. 14 (1939), 194–198. MR 22, DOI 10.1112/jlms/s1-14.3.194
D. V. Ingerman, Discrete and continuous inverse boundary problems on a disk, Ph.D. thesis, University of Washington, 1997.
Samuel Karlin, Total positivity. Vol. I, Stanford University Press, Stanford, Calif., 1968. MR 0230102
Samuel Karlin and James McGregor, Coincidence probabilities, Pacific J. Math. 9 (1959), 1141–1164. MR 114248
Gregory F. Lawler, Intersections of random walks, Probability and its Applications, Birkhäuser Boston, Inc., Boston, MA, 1991. MR 1117680
Bernt Lindström, On the vector representations of induced matroids, Bull. London Math. Soc. 5 (1973), 85–90. MR 335313, DOI 10.1112/blms/5.1.85
A. A. Milne, The house at Pooh corner, E. P. Dutton & Co., 1928 ff.
Robin Pemantle, Choosing a spanning tree for the integer lattice uniformly, Ann. Probab. 19 (1991), no. 4, 1559–1574. MR 1127715
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, DOI 10.1006/jagm.1997.0917
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
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, DOI 10.1017/CBO9780511805967
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