Modulus on graphs as a generalization of standard graph theoretic quantities

Albin, Nathan; Brunner, Megan; Perez, Roberto; Poggi-Corradini, Pietro; Wiens, Natalie

doi:10.1090/ecgd/287

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.