Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



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
Published electronically: April 9, 2001
MathSciNet review: 1837248
Full-text PDF

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 [Enhancements On Off] (What's this?)

  • 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

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
Published electronically: April 9, 2001
Additional Notes: Supported in part by NSF grant #DMS-9700927
Article copyright: © Copyright 2001 by Sergey Fomin

American Mathematical Society