Modulus on graphs as a generalization of standard graph theoretic quantities
HTML articles powered by AMS MathViewer
- by Nathan Albin, Megan Brunner, Roberto Perez, Pietro Poggi-Corradini and Natalie Wiens
- Conform. Geom. Dyn. 19 (2015), 298-317
- DOI: https://doi.org/10.1090/ecgd/287
- Published electronically: December 4, 2015
- PDF | Request permission
Abstract:
This paper presents new results for the modulus of families of walks on a graph—a discrete analog of the modulus of curve families due to Beurling and Ahlfors. Particular attention is paid to the dependence of the modulus on its parameters. Modulus is shown to generalize (and interpolate among) three important quantities in graph theory: shortest path, effective resistance, and max-flow or min-cut.References
- Lars Valerian Ahlfors, Collected papers. Vol. 1, Contemporary Mathematicians, Birkhäuser, Boston, Mass., 1982. 1929–1955; Edited with the assistance of Rae Michael Shortt. MR 688648
- N. Albin and P. Poggi-Corradini, The dual method for $p$-modulus on graphs. Preprint.
- N. Albin and P. Poggi-Corradini, F. Darabi Sahneh, and M. Goering, Modulus of families of walks on graphs. arXiv:1401.7640 (http://arxiv.org/abs/1403.5750).
- Arne Beurling, The collected works of Arne Beurling. Vol. 1, Contemporary Mathematicians, Birkhäuser Boston, Inc., Boston, MA, 1989. Complex analysis; Edited by L. Carleson, P. Malliavin, J. Neuberger and J. Wermer. MR 1057613
- James A. Clarkson, Uniformly convex spaces, Trans. Amer. Math. Soc. 40 (1936), no. 3, 396–414. MR 1501880, DOI 10.1090/S0002-9947-1936-1501880-4
- R. J. Duffin, The extremal length of a network, J. Math. Anal. Appl. 5 (1962), 200–215. MR 143468, DOI 10.1016/S0022-247X(62)80004-3
- Josh Ericson, Pietro Poggi-Corradini, and Hainan Zhang, Effective resistance on graphs and the epidemic quasimetric, Involve 7 (2014), no. 1, 97–124. MR 3127324, DOI 10.2140/involve.2014.7.97
- L. R. Ford Jr. and D. R. Fulkerson, Maximal flow through a network, Canadian J. Math. 8 (1956), 399–404. MR 79251, DOI 10.4153/CJM-1956-045-5
- Arpita Ghosh, Stephen Boyd, and Amin Saberi, Minimizing effective resistance of a graph, SIAM Rev. 50 (2008), no. 1, 37–66. MR 2403057, DOI 10.1137/050645452
- Peter Haïssinsky, Empilements de cercles et modules combinatoires, Ann. Inst. Fourier (Grenoble) 59 (2009), no. 6, 2175–2222 (French, with English and French summaries). MR 2640918, DOI 10.5802/aif.2488
- Juha Heinonen, Lectures on analysis on metric spaces, Universitext, Springer-Verlag, New York, 2001. MR 1800917, DOI 10.1007/978-1-4613-0131-8
- D. J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12 (1993), no. 1-4, 81–95. Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK, 1991). MR 1219566, DOI 10.1007/BF01164627
- R. Tyrrell Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, N.J., 1970. MR 0274683, DOI 10.1515/9781400873173
- Oded Schramm, Square tilings with prescribed combinatorics, Israel J. Math. 84 (1993), no. 1-2, 97–118. MR 1244661, DOI 10.1007/BF02761693
- H. Shakeri, P. Poggi-Corradini, C. Scoglio, and N. Albin, Generalized network measures based on modulus of families of walks. Preprint.
- G. F. Young, L. Scardovi, and N. E. Leonard, A new notion of effective resistance for directed graphs-Part I: Definition and properties. http://arxiv.org/abs/1310.5163.
Bibliographic Information
- Nathan Albin
- Affiliation: Department of Mathematics, Kansas State University, 138 Cardwell Hall, Manhattan, Kansas 66506
- Email: albin@math.ksu.edu; pietro@math.ksu.edu
- Received by editor(s): June 1, 2015
- Received by editor(s) in revised form: October 30, 2015
- Published electronically: December 4, 2015
- Additional Notes: This material is based upon work supported by the National Science Foundation under Grant No. 126287 (Albin, Brunner, Perez, Wiens), through Kansas State University’s 2014 Summer Undergraduate Mathematics Research program, and under Grant Nos. 1201427 (Poggi-Corradini) and 1515810 (Albin)
- © Copyright 2015 American Mathematical Society
- Journal: Conform. Geom. Dyn. 19 (2015), 298-317
- MSC (2010): Primary 90C35
- DOI: https://doi.org/10.1090/ecgd/287
- MathSciNet review: 3430866