×

The space of circular planar electrical networks. (English) Zbl 1357.90022

Summary: We discuss several parametrizations of the space of circular planar electrical networks. With any circular planar network we associate a canonical minimal network with the same response matrix, called a “standard” network. The conductances of edges in a standard network can be computed as a biratio of Pfaffians constructed from the response matrix. The conductances serve as coordinates that are compatible with the cell structure of circular planar networks in the sense that one conductance degenerates to \(0\) or \(\infty\) when moving from a cell to a boundary cell. We also show how to test if a network with \(n\) nodes is well-connected by checking that \(\binom{n}{2}\) minors of the \(n\times n\) response matrix are positive; Colin de Verdière had previously shown that it was sufficient to check the positivity of exponentially many minors. For standard networks with \(m\) edges, positivity of the conductances can be tested by checking the positivity of \(m+1\) Pfaffians.

MSC:

90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] J. Alman, C. Lian, and B. Tran, {\it Circular planar electrical networks: Posets and positivity}, J. Combin. Theory Ser. A, 132 (2015), pp. 58-101, . · Zbl 1307.05055
[2] L. Borcea, V. Druskin, and F. Guevara Vasquez, {\it Electrical impedance tomography with resistor networks}, Inverse Problems, 24 (2008), 035013, . · Zbl 1147.78002
[3] R. K. Card and B. I. Muranaka, {\it Using Network Amalgamation and Separation to Solve the Inverse Problem}, (2002).
[4] G. D. Carroll and D. Speyer, {\it The cube recurrence}, Electron. J. Combin., 11 (2004), R73, . · Zbl 1060.05004
[5] Y. Colin de Verdière, {\it Réseaux électriques planaires.} I, Comment. Math. Helv., 69 (1994), pp. 351-374, . · Zbl 0816.05052
[6] Y. Colin de Verdière, I. Gitler, and D. Vertigan, {\it Réseaux électriques planaires.} II, Comment. Math. Helv., 71 (1996), pp. 144-167, . · Zbl 0853.05074
[7] E. Curtis, E. Mooers, and J. Morrow, {\it Finding the conductors in circular networks from boundary measurements}, ESAIM Math. Model. Numer. Anal., 28 (1994), pp. 781-814. · Zbl 0820.94028
[8] E. B. Curtis, D. Ingerman, and J. A. Morrow, {\it Circular planar graphs and resistor networks}, Linear Algebra Appl., 283 (1998), pp. 115-150, . · Zbl 0931.05051
[9] E. B. Curtis and J. A. Morrow, {\it Inverse Problems for Electrical Networks}, Ser. Appl. Math., World Scientific, Singapore, 2000, . · Zbl 1056.94022
[10] N. Elkies, G. Kuperberg, M. Larsen, and J. Propp, {\it Alternating-sign matrices and domino tilings.} I, J. Algebraic Combin., 1 (1992), pp. 111-132. . · Zbl 0779.05009
[11] M. Fayers, {\it Dyck Tilings and the Homogeneous Garnir Relations for Graded Specht Modules}, preprint, \arXiv1309.6467, 2015. · Zbl 1365.05294
[12] I. Fischer and P. Nadeau, {\it Fully packed loops in a triangle: Matchings, paths and puzzles}, J. Combin. Theory Ser. A, 130 (2015), pp. 64-118, . · Zbl 1303.05006
[13] S. Fomin and A. Zelevinsky, {\it Total positivity: Tests and parametrizations}, Math. Intelligencer, 22 (2000), pp. 23-33, . · Zbl 1052.15500
[14] A. B. Goncharov and R. Kenyon, {\it Dimers and cluster integrable systems}, Ann. Sci. Éc. Norm. Supér. (4), 46 (2013), pp. 747-813. · Zbl 1288.37025
[15] Y. Huang and C. Wen, {\it ABJM amplitudes and the positive orthogonal Grassmannian}, J. High Energy Phys., 2014 (2014), . · Zbl 1307.81057
[16] Y.-T. Huang, C. Wen, and D. Xie, {\it The positive orthogonal Grassmannian and loop amplitudes of ABJM}, J. Phys. A, 47 (2014), 474008, . · Zbl 1307.81057
[17] W. Johnson, {\it Circular Planar Resistor Networks with Nonlinear and Signed Conductors}, preprint, \arXiv1203.4045, 2012.
[18] R. Kenyon, {\it The Laplacian on planar graphs and graphs on surfaces}, in Current Developments in Mathematics, 2011, International Press, Boston, 2012, pp. 1-55, . · Zbl 1316.05087
[19] R. W. Kenyon and D. B. Wilson, {\it Combinatorics of tripartite boundary connections for trees and dimers}, Electron. J. Combin., 16 (2009), R112, . · Zbl 1225.60020
[20] R. W. Kenyon and D. B. Wilson, {\it Boundary partitions in trees and dimers}, Trans. Amer. Math. Soc., 363 (2011), pp. 1325-1364, . · Zbl 1230.60009
[21] R. W. Kenyon and D. B. Wilson, {\it Double-dimer pairings and skew Young diagrams}, Electron. J. Combin., 18 (2011), P130, . · Zbl 1247.05025
[22] R. W. Kenyon and D. B. Wilson, {\it Spanning trees of graphs on surfaces and the intensity of loop-erased random walk on planar graphs}, J. Amer. Math. Soc., 28 (2015), pp. 985-1030, . · Zbl 1327.60033
[23] J. Kim and S. Lee, {\it Positroid stratification of orthogonal Grassmannian and ABJM amplitudes}, J. High Energy Phys., 2014 (2014), 85, . · Zbl 1333.81254
[24] J. S. Kim, {\it Proofs of two conjectures of Kenyon and Wilson on Dyck tilings}, J. Combin. Theory Ser. A, 119 (2012), pp. 1692-1710, . · Zbl 1246.05039
[25] J. S. Kim, K. Mészáros, G. Panova, and D. B. Wilson, {\it Dyck tilings, increasing trees, descents, and inversions}, J. Combin. Theory Ser. A, 122 (2014), pp. 9-27, . · Zbl 1311.05207
[26] E. H. Kuo, {\it Applications of graphical condensation for enumerating matchings and tilings}, Theoret. Comput. Sci., 319 (2004), pp. 29-57, . · Zbl 1043.05099
[27] T. Lai, {\it Proof of a Conjecture of Kenyon and Wilson on Semicontiguous Minors}, preprint, \arXiv1507.02611, 2015.
[28] T. Lam, {\it Electroid Varieties and a Compactification of the Space of Electrical Networks}, \arXiv1402.6261, 2014.
[29] T. Lam, {\it The uncrossing partial order on matchings is Eulerian}, J. Combin. Theory Ser. A, 135 (2015), pp. 105-111, . · Zbl 1319.05106
[30] T. Lam and P. Pylyavskyy, {\it Electrical networks and Lie theory}, Algebra Number Theory, 9 (2015), pp. 1401-1418, . · Zbl 1325.05181
[31] T. Lam and L. Williams, {\it Total positivity for cominuscule Grassmannians}, New York J. Math., 14 (2008), pp. 53-99, . · Zbl 1144.20029
[32] J. T. Russell, {\it \(⋆\) and \(\mathcal K\) solve the inverse problem}, (2003).
[33] K. Shigechi and P. Zinn-Justin, {\it Path representation of maximal parabolic Kazhdan-Lusztig polynomials}, J. Pure Appl. Algebra, 216 (2012), pp. 2533-2548 · Zbl 1262.20006
[34] F. Zhang, ed., {\it The Schur Complement and its Applications}, Numer. Methods Algorithms 4, Springer, New York, 2005, . · Zbl 1075.15002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.