Metric graphs, cross ratios, and Rayleigh’s laws. (English) Zbl 1507.05094

de Jong, Robin; Shokrieh, Farbod

Rocky Mt. J. Math. 52, No. 4, 1403-1422 (2022).

Summary: We systematically study the notion of cross ratios and energy pairings on metric graphs and electrical networks. We show that several foundational results on electrical networks and metric graphs immediately follow from the basic properties of cross ratios. For example, the projection matrices of Kirchhoff have natural (and efficiently computable) expressions in terms of cross ratios. We prove a generalized version of Rayleigh’s law, relating energy pairings and cross ratios on metric graphs before and after contracting an edge segment. Quantitative versions of Rayleigh’s law for effective resistances, potential kernels, and cross ratios will follow as immediate corollaries.

MSC:

05C90	Applications of graph theory
05C12	Distance in graphs
05C50	Graphs and linear algebra (matrices, eigenvalues, etc.)
05C82	Small world graphs, complex networks (graph-theoretic aspects)
14T15	Combinatorial aspects of tropical varieties
35J05	Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation
94C05	Analytic circuit theory

Keywords:

metric graph; electrical network; Laplacian; energy pairing; potential kernel; cross ratio; resistance; spanning tree; Rayleigh’s law

References:

[1]	Y. An, M. Baker, G. Kuperberg, and F. Shokrieh, “Canonical representatives for divisor classes on tropical curves and the matrix-tree theorem”, Forum Math. Sigma 2 (2014), art. id. e24. · Zbl 1306.05013 · doi:10.1017/fms.2014.25
[2]	M. Baker and X. Faber, “Metrized graphs, Laplacian operators, and electrical networks”, pp. 15-33 in Quantum graphs and their applications, edited by G. Berkolaiko et al., Contemp. Math. 415, Amer. Math. Soc., Providence, RI, 2006. · Zbl 1114.94025 · doi:10.1090/conm/415/07857
[3]	M. Baker and X. Faber, “Metric properties of the tropical Abel-Jacobi map”, J. Algebraic Combin. 33:3 (2011), 349-381. · Zbl 1215.14060 · doi:10.1007/s10801-010-0247-3
[4]	M. Baker and R. Rumely, “Harmonic analysis on metrized graphs”, Canad. J. Math. 59:2 (2007), 225-275. · Zbl 1123.43006 · doi:10.4153/CJM-2007-010-2
[5]	M. Baker and R. Rumely, Potential theory and dynamics on the Berkovich projective line, Mathematical Surveys and Monographs 159, Amer. Math. Soc., Providence, RI, 2010. · Zbl 1196.14002 · doi:10.1090/surv/159
[6]	M. Baker and F. Shokrieh, “Chip-firing games, potential theory on graphs, and spanning trees”, J. Combin. Theory Ser. A 120:1 (2013), 164-182. · Zbl 1408.05089 · doi:10.1016/j.jcta.2012.07.011
[7]	I. Benjamini, R. Lyons, Y. Peres, and O. Schramm, “Uniform spanning forests”, Ann. Probab. 29:1 (2001), 1-65. · Zbl 1016.60009 · doi:10.1214/aop/1008956321
[8]	N. Biggs, “Algebraic potential theory on graphs”, Bull. London Math. Soc. 29:6 (1997), 641-682. · Zbl 0892.05033 · doi:10.1112/S0024609397003305
[9]	B. Bollobás, Modern graph theory, Graduate Texts in Mathematics 184, Springer, New York, 1998. · Zbl 0902.05016 · doi:10.1007/978-1-4612-0619-4
[10]	M. R. Bridson and A. Haefliger, Metric spaces of non-positive curvature, Grundl. Math. Wissen. 319, Springer, Berlin, 1999. · Zbl 0988.53001 · doi:10.1007/978-3-662-12494-9
[11]	R. L. Brooks, C. A. B. Smith, A. H. Stone, and W. T. Tutte, “The dissection of rectangles into squares”, Duke Math. J. 7 (1940), 312-340. · Zbl 0024.16501
[12]	R. Burton and R. Pemantle, “Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances”, Ann. Probab. 21:3 (1993), 1329-1371. · Zbl 0785.60007
[13]	T. Chinburg and R. Rumely, “The capacity pairing”, J. Reine Angew. Math. 434 (1993), 1-44. · Zbl 0756.14013 · doi:10.1515/crll.1993.434.1
[14]	H. Flanders, “A new proof of R. Foster’s averaging formula in networks”, Linear Algebra Appl. 8 (1974), 35-37. · Zbl 0276.94013 · doi:10.1016/0024-3795(74)90005-6
[15]	R. M. Foster, “The average impedance of an electrical network”, pp. 333-340 in Reissner anniversary volume, contributions to applied mechanics, J. W. Edwards, Ann Arbor, Michigan, 1948.
[16]	W. H. Hayt, J. Kemmerly, and S. M. Durbin, Engineering circuit analysis, 8th ed., McGraw-Hill, 2012.
[17]	J. B. Hough, M. Krishnapur, Y. Peres, and B. Virág, Zeros of Gaussian analytic functions and determinantal point processes, University Lecture Series 51, Amer. Math. Soc., Providence, RI, 2009. · Zbl 1190.60038 · doi:10.1090/ulect/051
[18]	G. Kirchhoff, “Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird”, Annalen der Physik 148:12 (1847), 497-508. · doi:10.1002/andp.18471481202
[19]	D. J. Klein and M. Randić, “Resistance distance”, J. Math. Chem. 12:1-4 (1993), 81-95. · doi:10.1007/BF01164627
[20]	R. Lyons and Y. Peres, Probability on trees and networks, Cambridge Series in Statistical and Probabilistic Mathematics 42, Cambridge Univ. Press, New York, 2016. · Zbl 1376.05002 · doi:10.1017/9781316672815
[21]	S. Seshu and N. Balabanian, Linear network analysis, Wiley, 1959.
[22]	F. Shokrieh and C. Wu, “Canonical measures on metric graphs and a Kazhdan’s theorem”, Invent. Math. 215:3 (2019), 819-862. · Zbl 1440.14284 · doi:10.1007/s00222-018-0838-5
[23]	P. Tetali, “Random walks and the effective resistance of networks”, J. Theoret. Probab. 4:1 (1991), 101-109. · Zbl 0722.60070 · doi:10.1007/BF01046996
[24]	W. T. Tutte, Graph theory, Encyclopedia of Mathematics and its Applications 21, Addison-Wesley, Reading, MA, 1984. · Zbl 0554.05001
[25]	S. Zhang, “Admissible pairing on a curve”, Invent. Math. 112:1 (1993), 171-193 · Zbl 0795.14015 · doi:10.1007/BF01232429